[백준][Python][15558][BFS] 점프 게임
문제 : https://www.acmicpc.net/problem/15558 15558번: 점프 게임 첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000) 둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보가 주어지고, 각 문자의 의미는 왼쪽 줄의 의미와 동일하다. 왼쪽 줄의 1번 칸은 항상 안전한 칸이다. www.acmicpc.net BFS 문제다. 현재 위치를 x, 현재 줄을 line, 현재 시간을 time이라 할 때, 큐에 각각 [(line+1) %2, x + (k, 1, -1), time+1]을 넣어준다. 이때, ( (line+1) %2, x + (k, 1, -1) ) 에 대해 이미 탐색..
더보기
[백준][Python][17822][구현] 원판 돌리기
문제 : https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 구현 문제다. 우선, clockwise, counterclockwise, allavg, allsum 함수는 아래와 같다...
더보기
[백준][Python][14225][브루트 포스] 부분수열의 합
문제 : https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다. www.acmicpc.net 원래는 재귀 항목에 있는 문제이지만 난 그런 거 안 쓴다. 숫자 리스트를 받고, 이 리스트의 멱집합을 구한다. 이 부분집합들의 합을 더한 뒤 정렬한다. 코드가 최적화가 안됐다고 할 수 있는데, 어차피 멱집합은 O(2^n)이다. 정렬 한두 번 더한다고 O(nlo..
더보기
[백준][Python][2747][lru_cache] 피보나치 수
문제 : https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 www.acmicpc.net python 3.2 이상 기준이다. functools 의 lru_cache decorator 는 memoization을 자동..
더보기
