동적 계획법

최적 부분 구조는 동적 계획법을 적용할 수 있는 문제가 가져야 하는 핵심 조건 중 하나이다. 이는 어떤 문제의 최적해(Optimal Solution)가 그 문제의 부분 문제(Subproblem)들의 최적해들로부터 효율적으로 구성될 수 있는 성질을 의미한다. 즉, 전체 문제를 해결하는 최선의 방법이, 그 문제를 이루는 작은 단위들의 최선의 해법을 결합함으로써 얻어질 수 있어야 한다.

예를 들어, 그래프에서 두 지점 간의 최단 경로를 찾는 문제는 최적 부분 구조를 가진 대표적인 사례이다. A 지점에서 C 지점까지의 최단 경로가 A->B->C라면, 이 경로는 A->B의 최단 경로와 B->C의 최단 경로로 구성된다. 만약 A->B 사이에 더 짧은 다른 경로가 존재한다면, 전체 A->C 경로도 더 짧아질 수 있으므로, 전체 최적해는 부분 경로의 최적해에 의존한다.

이러한 성질이 있기 때문에, 동적 계획법은 큰 문제를 작은 부분 문제로 나누고, 각 부분 문제의 최적해를 메모이제이션이나 타뷸레이션 기법을 통해 저장해 놓은 뒤, 이를 조합하여 전체 문제의 최적해를 구할 수 있다. 최적 부분 구조가 없다면, 부분 문제의 해를 저장해도 전체 문제를 푸는데 재사용할 수 없게 되어 동적 계획법의 효율성이 사라진다.

따라서, 어떤 문제에 동적 계획법을 적용하고자 할 때는 먼저 해당 문제가 최적 부분 구조를 만족하는지 분석하는 것이 첫 번째 단계가 된다. 이 조건과 함께 중복되는 부분 문제 조건이 충족될 때, 동적 계획법은 지수 시간의 복잡도를 가지는 문제를 다항 시간 내에 해결할 수 있는 강력한 도구가 된다.

중복되는 부분 문제는 동적 계획법을 적용할 수 있는 문제가 가져야 하는 두 가지 핵심 조건 중 하나이다. 이는 큰 문제를 해결하는 과정에서 동일한 작은 문제가 반복적으로 등장하는 특성을 의미한다. 예를 들어, 피보나치 수열을 재귀적으로 계산할 때 F(5)를 구하기 위해 F(3)은 여러 번 계산되며, 이러한 중복 계산은 입력 크기가 커질수록 기하급수적으로 증가한다.

동적 계획법은 이러한 비효율성을 해결하기 위해 각 부분 문제의 해답을 메모이제이션이나 테이블화 기법을 사용하여 저장한다. 한 번 계산된 결과는 배열이나 해시 테이블 같은 자료 구조에 기록해 두었다가, 동일한 부분 문제가 다시 필요할 때 저장된 값을 즉시 반환한다. 이 접근법은 불필요한 재계산을 제거하여 알고리즘의 실행 시간을 획기적으로 단축시킨다.

중복되는 부분 문제의 존재 여부는 동적 계획법의 적용 가능성을 판단하는 중요한 척도가 된다. 분할 정복법이 병렬적으로 독립된 부분 문제를 해결하는 데 적합하다면, 동적 계획법은 상호 의존적이고 겹치는 부분 문제를 효율적으로 푸는 데 강점을 보인다. 따라서 최단 경로 문제나 배낭 문제와 같이 특정 상태에 도달하기 위한 여러 경로나 선택지가 존재해 하위 계산이 반복되는 문제들에서 그 효과가 두드러진다.

상향식 동적 계획법은 하향식 동적 계획법과 함께 동적 계획법의 두 가지 주요 구현 방법 중 하나이다. 이 방법은 가장 작은 하위 문제부터 시작하여 그 해답을 차례차례 계산하고 저장해 나가며, 결국 최종 목표인 전체 문제의 해답에 도달하는 방식으로 작동한다. 즉, 기본적인 경우의 해답을 먼저 구하고, 이를 바탕으로 점점 더 큰 문제의 해답을 구축해 올라간다.

이 접근법은 일반적으로 반복문을 사용하여 구현되며, 계산 결과를 저장하기 위해 배열이나 표를 활용한다. 예를 들어, 피보나치 수열을 구할 때, F(0)과 F(1)의 값을 먼저 배열에 저장한 후, F(2)부터는 이전에 저장된 두 값을 참조하여 순차적으로 계산해 나가는 방식이 상향식 방법의 전형적인 예이다. 이 과정에서 모든 하위 문제는 정확히 한 번만 계산된다.

상향식 방법의 주요 장점은 함수 호출 오버헤드가 발생하지 않으며, 재귀의 깊이 제한에 영향을 받지 않는다는 점이다. 또한 모든 하위 문제의 해답을 명시적으로 표에 저장하기 때문에, 전체 계산 과정과 중간 결과를 직관적으로 파악하기 쉽다. 그러나 최종 해답에 도달하기 위해 불필요할 수도 있는 모든 하위 문제를 반드시 계산해야 한다는 단점이 있을 수 있다.

이 방법은 배낭 문제, 최단 경로 문제, 그리고 행렬 곱셈 순서 최적화와 같은 문제를 해결하는 데 널리 사용된다. 상향식 접근법은 문제의 구조를 명확히 이해하고, 하위 문제 간의 의존 관계를 정의할 수 있을 때 효과적으로 적용할 수 있다.

하향식 동적 계획법은 메모이제이션이라는 기법을 사용하여 문제를 해결한다. 이 방법은 재귀 호출을 기본 골격으로 하며, 최상위 문제의 해답을 구하기 위해 필요한 하위 문제들을 재귀적으로 호출하여 풀어나간다. 핵심은 한 번 계산된 하위 문제의 결과를 메모이제이션 테이블(예: 배열, 해시맵)에 저장해 두고, 동일한 하위 문제가 다시 발생할 때는 재계산하지 않고 저장된 값을 반환하는 것이다. 이는 중복되는 부분 문제를 효율적으로 제거하여 재귀 알고리즘의 지수 시간 복잡도를 다항식 시간으로 개선하는 역할을 한다.

구현 과정은 일반적으로 다음과 같다. 먼저 재귀 함수를 정의하고, 함수의 시작 부분에서 현재 상태(주로 매개변수 조합)에 대한 결과가 이미 메모이제이션 테이블에 존재하는지 확인한다. 존재한다면 즉시 그 값을 반환한다. 그렇지 않다면 재귀 호출을 통해 하위 문제들을 풀고, 그 결과를 조합하여 현재 문제의 답을 계산한다. 최종 답을 계산한 후에는 반드시 메모이제이션 테이블에 저장한 다음 반환해야 한다. 이 접근법은 피보나치 수열 계산이나 최장 공통 부분 수열 문제를 재귀적으로 풀 때 매우 효과적이다.

하향식 방법의 주요 장점은 필요한 하위 문제만을 계산하는 지연 평가 방식이라는 점이다. 즉, 전체 문제 공간 중 실제로 해답에 기여하는 상태만을 탐색하기 때문에, 상향식 방법처럼 모든 가능한 하위 문제를 미리 계산할 필요가 없다. 이는 상태 공간이 매우 크지만 실제로 방문하는 상태는 상대적으로 적은 문제에서 유리할 수 있다. 또한 재귀적인 문제 정의를 거의 그대로 코드로 옮길 수 있어 구현이 직관적이고 자연스럽다는 장점이 있다.

반면, 재귀 호출의 깊이가 매우 깊어질 경우 스택 오버플로가 발생할 수 있는 위험이 있다. 또한 함수 호출 오버헤드가 존재하며, 메모이제이션을 위한 추가적인 메모리 공간이 필요하다. 일반적으로 하향식과 상향식 방법은 시간 복잡도는 동일하지만, 상향식 방법이 상수 인자 측면에서 더 빠른 경우가 많다. 따라서 문제의 특성과 제약 조건에 따라 두 방법 중 적절한 구현 방식을 선택하는 것이 중요하다.

피보나치 수열은 동적 계획법을 설명하는 가장 전형적이고 단순한 예시이다. 피보나치 수열은 F(0)=0, F(1)=1이고, n>=2일 때 F(n) = F(n-1) + F(n-2)로 정의되는 수열이다. 이 문제는 재귀적으로 정의되기 때문에, 단순한 재귀 함수로 구현하면 중복 계산이 매우 많이 발생한다. 예를 들어 F(5)를 계산하기 위해 F(3)은 여러 번 계산되며, n이 커질수록 이 중복은 기하급수적으로 증가한다.

이러한 중복 계산 문제를 해결하기 위해 동적 계획법이 적용된다. 하향식 접근법인 메모이제이션을 사용하면, 한 번 계산된 F(n)의 값을 캐시(배열이나 사전)에 저장한다. 이후 동일한 F(n)을 다시 계산해야 할 때는 저장된 값을 즉시 반환한다. 이로 인해 계산 횟수가 크게 줄어들어 시간 복잡도가 O(n)으로 개선된다.

상향식 접근법인 타뷸레이션을 사용하는 방법도 있다. 이 방법은 가장 작은 부분 문제인 F(0)과 F(1)부터 시작하여 순차적으로 F(2), F(3), ... , F(n)까지 차례대로 계산해 나간다. 각 단계의 결과는 보통 배열에 저장되며, 이전 두 항의 값을 참조하여 다음 항을 계산한다. 이 방법도 O(n)의 시간 복잡도를 가지며, 재귀 호출의 오버헤드가 없어 종종 선호된다.

피보나치 수열 문제는 동적 계획법의 핵심 원리인 '중복되는 부분 문제'를 명확하게 보여주며, 계산 결과를 저장하고 재사용함으로써 효율성을 극적으로 높이는 과정을 이해하는 데 가장 적합한 출발점이다. 이 기본적인 이해는 이후 배낭 문제나 최장 공통 부분 수열 같은 더 복잡한 동적 계획법 문제를 푸는 데 기초가 된다.

배낭 문제는 동적 계획법을 설명하는 데 가장 널리 사용되는 고전적인 예시 중 하나이다. 이 문제는 주어진 용량의 배낭과 각각 무게와 가치를 가진 물건들이 있을 때, 배낭의 용량을 초과하지 않으면서 가치의 합이 최대가 되도록 물건들을 선택하는 방법을 찾는 조합 최적화 문제이다. 문제는 물건을 쪼갤 수 있는 경우와 쪼갤 수 없는 경우로 나뉘며, 일반적으로 동적 계획법으로 해결하는 것은 쪼갤 수 없는 0-1 배낭 문제를 가리킨다.

이 문제를 동적 계획법으로 해결하기 위해서는 최적 부분 구조를 활용한다. 배낭의 용량과 고려할 물건의 개수를 변수로 하는 2차원 테이블을 구성하는 것이 일반적이다. 테이블의 각 셀 DP[i][w]는 처음 i개의 물건만을 고려하고 배낭의 용량이 w일 때 얻을 수 있는 최대 가치를 의미한다. 각 단계에서 i번째 물건을 배낭에 넣지 않는 경우와, 넣을 수 있다면 넣는 경우를 비교하여 더 큰 가치를 선택하는 점화식을 세워 문제를 해결한다.

이 접근법을 통해 모든 물건과 모든 가능한 용량(0부터 최대 용량까지)에 대해 계산을 수행하면, 테이블의 마지막 셀인 DP[n][W](n은 물건 총 개수, W는 배낭 최대 용량)에 전체 문제의 최적해, 즉 최대 가치가 저장된다. 이 과정에서 중복되는 부분 문제, 예를 들어 더 작은 용량에 대한 최적값이 반복적으로 필요하게 되므로, 계산 결과를 테이블에 저장해 재사용하는 동적 계획법의 이점이 잘 드러난다.

배낭 문제의 변형으로는 무게뿐만 아니라 부피 등의 제약이 추가된 다차원 배낭 문제, 물건을 여러 개 선택할 수 있는 무제한 배낭 문제 등이 있으며, 이들 역시 동적 계획법의 확장된 형태로 해결할 수 있다. 이 문제는 자원 배분, 투자 포트폴리오 선택, 프로젝트 스케줄링 등 실제 운영 연구 및 알고리즘 설계에 폭넓게 응용된다.

최장 공통 부분 수열 문제는 두 개 이상의 수열이 주어졌을 때, 모든 수열에 공통으로 나타나는 부분 수열 중 가장 긴 것을 찾는 문제이다. 여기서 부분 수열은 원래 수열에서 일부 원소를 삭제하여 얻을 수 있는 수열을 의미하며, 원소들의 순서는 유지되어야 한다. 이 문제는 문자열 처리, 생물정보학에서의 DNA 서열 정렬, 버전 관리 시스템의 차이점 비교 등 다양한 분야에서 응용된다.

동적 계획법을 이용한 해결은 일반적으로 2차원 표를 사용한다. 두 문자열의 길이를 각각 m, n이라 할 때, (m+1) x (n+1) 크기의 표를 생성한다. 표의 각 셀 dp[i][j]는 첫 번째 문자열의 처음 i개 문자와 두 번째 문자열의 처음 j개 문자까지 고려했을 때의 최장 공통 부분 수열의 길이를 저장한다. 점화식은 두 문자열의 현재 문자가 같을 때와 다를 때로 나누어 정의된다.

점화식은 다음과 같이 구성된다. 두 문자열을 A, B라고 하고, dp[i][j]를 A[0..i-1]과 B[0..j-1]의 LCS 길이라고 정의한다.

1. 만약 A[i-1] == B[j-1]이라면, 이 문자는 공통 부분 수열에 포함되므로, dp[i][j] = dp[i-1][j-1] + 1이 된다.

2. 만약 문자가 다르다면, dp[i][j] = max(dp[i-1][j], dp[i][j-1])이 된다. 이는 A의 현재 문자를 제외한 경우와 B의 현재 문자를 제외한 경우 중 더 나은 결과를 선택하는 것을 의미한다.

이 알고리즘의 시간 복잡도는 표의 모든 셀을 한 번씩 채우므로 O(m*n)이다. 공간 복잡도도 동일하게 O(m*n)이지만, 최적화를 통해 O(min(m, n))까지 줄일 수 있다. 표를 완성한 후, dp[m][n] 값이 LCS의 길이가 되며, 표를 역추적하여 실제 LCS 문자열을 구성할 수 있다. 이 접근법은 최적 부분 구조와 중복되는 부분 문제의 성질을 명확히 보여주는 대표적인 동적 계획법 예시이다.

최단 경로 문제는 주어진 그래프에서 두 정점 사이의 가장 짧은 경로를 찾는 문제로, 동적 계획법의 대표적인 응용 사례이다. 이 문제는 출발점에서 목표점까지 가는 경로 중 간선의 가중치 합이 최소가 되는 경로를 계산하는 것을 목표로 한다. 동적 계획법은 이 문제를 여러 개의 작은 하위 문제로 분해하고, 각 하위 문제의 해를 저장하여 중복 계산을 피함으로써 효율적으로 해결한다.

이 문제에 동적 계획법을 적용하는 대표적인 알고리즘으로는 플로이드-워셜 알고리즘이 있다. 이 알고리즘은 그래프의 모든 정점 쌍 사이의 최단 거리를 구하는 문제를 해결한다. 알고리즘의 핵심은 각 정점을 중간 경유지로 고려할 때마다 최단 거리 테이블을 갱신하는 것이다. 즉, 정점 i에서 j로 가는 최단 경로가 정점 k를 경유하는 것이 더 짧은지 확인하고, 그렇다면 거리를 업데이트하는 과정을 반복한다.

이 방식은 최적 부분 구조를 명확히 보여준다. 정점 k를 경유하는 최단 경로는, i에서 k까지의 최단 경로와 k에서 j까지의 최단 경로로 구성되며, 이 두 하위 경로 역시 각각 최단 거리여야 한다. 또한, 모든 정점 쌍에 대한 거리를 계산하는 과정에서 동일한 하위 경로(예: i에서 k까지의 거리)가 반복적으로 참조되므로 중복되는 부분 문제의 특성도 가진다. 플로이드-워셜 알고리즘은 이러한 특성을 활용해 상향식 방법으로 문제를 해결하는 전형적인 예시이다.