[코딩테스트 / 알고리즘] 다이나믹 프로그래밍(Dynamic)
다이나믹 프로그래밍
다이나믹 프로그래밍(Dynamic Programming, DP) 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘으로 동적계획법이라고도 한다. 즉 큰 문제를 작게 나누고, 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
DP 푸는 과정
- 테이블 정의하기
- 점화식 찾기
- 초기값 정의하기
다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제는 피보나치 수열이다. 피보나치 수열을 재귀적으로 풀면 엄청난 시간복잡도와 중복된 연산으로 인한 비효율이 발생한다. 하지만 다이나믹 프로그래밍으로 푼다면 연산 속도와 메모리 공간을 최대한으로 활용하면서 효과적으로 문제를 해결할 수 있다.
구현방식
다이나믹 프로그래밍은 복잡한 문제를 간단한 여러 개의 하위 문제(sub-problem)로 나누어 푸는 방법을 말한다.
DP 에는 두 가지 구현 방식이 존재한다.
- top-down : 여러 개의 하위 문제(sub-problem) 나눴을시에 하위 문제를 결합하여 최종적으로 최적해를 구한다. 같은 하위 문제를 가지고 있는 경우가 존재한다. 그 최적해를 저장해서 사용하는 경우 하위 문제수가 기하급수적으로 증가할 때 유용하다. 위 방법을 memoization 이라고 한다.
- bottom-up : top-down 방식과는 하위 문제들로 상위 문제의 최적해를 구한다.
접근 방식
접근방법
- 모든 답을 만들어보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.
- 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 저수만을 반환하도록 부분 문제 정의를 변경한다.
- 재귀 호출의 입력 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다.
- 입력이 배열이거나 문자열인 경우 가능하다면 적절한 변환을 통해 메모이제이션할 수 있도록 조정한다.
- 메모이제이션을 적용한다.
메모이제이션
메모이제이션 기법은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱이라고도 한다.
실제 메모이제이션을 구현하는 방법은 한 번 구한 정보를 리스트에 저장하는 것이다. 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요하면 이미 구한 정답을 그대로 리스트에서 가져오면 된다.