[파이썬 알고리즘 인터뷰] 다이나믹 프로그래밍
다이나믹 프로그래밍(Dynamic Programming) 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다. 이를 이용하면, 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제, 즉 최적 부분 구조(Optimal Substructure)를 갖고 있는 문제를 풀이할 수 있다.
다이나믹 프로그래밍 방법론
다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식으로 구성된다.
- 탑다운: 위에서 부터 아래로 내려가는 방식으로 하향식이라고도 불린다.
- 보텀업: 아래에서 위로 올라가는 방식으로 상향식이라고 불린다.
다이나믹 프로그래밍은 동적 계획법이라고도 불린다.
일반적으로 프로그래밍 분야에서 동적(Dynamic)이란 어떤 의미를 가질까?
- 자료구조에서 동적 할당(Dynamic Allocation)은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미한다.
- 반면에
다이나믹 프로그래밍에서다이나믹은 별다는 의미 없이 사용된 단어이다.
다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다.
최적 부분 구조(Optimal Substructure)- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
중복되는 부분 문제(Overlapping Subproblem)- 동일한 작은 문제를 반복적으로 해결해야 한다.
대표적인 다이나믹 프로그래밍으로 해결할 수 있는 문제로 ‘피보나치 수열’이 있다.
메모제이션
다이나믹 프로그래밍을 탑다운 방법으로 구현하는 기법으로 메모제이션(Memoization)이 있다. 이 기법은 한 번 계산한 결과를 메모리 공간에 메모하여 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다. 이렇게 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.
이 기법을 구현할 때는 재귀함수를 사용한다. 큰 문제를 해결하기 위해서 작은 문제들을 재귀적으로 호출하여 이 문제들을 모두 해결한 후 큰 문제에 대한 답을 얻는다.
DP 테이블
보텀업 방식은 전형적으로 다이나믹 프로그래밍에서 사용된다. 이 방식으로 구현하기 위해서 결과 저장용 리스트를 만들에 문제를 해결하는데 이 리스트를 DP 테이블이라고 부른다.
메모이제이션은 다이나믹 프로그래밍에서만 사용되는 개념은 아니다. 한 번 계산된 결과를 담아 놓고 다이나믹 프로그래밍을 위해 활용되지 않아도 메모이제이션을 사용했다고 말할 수 있다.
다이나믹 프로그래밍 vs 분할 정복
다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황
다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다. 다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복되지만, 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.