크래프톤 정글 주제별 탐구 -다이나믹 프로그래밍-

정의

동적 계획법(Dynamic Programming, 이하 DP)이란, 최적화 이론을 기반으로 특정 범위까지의 값을 구하기 위해 이전에 구한 값을 이용하여 효율적으로 계산하는 알고리즘 설계 기법이다. 실질적으로, DP는 DFS나 BFS처럼 특정 방식으로 구현한다기보다는, 문제를 해결하는 하나의 방식과 유사하다. DP는 기본적으로 분할 정복 알고리즘과 메모이제이션의 융합과 비슷하다. 그렇기에, 특정 방식을 외운다기 보다는, 직관적인 해결책이 아닌 또 다른 방식의 효율적인 해결책을 생각하게 만든다.

특징

DP의 경우에는 이전의 계산을 저장해두는 공간이 필요하며, 이 공간에서 값을 불러오는 것을 통해 반복적인 계산 혹은 중복되는 계산을 제거한다. 이를 통해 구할 수 있는 대표적인 문제들은 다음과 같다.

• 피보나치 수열
• 3항 이상의 재귀 수열
• 0-1 배낭 문제(0-1 Knapsack Problem): 견딜 수 있는 무게가 제한된 배낭에 가장 많은 가치의 물건을 넣기. 모든 무게를 정수로 볼 수 있다면, 배낭의 최대 무게 W일 때 O(W)로 구할 수 있다. 그게 아닌 경우라면 NP-hard이므로 근사 알고리즘을 써야 한다. 비슷한 것으로 Rational Knapsack Problem이 존재하는데, 이는 보통 그리디 알고리즘으로 사용된다. 0-1 Knapsack과 다른 점은 단순히 물건을 넣느냐 빼느냐가 아니라, 잘라서 (일부분만) 넣을 수 있게 하는 것이다.
• 가장 긴 증가 수열 문제(LIS Problem): 아무 수열이나 주고, 순서를 바꾸지 않은 상태로 뽑아서 만들 수 있는 가장 긴 증가수열의 길이 구하기. O(N²)이며, 이진 탐색을 사용할 줄 안다면 O(NlogN)으로도 줄일 수 있다.
• 연쇄 행렬 곱셈 문제: 주어진 연쇄행렬들의 곱셈을 각 원소의 곱셈 횟수를 최소로 할 수 있는 행렬곱셈의 순서를 찾는 최적화 문제이다. 동적 계획법과 메모이제이션을 적용할 수 있는 대표적인 알고리즘들 중 하나이다.
• 그래프 상의 최단거리 문제 - 벨먼-포드 알고리즘, 플로이드-워셜 알고리즘: 점 개수가 V일 때 O(V³)으로 구할 수 있다. Floyd-Warshall은 모든 출발점과 도착점에 대해 최단거리를 구할 수 있고, Bellman-Ford는 거리 합이 음수인 사이클이 있을 때에 대해서도 구할 수 있다. (다익스트라 알고리즘은 일종의 BFS이다.)

나무위키에 있는 대표 문제들을 가져와봤다. 지난주차에 진행한 플로이드-워셜 같은 경우에도 이러한 DP의 해결책으로 볼 수 있다.

단점

DP의 경우, 이런식으로 이전에 진행한 계산을 저장할 공간을 할당하기 때문에 기본적으로 메모리 사용량이 많을 수 있다.

알고리즘 문제