파이썬_알고리즘
-
알고리즘: 백준 2193번 이친수 (feat.Python)알고리즘/백준(BaekJoon) 2020. 7. 29. 15:09
예시를 들어서 문제를 좀 더 자세히 뜯어 봅시다. f(N) = N 자리 이친수의 개수 라고 할때, N = 5 인 상태 즉, f(5)는 어떻게 구성되어 있을까요? 우선 N = 5 일때 이친수는 다음과 같습니다. 10101 10100 10010 10001 10000 이것들을 가장 처음 1을 제외한 그 다음 1을 기준으로 쪼개보면 다음과 하나의 규칙을 발견할 수 있습니다. 10101 10100 f(3)과 모양이 같고 100010 f(2)와 모양이 같고 100001 f(1)과 모양이 같습니다. 100000 N = 0 는 정의되어 있지는 않지만 f(0) = 1이라고 합시다. 이렇게 봤을 때 f(5) = f(3) + f(2) + f(1) + f(0) 이라고 할 수 있겠군요! 그런데 여기서 또 살펴보면 f(2) + ..
-
알고리즘: 백준 1932번 정수 삼각형 (feat. Python)알고리즘/백준(BaekJoon) 2020. 7. 22. 07:21
최적 부분 구조와 중복되는 부분이 보인다. 다이나믹 프로그래밍으로! 점화식: n 번째 줄 0번째까지의 합 = n - 1번째 줄 0번째까지의 합 + n 번째 줄 0번째 값 n 번째 줄 1번째까지의 합 = max(n - 1번째 줄 0번째까지의 합, n - 1번째 줄 1번째까지의 합) + n번째 줄 1번째 값 n 번째 줄 2번째까지의 합 = max(n - 1번째 줄 1번째까지의 합, n - 1번째 줄 2번째까지의 합) + n번째 줄 2번째 값 ... n 번째 줄 n - 1번째까지의 합 = max(n - 1번째 줄 n - 2번째까지의 합, n - 1번째 줄 n - 1번째까지의 합) + n번째 줄 n - 1번째 값 n 번째 줄 n번째까지의 합 = n - 1번째 줄 n - 1번째까지의 합 + n 번째 줄 n번째 값..