동적 프로그래밍(Dynamic Programming = DP)은 동적계획법이라고도 한다. DP는 DFS / BFS 못지 않게 많이 사용되는 알고리즘인 것 같다. 코딩 테스트를 대비하면서 문제를 풀고 있는데 DP를 응용해서 푸는 문제도 종종 봤다. 물론 DP가 아니더라도 풀 수는 있지만 DP를 이용하면 좀 더 간단하게 풀 수 있다. 작년에도 공부를 살짝 했었는데 완벽하게 이해를 하지는 못했던 것 같다. 내가 프로젝트를 하면서 직접 사용한 경험이 없기에 금방 까먹는 것 같다. 아무튼 DP도 알아두면 쓸모가 많을 것 같다.
- 동적 프로그래밍 : DP
DP는 복잡한 하나의 큰 문제를 간단한 여러개의 작은 문제로 나누어 해결하는 것이다. 즉, 작은 문제의 정답을 이용하여 큰 문제의 정답을 찾는 것이다. 이때 작은 문제들은 중복된다는 것이 특징이라고 한다.
-
사용조건
중복되는 문제가 존재해야 한다. DP는 작은 문제의 결과를 다시 계산하지 않기 위해서 저장하여 사용하는 것이 핵심인데, 작은 문제가 중복되지 않는다면 재사용이 불가능하니 DP를 사용할 수 없다.
또한 작은 문제에서 구한 답이 전체 큰 문제에서도 동일한 결과를 보일 때 DP를 사용한다. 예를 들어 작은 문제에서 정답이 1인데 전체 문제에서 작은 문제의 구간에 정답이 2로 변할 경우에는 사용할 수 없다. -
사용방법
Step 1 : DP 적용 여부 파악
Step 2 : 문제 변수 파악
Step 3 : 점화식(관계식) 만들기
Step 4 : 결과 저장하기
Step 5 : 최소 크기의 문제 파악하기
Step 6 : 구현하기(반복문 혹은 재귀)
이 중에서 구현하기만 좀 더 알아보겠다.
첫번째는 반복문이다. 어디서는 Bottom-Up 방식이라고 한다. 작은 단위에서 문제를 풀어서 결과를 누적시켜서 큰 문제를 해결한다.
두번째는 재귀이다. Top-Down 방식이라고 한다. 큰 문제를 호출하여 작은 문제를 계속해서 호출한다. 가장 작은 최소단위의 문제까지 내려간 후에 재귀를 통해서 값을 호출하여 문제를 해결한다. 좀더 편한대로 하면 될 것 같다.
- Code
피보나치 수열을 DP로 풀어보려 한다. 아래 이미지는 피보나치 수열의 점화식이다.
num = 10
dp_list = [0] * num
dp_list[0] = dp_list[1] = 1
for i in range(2, num):
dp_list[i] = dp_list[i-1] + dp_list[i-2]
print("반복문: ",dp_list)
############################################################
dp_list = [0] * num
dp_list[0] = dp_list[1] = 1
def fibonacci(x=num):
if x == 0 or x == 1:
return 1
if dp_list[x] != 0:
return dp_list[x]
dp_list[x] = fibonacci(x-1) + fibonacci(x-2)
return dp_list[x]
fibonacci(num-1)
print("재귀 : ", dp_list)출력
반복문: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
재귀 : [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]