[자료 구조/알고리즘] 동적 프로그래밍
동적 프로그래밍
동적 프로그래밍(dynamic programming)(또는 동적 계획법)이란 복잡한 문제를 여러개의 간단한 하위 문제(subproblem)들로 분류하고 단순화하여 해결하는 방법이다. 문제를 더 작은 하위 문제로 나누고, 이 하위 문제를 해결한 결과를 이용해서 더 큰 문제를 해결한다.
해결하려는 문제가 최적 하위 구조(optimal substructure)와 중복되는 하위 문제(overlapping subproblem)를 갖고 있다면, 동적 프로그래밍으로 해결할 수 있다.
동적 프로그래밍의 전제 조건과 제한
동적 프로그래밍으로 문제를 해결하기 위해서는 문제가 다음 두 조건을 만족해야 한다.
- 문제는 최적 하위 구조를 갖는다.
- 문제를 해결하는 과정은 중복되는 하위 문제를 여러번 다시 해결하는 과정을 포함한다.
최적 하위 구조와 중복되는 하위 문제의 정의는 다음과 같다.
- 최적 하위 구조 (optimal substructure): 문제의 최적 해답이 문제의 하위 문제들의 최적 해답으로 구성되면 그 문제를 최적 하위 구조를 갖는다라고 할 수 있다. 최적 하위 구조는 그리디(greedy) 알고리즘에서도 사용된다. 최적 하위 구조의 대표적인 예로는 최단 경로 탐색(shortest path search)이 있다. 목적지 A, B, C가 있을 때 A에서부터 B를 거쳐 C까지의 최단 경로를 찾는 문제는 A에서부터 B까지의 최단 경로를 구하고, B에서부터 C까지의 최단 경로를 구하는 하위 문제들의 최적 해결 과정을 포함한다. 단, B를 거치지 않고 A에서부터 C까지 바로 연결된 경로가 존재하는 경우 이 문제는 최적 하위 구조를 갖는 문제가 아니며 동적 프로그래밍이나 그리디 알고리즘으로 해결할 수 없다.
- 중복되는(겹치는) 하위 문제 (overlapping subproblems): 문제가 하위 문제로 쪼개질 수 있고 문제를 해결하는 과정에서 동일한 하위 문제들을 여러번 다시 해결해야 하는 경우 해당 문제를 해결하는 과정은 중복되는 하위 문제 해결 과정을 포함한다. 재귀 함수 호출이나 반복문을 통해 동일한 하위 문제를 해결한다. 이때 중복되는 하위 문제를 여러 번 다시 해결하는 대신 이미 해결한 문제의 답을 재사용한다. 중복되는 하위 문제의 대표적인 예로는 피보나치 수열(Fibonacci sequence)이 있다.
위 두 조건을 만족한다면 문제는 동적 프로그래밍으로 해결할 수 있다. 동적 프로그래밍은 하위 문제를 해결하고 결과를 저장한 후, 중복되는 하위 문제를 해결하는 과정에서 저장된 결과를 사용한다. 즉, 동적 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.
분할 정복 알고리즘과 동적 프로그래밍
분할 정복 알고리즘과 동적 프로그래밍 모두 문제를 재귀적으로 하위 문제로 분류하여 해결하는 점에서 유사하지만 몇가지 차이가 있다.
하위 문제들이 서로 중복되지 않으면 분할 정복 알고리즘, 하위 문제들이 서로 중복되어 동일한 하위 문제를 여러 번 해결하는 경우 동적 프로그래밍으로 해결할 수 있다. 이때 하위 문제의 결과를 저장하고 중복되는 하위 문제의 경우 저장된 결과를 사용하여 실행 시간을 줄인다. 동적 프로그래밍은 하위 문제들이 서로 영향을 미치는 반면 분할 정복 알고리즘은 하위 문제들이 서로 관계가 없다(서로 의존하지 않는다).
분할 정복 알고리즘을 사용하는 퀵 정렬에서 설정된 기준 원소(pivot)에 대한 문제는 다시 해결하지 않는다. 하위 문제들의 해결 결과를 조합하여 문제의 해결에 사용할 뿐이다. 반면 동적 프로그래밍에서는 한 번 해결했던 문제를 다시 해결한다. 이미 해결된 하위 문제에 대한 답을 저장해 놓고, 동일한 문제에 대해 다시 해결할 필요 없이 이미 해결된 문제의 답을 반환하면 되며 이를 위해 메모이제이션 또는 타뷸레이션 기법이 사용된다.
재귀 함수를 사용하는 경우 함수의 호출 결과는 메모리 상에 적재되므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신에 반복문을 사용하면 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 알고리즘의 성능이 더 좋다.
하향식과 상향식, 메모이제이션과 타뷸레이션
동적 프로그래밍은 중복 하위 문제를 포함한다. 따라서 동일한 하위 문제를 여러번 해결해야 한다. 프로그램이 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 생략함으로써 프로그램의 실행 속도를 빠르게 할 수 있다. 이러한 기법을 캐싱(caching)이라고 한다. 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 사용하여 중복 계산을 방지할 수 있다. 이 방법은 동적 프로그래밍의 핵심이며 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄인다. 동적 프로그래밍에서 하위 문제의 해결 결과를 저장하기 위한 임시 자료 구조를 DP 테이블(dp table)이라고 한다.
계산한 결과를 배열, 리스트, 연관 배열(associative array) 자료 구조 등에 저장함으로써 DP 테이블을 구현할 수 있다. 배열이나 리스트의 경우 인덱싱(indexing)을, 해시 테이블(hash table)과 같은 연관 배열의 경우 해싱(hashing)을 사용한다. 미리 계산해둔 값을 조회하는 연산의 시간 복잡도는 상수 시간인 O(1)이다.
동적 프로그래밍을 구현하는 방법은 크게 두 가지가 있다. 두 방법 모두 동일한 문제는 다시 해결하지 않고 저장된 답을 사용한다.
- 하향식(top-down) 또는 메모이제이션(memoization): 재귀 함수를 사용하여 문제를 해결한다. 전체 문제를 해결하기 위해 문제를 하위 문제로 작게 만들어가면서 하위 문제를 이미 해결했는지 먼저 확인한 후 이미 해결된 문제이면 답을 재사용하며 전체 문제를 해결한다. 문제를 하위 문제로 작게 만드는 반복 과정에서, 동일한 하위 문제가 생성될 수 있다.
- 상향식(bottom-up) 또는 타뷸레이션(tabulation): 반복문을 사용하여 문제를 해결한다. 전체 문제를 해결하기 위해 하위 문제를 크게 만들어가면서 하위 문제를 이미 해결했는지 먼저 확인한 후 이미 해결된 문제이면 답을 재사용하며 전체 문제를 해결한다. 더 큰 문제를 해결하는 반복 과정에서, 동일한 하위 문제를 다시 해결할 수 있다.
하향식 해결 방법은 다음과 같다.
- 재귀 함수를 정의한다. 재귀 함수는 전체 문제 또는 하위 문제를 해결하고 답을 반환하는 함수이다. 재귀 함수에서 문제는 하위 문제로 쪼개진다.
- 재귀 함수의 기본 단계를 해결한다. 기본 단계는 가장 작은 하위 문제이다. 결과를 DP 테이블에 저장한다.
- 중복 하위 문제를 해결한다. 미리 계산한 결과를 반환하는 조건을 작성한다. 미리 계산한 결과가 있으면 해당 값을 반환한다.
- 최적 하위 구조에 따라 하위 문제를 조합하여 상위 문제를 해결한다. 하위 문제를 조합하여 상위 문제를 해결하는 방법은 최적 하위 구조에 따른다. 재귀 함수에서 하위 문제를 해결하기 위해 함수를 재귀적으로 호출하고 하위 문제의 해결 결과를 사용하여 문제를 해결한 결과를 DP 테이블에 저장 및 반환한다.
- 재귀 함수를 호출한다. 재귀 함수는 가장 큰 문제를 인자로 받는다.
상향식 해결 방법은 다음과 같다.
- 가장 작은 하위 문제를 먼저 해결한다.
- 하위 문제를 조합하여 상위 문제를 해결한다. 해결한 상위 문제는 또다른 상위 문제를 해결하는데 사용된다. 하위 문제의 조합 결과가 전체 문제를 해결하는데 사용될 때까지 위 과정을 반복한다. 이 과정에서 중복 하위 문제를 해결한다. 미리 계산한 결과가 있으면 해당 값을 조회하여 재사용한다.
문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 동적 프로그래밍을 적용할 수 있는지 확인하기 위해 해결하고자 하는 문제들이 하위 문제로 구성되어 있는지, 하위 문제들을 중복으로 해결해야 하는지 확인하면 된다. 하향식 방식으로 재귀 함수를 사용하여 문제를 해결한 뒤에 상향식 방식으로 반복문을 사용하여 코드를 개선하는 것도 좋은 방법이다.
문제에 따라 DP 테이블이 필요하지 않을 수 있다. DP 테이블은 문제에 대한 답을 키와 값으로 저장해 놓는 자료 구조로 사용되지만 이를 사용하는 대신 이전의 하위 문제를 반복적으로 해결하면서 얻은 현재까지의 답과 새로운 하위 문제의 답을 비교하고 전체 답을 갱신하는 방법으로 문제를 해결할 수 있다.
시스템 상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문에 함수 호출의 깊이가 매우 깊다면 런타임에 스택 오버플로우(stack overflow) 예외가 발생할 수 있다. 가능하다면 재귀 함수를 사용하는 하향식 방식보다는 반복문을 사용하는 상향식 방식으로 구현하는 것이 좋다.
피보나치 수열
피보나치 수열(Fibonacci numbers)이란 첫 번째와 두 번째 수가 1이고, 다음의 모든 수는 바로 앞의 두 수의 합인 수열을 말한다.
피보나치 수열의 n번째 수를 구하는 문제는 동적 프로그래밍으로 해결할 수 있다. 최적 하위 구조와 중복 하위 문제는 다음과 같다.
- 최적 하위 구조: n번째 수를 구하는 문제는 n-2번째 수를 구하는 문제와 n-1번째 수를 구하는 하위 문제를 해결하고 그 결과를 조합하여 해결할 수 있다. 따라서 n-1번째 수를 구하는 문제가 최적 하위 구조이다. 피보나치 수열 문제는 최적 하위 구조를 포함한다.
- 중복 하위 문제: 문제를 해결하는 과정에서 n-1번째 수를 구하는 문제를 여러 번 해결할 수 있다. 예를 들어, n번째 수를 구하는 것은 n-2번째 수와 n-1번째 수를 구하는 과정을 포함하며, n-1번째 수를 구하는 것은 n-3번째 수와 n-2번째 수를 구하는 과정을 포함한다. 이때 n-2번째 수를 구하는 문제를 중복으로 해결한다. 피보나치 수열 문제는 중복 하위 문제 해결 과정을 포함한다.
하위 문제는 다음과 같이 해결한다.
- n번째 수는 n-2번째 수와 n-1번째 수의 합이다.
하향식 해결 방법은 다음과 같다. 수를 감소해 나가면서 수열을 계산한다.
- 재귀 함수를 정의한다. 재귀 함수는 n번째 수를 반환하는 함수이다.
- 재귀 함수의 기본 단계를 해결한다. 기본 단계는 0번째 수와 1번째 수이다. 결과를 DP 테이블에 저장한다.
- 중복 하위 문제를 해결한다. 미리 계산한 결과를 반환하는 조건을 작성한다. 미리 계산한 결과가 있으면 해당 값을 반환한다.
- 최적 하위 구조에 따라 하위 문제를 조합하여 상위 문제를 해결한다. 하위 문제를 해결하기 위해 n-2번째 수와 n-1번째 수를 인자로 받는 함수를 재귀적으로 호출하고 하위 문제의 해결 결과를 사용하여 문제를 해결한 결과를 DP 테이블에 저장 및 반환한다.
- 재귀 함수를 호출한다. 재귀 함수의 인자는 n이다.
상향식 해결 방법은 다음과 같다. 수를 증가해 나가면서 수열을 계산한다.
- 가장 작은 하위 문제를 먼저 해결한다. 0번째 수와 1번째 수를 합하여 2번째 수를 구한다.
- 하위 문제를 조합하여 상위 문제를 해결한다. n번째 수까지 차례대로 n-2번째 수와 n-1번째 수를 합하여 n번째 수를 구한다. 위 과정을 반복한다. 이 과정에서 중복 하위 문제를 해결한다. 미리 계산한 결과가 있으면 해당 값을 조회하여 재사용한다.
최장 공통 부분 문자열과 최장 공통 부분열 구하기
최장 공통 부분 문자열(longest common substring)이란 두 문자열이 공통으로 갖는 동일한 순서의(연속적) 문자열 중 가장 긴 부분 문자열을 말한다. 최장 공통 부분 문자열은 동적 프로그래밍을 통해 구할 수 있다. 예를 들어, 문자열 ABABC, BABCA, ABCBA의 최장 공통 부분 문자열은 ABC이다. 최장 공통 부분 문자열을 구하는 문제는 동적 프로그래밍으로 해결할 수 있다.
최장 공통 부분 문자열을 구하는 문제에서 최대화하고자 하는 값은 두 문자열이 공통으로 가지는 가장 긴 부분 문자열의 길이이며, 하위 문제는 두 문자열의 부분 문자열을 서로 비교하는 것이다. 모든 문자에 대해 비교를 연속적으로 수행하고 값을 기록하면서 첫 문자부터 마지막 문자까지 비교를 수행한 후 가장 큰 값을 기준으로 공통 문자열의 길이가 가장 긴 문자열을 찾을 수 있다.
하위 문제는 다음과 같이 해결한다.
- 2차원 배열의 DP 테이블을 사용하여 각 상태에서 값을 구한다. DP 테이블의 행은 문자열1의 문자, 열은 문자열2의 문자이며 행과 열에 대한 값은 최장 공통 부분 문자열의 길이이다. 배열을 순회할 때마다 최장 공통 부분 문자열의 길이를 갱신해 나간다. 행과 열에서 최장 공통 부분 문자열의 길이는 다음과 같이 계산한다.
- 문자가 동일하지 않으면 공통 문자열이 없으므로 0을 저장한다.
- 문자가 동일하면 (행 - 1, 열 - 1)의 값에 1을 더한 값을 저장한다.
- 모든 행과 열에 대해 위 과정을 반복한 후 2차원 배열에서 가장 큰 값을 찾는다. 최대값은 최장 공통 부분 문자열의 길이를 의미한다. 위 과정에서 문자가 동일할 경우 해당 문자를 누적해서 저장한 문자열은 최장 공통 부분 문자열이 된다.
최장 공통 부분열(longest common subsequence)이란 두 문자열에서 순서가 바뀌지 않고 공통으로 들어간(비연속적) 문자의 개수가 최대인 부분 문자열을 말한다. 부분 문자열(substring)은 문자들이 서로 연결되어 있는 연속적인 것을 말하지만 부분열(subsequence)은 문자들이 서로 연결되어 있지 않더라도 순서가 동일한지를 판별한다. 예를 들어, 문자열 ABCD과 ACBAD의 공통 부분열은 AB, AC, AD, BD, CD, ABD, ACD이며, 최장 공통 부분열은 ABD, ACD이다.
하위 문제는 다음과 같이 해결한다.
- 2차원 배열의 DP 테이블을 사용하여 각 상태에서 값을 구한다. DP 테이블의 행은 문자열1의 문자, 열은 문자열2의 문자이며 행과 열에 대한 값은 최장 공통 부분열의 길이이다. 배열을 순회할 때마다 최장 공통 부분열의 길이를 갱신해 나간다. 행과 열에서 최장 공통 부분열의 길이는 다음과 같이 계산한다.
- 문자가 동일하지 않으면 (행 -1, 열)의 값과 (행, 열 -1)의 값 중 더 큰 값을 저장한다.
- 문자가 동일하면 (행 - 1, 열 - 1)의 값에 1을 더한 값을 저장한다.
- 모든 행과 열에 대해 위 과정을 반복한 후 2차원 배열에서 가장 큰 값을 찾는다. 최대값은 최장 공통 부분열의 길이를 의미한다. 위 과정에서 문자가 동일할 경우 해당 문자를 누적해서 저장한 문자열은 최장 공통 부분열이 된다.
최대 하위 배열 문제
최대 하위 배열 문제(maximum subarray problem)란 배열에서 합이 최대가 되는 연속된 값으로 구성된 하위 배열을 찾는 문제이다. 이 문제를 브루트 포스로 해결할 경우 전체 배열과 하위 배열을 반복하는 이중 반복을 수행하며 이 경우 시간 복잡도는 O(N2)이다. 이 문제는 동적 프로그래밍으로 해결하여 시간 복잡도를 개선할 수 있다.
최대 하위 배열 문제에서 최적 하위 구조와 중복 하위 문제는 다음과 같다.
- 최적 하위 구조: 길이 n의 배열의 합을 최대화하는 문제는 길이 n-1의 배열의 합을 최대화하는 하위 문제를 해결하고 하위 문제의 해결 결과와 길이 n의 배열의 마지막 원소와의 합을 최대화하는 문제를 해결하는 것이다. 최대 하위 배열 문제는 최적 하위 구조를 포함한다.
- 중복 하위 문제: 문제를 해결하는 과정에서 길이 n-1의 배열의 최대합을 구하는 문제를 여러 번 해결할 수 있다. 최대 하위 배열 문제는 중복 하위 문제 해결 과정을 포함한다.
하위 문제는 다음과 같이 해결한다.
- 길이가 n인 배열의 최대합은 길이가 n-1인 배열의 최대합을 이용한다.
- 길이가 n-1인 배열의 최대합과 마지막 원소를 사용하여 최대합을 계산한다. 다음 경우에 따라 처리한다.
- 길이가 n-1인 배열의 최대합이 양수이고 마지막 원소가 양수이면 더한 값을 최대합으로 갱신한다.
- 길이가 n-1인 배열의 최대합이 양수이고 마지막 원소가 음수이면 더한 값을 최대합으로 갱신한다.
- 길이가 n-1인 배열의 최대합이 음수이고 마지막 원소가 양수이면 더하지 않는다. 마지막 원소의 값을 최대합으로 갱신한다.
- 길이가 n-1인 배열의 최대합이 음수이고 마지막 원소가 음수이면 더하지 않는다. n-1인 배열의 최대합이 현재까지 구한 최대합이며 그대로 유지한다.
하향식 해결 방법은 다음과 같다. 배열의 크기를 1씩 감소해 나가면서 해당 배열의 최대합을 계산한다.
- 재귀 함수를 정의한다. 재귀 함수는 주어진 크기의 배열의 최대합을 구하는 함수이다.
- 재귀 함수의 기본 단계를 해결한다. 기본 단계는 원소가 1개인 배열이다.
- 중복 하위 문제를 해결한다. 미리 계산한 결과를 반환하는 조건을 작성한다.
- 최적 하위 구조에 따라 하위 문제를 조합하여 상위 문제를 해결한다. 하위 문제를 해결하기 위해 길이가 n-1인 배열을 인자로 받는 함수를 재귀적으로 호출하고 하위 문제의 해결 결과를 사용하여 문제를 해결한 결과를 DP 테이블에 저장 및 반환한다.
- 재귀 함수를 호출한다. 재귀 함수의 인자는 길이가 n인 배열이다.
상향식 해결 방법은 다음과 같다. 배열의 크기를 1씩 증가해 나가면서 해당 배열의 최대합을 계산한다.
- 가장 작은 하위 문제를 먼저 해결한다. 원소가 1개인 배열의 최대합을 구한다.
- 하위 문제를 조합하여 상위 문제를 해결한다. 가장 큰 최대합을 찾는 문제이므로 반복할 때마다 최대합을 비교하여 갱신한다. 미리 계산한 결과가 있으면 해당 값을 조회하여 재사용한다.
최대 하위 배열 문제는 전체 배열에서 최대합을 찾는 문제이지만 하위 배열의 최대합을 반복적으로 계산해 나가면서 이를 최대화시키는 방법으로 문제 해결 방법을 최적화할 수 있다. 이러한 알고리즘을 카데인 알고리즘(Kadane’s algorithm)이라고 한다. 카데인 알고리즘의 시간 복잡도는 O(N)이다.
배낭 채우기 문제
배낭 채우기 문제(knapsack problem)란 정해진 크기의 배낭에 가장 비싼(expensive) 물건을 채우는 문제이다. 물건들의 무게와 가격을 기반으로 물건의 총 가치를 최대로 높이려면 어떤 물건들을 조합하여 배낭에 넣어야 하는지 해결하는 문제이다. 이 문제는 유한한 객체 집합에서 최적의 객체 조합을 찾는 조합 최적화(combinatorial optimization) 문제 중 하나이다. 이 문제는 그리디 알고리즘으로는 해결하기가 어렵다.
배낭 채우기 문제에서 최적 하위 구조와 중복 하위 문제는 다음과 같다.
- 최적 하위 구조: 전체 배낭의 크기를 채우는 문제는 더 작은 배낭을 채우는 문제를 풀고 그 결과를 조합하여 해결할 수 있다. 배낭 채우기 문제는 최적 하위 구조를 포함한다.
- 중복 하위 문제: 문제를 해결하는 과정에서 더 작은 배낭을 채우는 문제를 여러 번 해결할 수 있다. 배낭 채우기 문제는 중복 하위 문제 해결 과정을 포함한다.
하위 문제는 다음과 같이 해결한다.
- 크기가 n인 배낭 채우기 문제는 크기가 n-1인 배낭 채우기 문제를 이용한다. 크기가 n-1인 배낭의 최대 가치와 현재 물건의 가치를 비교하여 최대화한다.
- 2차원 배열의 DP 테이블을 사용하여 각 상태에서 물건의 최대 가치를 구한다. DP 테이블의 행은 물건의 종류, 열은 배낭의 크기이며 행과 열에 대한 값은 해당 배낭의 크기에서 최대로 넣을 수 있는 물건의 가치의 합이다. 배열을 순회할 때마다 최대 가치를 갱신해 나간다. 행과 열에서 물건의 가치는 다음과 같이 계산한다.
- 첫 번째 행에서 해당 행의 물건만 넣을 수 있으며, 해당 열의 크기의 배낭의 해당 행의 물건을 넣을 수 있는지 없는지 판별한다. 물건을 넣을 수 있으면 최대 가치를 갱신한다.
- 두 번째 행부터 해당 행의 물건만 넣을 수 있으며, 해당 열의 크기의 배낭의 해당 행의 물건을 넣을 수 있는지 없는지 판별한다.
- 배낭에 물건을 넣을 수 있고 배낭에 여분의 공간이 없는 경우: 해당 크기의 배낭에서 지금까지의 최대 가치(행 - 1, 열)의 값)와 비교한 후 더 큰 가치의 물건으로 최대 가치를 갱신한다.
- 배낭에 물건을 넣을 수 있고 배낭에 여분의 공간이 있는 경우: 해당 크기의 배낭에서 지금까지의 최대 가치와 비교한 후 더 큰 가치의 물건으로 최대 가치를 갱신한다. 그리고 여분의 공간에 대한 최대 가치(미리 계산한 값)를 DP 테이블에서 조회하여 더한다.
- 모든 행과 열에 대해 위 과정을 반복한 후 2차원 배열에서 가장 큰 값을 찾는다. 최대값은 해당 배낭에 넣을 수 있는 물건의 최대 가치이다.
상향식 해결 방법은 다음과 같다. 배낭의 크기를 1씩 증가해 나가면서 해당 크기의 배낭에 넣을 수 있는 물건들의 가치가 최대가 되도록 한다.
- 가장 작은 하위 문제를 먼저 해결한다. 배낭의 크기가 1인 경우 배낭에 넣을 수 있는 물건들의 가치의 최대값을 구한다.
- 하위 문제를 조합하여 상위 문제를 해결한다. 가장 큰 최대합을 찾는 문제이므로 반복할 때마다 최대합을 비교하여 갱신한다. 미리 계산한 결과가 있으면 해당 값을 조회하여 재사용한다.
Comments