[알고리즘] 동적 프로그래밍

동적 계획법

동적 프로그래밍(dynamic programming)(동적 계획법)이란 복잡한 문제를 여러개의 간단한 하위 문제(subproblem)들로 분류하고 단순화하여 해결하는 방법이다. 문제를 더 작은 하위 문제로 나누고, 이 하위 문제를 해결한 결과를 이용해서 더 큰 문제를 해결한다.

해결하려는 문제가 최적 하위 구조(optimal substructure)와 중복되는 하위 문제(overlapping subproblem)를 갖고 있다면, 동적 프로그래밍으로 해결할 수 있다. 최적 하위 구조란 답을 구하기 위해 수행했던 계산을 반복해야 하는 문제의 구조를 말한다.

동적 프로그래밍을 사용하려면 먼저 최적 하위 구조가 있는지 확인해야 한다.

동적 프로그래밍의 전제조건과 제한

1. 최적 하위 구조 (optimal substructure): 문제의 최적 해답이 문제의 하위 문제들의 최적 해답으로부터 구성되면 그 문제를 최적 하위 구조라고 할 수 있다.
2. 중복되는 하위 문제 (overlapping subproblems): 문제가 하위 문제로 쪼개질 수 있고 이 하위 문제들이 여러번 재사용되는 경우, 또는 문제를 해결하는 과정에서 새로운 하위 문제를 생성하는 것보다 재귀 알고리즘이 동일한 하위 문제를 해결하는 경우 이 문제를 중첩 하위 문제라고 할 수 있다.

위 두 조건을 만족한다면 분할 정복 문제는 동적 프로그래밍으로 해결할 수 있다. 문제에 어떤 전제조건과 제한이 있을 경우 동적 프로그래밍을 문제에 적용할 수 있으며 이 경우 동적 계획법은 메모이제이션(memoization)과 타뷸레이션(tabulation)(도표 작성) 기법을 가지고 분할 정복 접근 방법을 확장한다.

동적 프로그래밍은 하위 문제를 풀고 결과를 저장한 후, 다음 하위 문제(중복되는 하위 문제)를 푸는 과정에서 저장된 결과를 사용한다. 즉, 동적 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

동적 프로그래밍은 각 하위 문제들이 서로 관계가 없을 때, 즉 서로 의존하지 않는 경우에만 사용할 수 있다.

분할 정복 알고리즘과 동적 프로그래밍

분할 정복 알고리즘과 동적 계획법 모두 문제를 재귀적으로 하위 문제로 분류하여 해결하는 점에서 동일하다. 동적 프로그래밍은 분할 정복 알고리즘의 확장이라고 볼 수 있다.

하위 문제들이 서로 겹치지 않으면 분할 정복 알고리즘, 하위 문제들이 서로 겹쳐서 동일한 하위 문제를 여러 번 해결하는 경우 동적 프로그래밍에 해당한다. 즉, 동적 프로그래밍은 문제들이 서로 영향을 미친다.

분할 정복 알고리즘을 사용하는 퀵 정렬에서 설정된 기준 원소(pivot)에 대한 문제는 다시 해결하지 않는다. 반면 동적 프로그래밍에서는 한 번 해결했던 문제를 다시 해결한다. 따라서 이미 해결된 하위 문제에 대한 답을 저장해 놓고, 동일한 문제에 대해 다시 해결할 필요 없이 이미 해결된 문제의 답을 반환하면 되며 이를 위해 메모이제이션 기법이 사용된다.

재귀 함수를 사용하는 경우 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야하므로 오버헤드가 발생할 수 있다. 따라서 재귀 함수 대신에 반복문을 사용하면 오버헤드를 줄일 수 있다. 일반적으로 반복문을 이용한 동적 프로그래밍의 성능이 더 좋다.

메모이제이션과 타뷸레이션

메모이제이션(memoization)이란 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거함으로써 프로그램의 실행 속도를 빠르게 하는 기법이다. 즉, 계산한 값을 캐시에 저장하고 이미 캐시된 값을 불러옴으로써 계산 횟수를 줄인다. 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 사용함으로써 중복 계산을 방지할 수 있게 하는 기법이다. 메모이제이션은 동적 프로그래밍의 핵심이 되는 기술로써 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄인다.

타뷸레이션(tabulation)은 메모이제이션과 비슷하지만, 값을 미리 계산해둔다는 점에서 차이가 있다. 즉, 메모이제이션이 결과가 필요할 때 계산(lazy-evaluation)한다면 타뷸레이션은 필요하지 않은 값도 미리 계산(eager-evaluation)둔다. 따라서 타뷸레이션은 초기화 오버헤드가 있지만 일단 계산해둔 값은 시간 복잡도가 상수 시간(O(1))이 된다.

계산한 결과를 리스트에 저장함으로써 메모이제이션을 구현할 수 있다. 동적 프로그래밍을 재귀적으로 수행하다가 동일한 정보가 필요할 때는 미리 구한 계산 결과를 그대로 리스트에서 가져오면 된다.

탑다운과 바텀업

재귀 함수를 이용하여 동적 프로그래밍 구현 코드를 작성하는 방법을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(top-down) 방식이라고 한다.

반면 단순히 반복문을 사용하여 소스 코드를 작성하는 경우, 작은 문제부터 차근차근 답을 도출한다고 하여 바텀업(bottom-up) 방식이라고 한다. 바텀업 방식에서 사용되는 결과 저장용 리스트를 ‘DP 테이블’이라고 부른다.

탑다운 방식은 ‘하향식’이라고도 하며, 바텀업 방식은 ‘상향식’이라고도 한다. 메모이제이션은 탑다운 접근 방식을 사용하며 타뷸레이션은 바텀업 접근 방식을 사용한다.

동적 프로그래밍의 전형적인 형태는 바텀업 방식이다. 하지만 탑다운 방식과 바텀업 방식 모두 동적 프로그래밍을 구현하는 데 사용할 수 있다.

메모이제이션이 동적 프로그래밍에 국한된 개념은 아니다. 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하므로 동적 프로그래밍과는 별도의 개념이다. 즉, 동적 프로그래밍에 메모이제이션 기법이 사용될 수 있다고 말할 수 있다. 메모이제이션은 때에 따라 리스트와는 다른 자료형(예를 들어 해시 맵 등)을 이용할 수도 있다.

문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 동적 프로그래밍을 적용할 수 있는지 확인하기 위해 해결하고자 하는 하위 문제들의 중복 여부를 확인하면 된다. 단순히 재귀 함수로 비효율적인 프로그램을 작성한 뒤에(탑다운 방식) 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면(즉, 메모이제이션을 적용할 수 있으면) 코드를 개선하는 것도 좋은 방법이다.

시스템 상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문에 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 바텀업 방식으로 구현하는 것이 좋다.

최장 공통 부분 문자열

최장 공통 부분 문자열(longest common substring)이란 두 문자열이 공통으로 갖는 동일한 순서의 문자열 중 가장 긴 부분 문자열을 말한다. 두 문자열의 최장 공통 부분 문자열은 동적 프로그래밍을 통해 구할 수 있다. 여기서 하위 문제는 두 문자열의 문자를 서로 비교하는 것이다. 모든 문자에 대해 비교를 연속적으로 수행하고 값을 기록한다. 첫 문자부터 마지막 문자까지 비교를 수행한 후 가장 큰 값을 기준으로 공통 문자열의 길이가 가장 긴 문자열을 찾을 수 있다.

최장 공통 부분열(longest common subsequence)이란 두 문자열에서 순서가 바뀌지 않고 공통으로 들어간 문자의 개수가 최대인 부분 문자열을 말한다.