백준(30)
-
[정렬] 수 정렬하기(?)
2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 두 가지 방법으로 풀었는데, 나름 참신하다고 생각한 방법이 python 내장 정렬이랑 시간이 비슷하게 걸려서 놀랐다. 아래 104ms가 걸린 방법은 기존 정렬 알고리즘이랑 다르게 풀어보고 싶어서 내 나름대로 생각해서 해본 방식이다. length = int(input()) EMPTY = "EMPTY" dummy = [EMPTY] * 2001 for i in range(length): num = int(input()) + 1000 dummy[num] = num resul..
2021.05.30 -
[브루트 포스] 영화감독 숌
1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net n = int(input()) res = [] count = 0 target = '666' while True: if target.find('666') != -1: count = count + 1 if count == n: print(target) break target = str(int(target) + 1)
2021.05.30 -
[브루트 포스] 체스판 다시 칠하기
1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이 문제를 풀 당시에 매사가 귀찮아서 진짜 무식하게 풀었다 ㅠ from sys import stdin [n, m] = list(map(int, stdin.readline().split(" "))) WHITE_ROW = list("WBWBWBWB") BLACK_ROW = list("BWBWBWBW") matrix = [] for i in range(n): matrix.append(input()) def check_chess_row(row: str, is_w..
2021.05.30 -
[재귀] 하노이 탑
11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 첫 공부를 할 시점에 이 문제를 접했던 기억이 난다. 아무리 생각해도 모르겠어서 이 길이 내 길이 아닌지 심각하게 고민했던 시기가 있었는데... 지금에는 보고 쉽게 풀지만 그 당시에는 정말 내 앞을 가로막은 거대한 벽으로 느껴졌었다. count = int(input()) def move(now, target, empty, c): if c == 1: print(now, target) return move(now, empty, target, c - 1) ..
2021.05.30 -
[기본수학 2] 골드바흐의 추측
9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 와우.... 왜 골드바흐의 '추측'인가 했더니 아직 증명되지 않은 정수론의 미해결 문제라고 한다. 골드바흐의 추측 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 골드바흐의 추측(Goldbach's conjecture)은 오래전부터 알려진 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것 ko.wikipedia.org 흥미진진 난 비록 문제풀이를 위해 끄..
2021.03.28 -
[기본 수학2] 베르트랑 공준
www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 기존에 만들어 놓은 소수 구하는 함수를 돌렸더니 시간초과가 나서 잠시 당황했다. 매번 소수를 구하는 방식으로는 테스트케이스 갯수대비 짧은 제한시간(1초)을 통과할 수 없을 것 같아서... 테스트케이스에 나올 수 있는 소수의 범위 2*123456 내에 있는 소수를 다 구하고 인덱싱 하는 방식으로 전환했다. import math from sys import stdin test_case_list = [] wh..
2021.03.28