Dynamic Programming(동적계획법)
다이나믹 프로그래밍은 특정한 알고리즘이라기 보다는 분할정복(devide-and-conquer)와 같은 하나의 문제 해결 기법이다.
문제 해결을 위해 컴퓨터를 사용할 때, 컴퓨터의 자원과 속도에는 한계가 있다. 따라서 우리는 가장 효율적인 알고리즘을 고안하게 되는데, 메모리 공간을 조금 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 문제해결 방법을 다이나믹 프로그래밍(동적계획법)이라고 한다.
다이나믹 프로그래밍 기법은 분할정복(devide-and-conquer)과 같이 subproblem으로 문제를 나누고, 해결하는 과정을 거친다. 분할정복 과의 차이점은 분할정복이 문제를 disjoint subproblem으로 나누는 반면에, 다이나믹 프로그래밍의 경우 subproblem이 겹칠 수 있다는 점이다.
이 겹치는 subproblem들을 여러번 계산하지 않고, 메모리에 저장함으로써 효율적으로 문제를 해결하는 것이 다이나믹 프로그래밍의 핵심이다.
설계방법
📌 Four-step method
1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution in a bottom-up fashion
4. Construct an optimal solution from computed information
위 내용은 알고리즘 시간에 dynamic programming 알고리즘을 설계하는 방법으로 배운 내용이다. 위 과정을 따라서 dynamic programming 알고리즘을 구현할 수 있는데, 실제로 문제를 접하면서 중요하다고 느낀점은 2번, solution을 점화식 형태로 표현하는 것 이다.
문제의 optimal solution이 무엇인지 고민해보고, 그것을 subproblem의 optimal solution으로 구성된 점화식으로 표현할 수 있다면, 생각보다 쉽게 문제를 해결 할 수 있다.
두가지 방식
dynamic programming 기법은 두가지 방식으로 구현할 수 있는데, 재귀함수를 사용하는 top-down 방식이 있고, 반복문으로 구현하는 Bottom-up방식이 있다.
피보나치 함수를 두가지 방식으로 구현한 소스코드를 통해 더 자세히 이해할 수 있을 것이다.
Top-down with memoization
다이나믹 프로그래밍의 top-down방식은 기존의 재귀함수를 통한 방식과 같이 문제를 해결하지만, 각 subproblem의 solution을 저장한다(memoization)는 점이 추가된다.
# Dynamic Programming -- memoization (topdown)활용! O(N)의 시간복잡도.
d = [0] * 100
def fiboMemo(x):
if x == 1 or x == 2:
return 1
if d[x] != 0:
return d[x]
d[x] = fiboMemo(x - 1) + fiboMemo(x - 2)
return d[x]피보나치 수열은 점화식 형태, 재귀함수로 나타낼 수 있는 대표적인 case 이다. 위 소스코드에서 기존의 재귀함수를 사용한 코드와 달라진 점은 리스트 d를 통해 계산 결과를 저장하고, 이미 계산된 결과라면 저장된 값을 사용한다는 점이다.
이렇게 top-down 방식으로 큰 문제에서 작은 문제로 내려가면서 문제를 풀 때, 메모리 공간에 계산된 결과를 저장하여 사용하는 기법을 메모이제이션(memoization)이라고 한다. 이는 대표적인 다이나믹 프로그래밍 기법이다.
Bottom-up
bottom-up방식은 subproblem을 작은 것 부터 순서대로 해결하여 최적의 solution을 찾아낸다. 특정 subproblem을 풀 때, 보다 작은 subproblem에 대한 해답은 이미 계산하여 저장되어 있고, 그 값을 사용한다.
d=[0]*100
def fiboBottomUp(x):
d[1] = 1
d[2] = 1
for i in range(3, x + 1):
d[i] = d[i - 1] + d[i - 2]
return d[x]이 방법에서도 subproblem의 해법을 저장하기 위해 메모리를 사용하는데, 이를 DP table이라고 부르며, 위 코드에서 리스트 d에 해당한다. 그리고, 재귀함수가 아니라 반복문을 사용하여 그 안에서 점화식 형태로 표현한 subproblem의 solution을 통해 알고리즘을 구현한다.
효율성
위의 두가지 방식으로 다이나믹 프로그래밍 기법을 적용한 피보나치 수열 함수의 경우, 시간 복잡도가 O(N)이다. f(1)이 f(2)에 사용되고, 또 그 값이 f(3) 계산에 사용되는 식이다.
기존의 재귀함수만을 사용해 구현한 피보나치 수열 함수의 경우, 시간 복잡도가 O(2^N)의 지수시간에 해당하는 복잡도를 가진다. 이는 계속 f(3), f(4)와 같은 subproblem이 계속 반복되어 계산되기 때문이다.
피보나치 수열의 예시처럼 다이나믹 프로그래밍을 통해 subproblem의 해법을 메모리에 저장하는 과정을 통해 연산속도를 높이고 효율적인 문제해결을 할 수 있다.
🍯 Tip
이번에 다이나믹 프로그래밍을 공부하고 코딩테스트 문제를 접하면서 느낀 점은 문제에 대한 solution을 점화식 형태로 표현하는 것이 굉장히 중요한 포인트라는 점이다.
다이나믹 프로그래밍 문제의 경우 문제가 여러개의 subproblem으로 나뉘어 구성되어 있을 때 특정한 시점/단계의 subproblem을 다른 subproblem의 해법을 사용해 점화식 형태로 잘 표현하게 되면, 생각보다 쉽게 문제들이 풀렸다.
따라서, 아래와 같은 방식으로 접근하면 다이나믹 프로그래밍 문제를 쉽게 해결할 수 있을 것 같다!
dp table에 해당하는 메모리 공간을 잡는다.- 점화식으로 optimal solution을 표현한다.
- 예외/기타 조건을 살펴본다.
- 가장 작은 subproblem의 해답은 보통 정해져 있으므로, 그 값을
dp table에 넣고 나머지에 대해 반복한다.
📚 Reference
이 글은 『이것이 코딩테스트다 with 파이썬』 을 통해 공부하면서 작성한 글입니다.
- 『이것이 코딩테스트다 with 파이썬』, 나동빈 지음
- 고려대학교 정순영 교수님 알고리즘 강의자료
