DP란 문제에 대한 정답이 될 가능성이 있는 모든 해결책을 “체계적”이고 “효율적”으로 탐색하는 풀이법를 말합니다.
모든 해결책을 다 탐색해보는 ‘완전 탐색’은 기본적으로 높은 시간 복잡도를 가집니다. 이를 ‘체계적’이고 ‘효율적으로 탐색하기 위해서는 몇 가지 조건이 있어야 합니다.
•
Overlapping Subproblems - 중복 하위 문제
◦
중복 계산해야 하는 하위 문제가 존재합니다.
•
Optimal Substructure - 최적 부분 구조
◦
하위 문제에서 구한 최적의 답이 큰 문제의 최적의 답을 구할 수 있는 구조여야 합니다.
피보나치 수열을 통해 dp에 대한 개념을 가져가 보도록 하겠습니다.
피보나치 수열은 다음과 같이 인 수열을 말합니다. 저희는 앞선 재귀 파트에서 가 recurrence relation(점화식)임과 이 base case임을 배웠습니다. 그리고 코드는 다음과 같았습니다.
def fibo(n):
if n == 1 or n == 2:
return 1
return fibo(n - 1) + fibo(n - 2)
Python
복사
이 때 시간복잡도는 매 번 2개의 함수를 호출함으로 의 시간복잡도를 가집니다. 아무래도 완전 탐색이다보니, 꽤 높은 시간복잡도를 가집니다. 그러나 이 피보나치에는 중복된 하위 문제들이 존재합니다. fibo(7)를 보도록 합시다.
위와 같이 상당한 중복이 발생하는 것을 볼 수 있습니다. 만약 전에 계산했던 것을 기억한다면, 위와 같은 중복 문제를 피할 수 있을 것입니다. 예를 들어, f(5)를 전에 계산 했으면, 후에 같은 과정으로 f(5)를 계산할 필요 없는 것입니다. 이렇게 될 시, 시간 복잡도는 O(n)으로 획기적으로 줄게 됩니다.
memo = {}
def fibo(n):
if n == 1 or n == 2:
return 1
if n not in memo:
memo[n] = fibo(n - 1) + fibo(n - 2)
return memo[n]
Python
복사
Top-down 방식과 Bottom-up 방식
memo = {}
def fibo(n):
if n == 1 or n == 2:
return 1
if n not in memo:
memo[n] = fibo(n - 1) + fibo(n - 2)
return memo[n]
Python
복사
위와 같은 방식은 f(n)부터 f(1)로 접근하므로, top-down 방식이라고 합니다. 반대로 f(1)부터 f(n)까지 접근하는 방식을 Bottom-up 방식이라고 합니다. Bottom-up 방식의 코드는 아래와 같습니다.
memo = {}
def fibo(n):
for i in range(3, n + 1):
memo[i] = memo[i - 1] + memo[i - 2]
return memo[n]
Python
복사
Top-down 방식은 재귀(recursion)로 구현되는 반면, Bottom-up 방식은 반복문(iteration)을 통해 구현됩니다. 또 Top-down 방식에서 memo를 채워 나가는 것을 memoization이라 하며, Bottom-up 방식에서 memo를 채워 나가는 것을 tabulation라고 합니다.
Copyright 2023. 노씨데브. All rights reserved. 무단 공유 및 배포를 금합니다.