동적 계획법(Dynamic Programming)편집자 확인

최적 부분 구조는 동적 계획법이 적용 가능한 문제가 가져야 하는 핵심 조건 중 하나이다. 이는 문제의 최적해가 그 부분 문제들의 최적해로부터 구성될 수 있는 성질을 의미한다. 즉, 전체 문제를 더 작은 부분 문제로 나누었을 때, 각 부분 문제의 최적해를 결합하면 원래 전체 문제의 최적해를 얻을 수 있다.

이 성질이 없다면, 부분 문제의 해를 조합하여 전체 해를 구하는 접근 방식 자체가 성립하지 않는다. 예를 들어, 최단 경로 문제에서 A에서 C까지의 최단 경로가 A->B->C라면, 이 경로의 부분 경로인 A->B와 B->C 역시 각 구간의 최단 경로여야 한다. 만약 A->B 구간에 더 짧은 다른 경로가 존재한다면, 원래의 A->B->C 경로는 전체 최단 경로가 될 수 없다. 이처럼 큰 문제의 최적해가 작은 문제의 최적해를 포함하는 구조를 가져야 동적 계획법을 통해 효율적으로 해를 구할 수 있다.

최적 부분 구조를 확인하는 일반적인 방법은 "절단-붙여넣기" 논증을 사용하는 것이다. 주어진 문제의 최적해를 가정하고, 이를 어떤 부분으로 자른다고 상상한다. 만약 잘라낸 부분의 해가 해당 부분 문제의 최적해가 아니라면, 그 부분을 더 최적의 해로 대체함으로써 전체 해를 개선할 수 있어야 한다. 이는 모순을 일으키므로, 원래의 전체 해가 최적이려면 각 부분도 반드시 최적이어야 한다는 결론을 내린다. 이 논증이 성립할 때 해당 문제는 최적 부분 구조를 가진다고 말한다.

동적 계획법의 핵심 원리 중 하나는 중복 부분 문제 속성입니다. 이는 주어진 문제를 재귀적으로 해결할 때, 동일한 작은 문제들이 반복적으로 계산되는 현상을 의미합니다. 예를 들어, 피보나치 수열을 재귀 함수로 계산할 경우, F(5)를 구하기 위해 F(3)은 여러 번 중복되어 계산됩니다. 이러한 중복 계산은 지수 시간 복잡도를 초래하여 알고리즘의 효율성을 크게 떨어뜨립니다.

동적 계획법은 이 문제를 해결하기 위해 각 부분 문제의 해답을 한 번만 계산하고 이를 저장해 놓는 메모이제이션 또는 타뷸레이션 기법을 사용합니다. 이미 계산된 부분 문제의 결과는 테이블이나 배열과 같은 자료 구조에 저장됩니다. 이후 동일한 부분 문제에 대한 요청이 들어오면 저장된 값을 즉시 반환하여 재계산을 방지합니다. 이 접근법은 중복 계산을 제거함으로써 알고리즘의 시간 복잡도를 극적으로 개선합니다.

중복 부분 문제 속성은 최적 부분 구조 속성과 함께 동적 계획법 적용 가능성을 판단하는 두 가지 주요 기준이 됩니다. 문제가 이 두 속성을 모두 만족할 때, 동적 계획법을 통해 효율적인 해법을 설계할 수 있습니다. 반면, 그리디 알고리즘이 주로 사용되는 문제들은 일반적으로 중복 부분 문제 속성을 보이지 않습니다.

메모이제이션과 타뷸레이션은 동적 계획법을 구현하는 두 가지 주요 기법이다. 두 방법 모두 중복 계산을 피해 효율성을 높이는 것이 목표이지만, 접근 방식과 실행 흐름에서 차이를 보인다.

메모이제이션은 하향식 접근법으로, 재귀 함수를 사용하여 문제를 해결한다. 알고리즘은 최상위 문제(예: F(n))를 호출하고, 이는 필요한 하위 문제들을 재귀적으로 호출한다. 각 하위 문제의 결과는 배열이나 해시 테이블 같은 캐시에 저장된다. 이후 동일한 하위 문제에 대한 호출이 발생하면, 캐시에 저장된 값을 즉시 반환하여 계산을 생략한다. 이 방식은 실제로 필요한 하위 문제만 계산한다는 장점이 있지만, 재귀 호출로 인한 오버헤드가 발생할 수 있다.

반면, 타뷸레이션은 상향식 접근법을 취한다. 가장 작은 하위 문제부터 차례대로 해결하여 그 결과를 테이블(보통 배열)에 채워나간다. 예를 들어, 피보나치 수열을 구할 때 F(0), F(1)부터 시작해 F(2), F(3) 순서로 반복문을 사용해 테이블을 완성한다. 이 방법은 모든 하위 문제를 미리 계산하기 때문에 재귀 호출이 없어 오버헤드가 적고, 테이블 접근이 일반적으로 더 빠르다. 그러나 문제에 따라 불필요한 하위 문제까지 모두 계산할 가능성이 있다.

두 방법의 선택은 문제의 성격에 따라 달라진다. 다음 표는 주요 차이점을 비교한 것이다.

일반적으로 타뷸레이션이 공간 최적화가 더 용이하고 성능이 우수한 경우가 많다. 그러나 메모이제이션은 문제의 구조를 그대로 재귀 함수로 표현할 수 있어 코드 가독성이 높을 때가 있다. 두 기법 모두 최적 부분 구조와 중복 부분 문제를 가진 문제를 효율적으로 해결하는 동적 계획법의 핵심 구현 수단이다.

피보나치 수열은 동적 계획법을 설명하는 데 가장 흔히 사용되는 고전적인 예시이다. 이 수열은 F(0) = 0, F(1) = 1이고, n ≥ 2일 때 F(n) = F(n-1) + F(n-2)로 정의된다. 재귀 함수를 사용해 단순히 구현하면, 같은 값을 반복적으로 계산하는 중복 부분 문제가 발생하여 지수 시간 복잡도를 가진다[2].

동적 계획법은 이 비효율성을 해결한다. 하향식 접근법(메모이제이션)을 사용하면, 한 번 계산된 피보나치 수를 배열이나 해시 테이블에 저장하여 재사용한다. 상향식 접근법(타뷸레이션)은 더 작은 문제부터 차례대로 계산해 나간다. 보통 0과 1부터 시작해 n까지 순차적으로 계산하며, 이전 두 값만 저장하면 되므로 공간 복잡도도 최적화할 수 있다.

두 접근법 모두 시간 복잡도를 O(n)으로 줄이며, 기본적인 재귀 구현의 비효율성을 명확히 보여준다. 다음 표는 상향식 접근법으로 피보나치 수를 계산하는 과정을 보여준다.

배낭 문제는 동적 계획법의 대표적인 적용 예시 중 하나이다. 이 문제는 주어진 용량을 가진 배낭과 각각 무게와 가치가 정해진 물건들의 집합이 주어졌을 때, 배낭의 용량을 초과하지 않으면서 가치의 합이 최대가 되도록 물건들을 선택하는 방법을 찾는 조합 최적화 문제이다. 문제는 보통 0-1 배낭 문제와 분할 가능 배낭 문제로 나뉘는데, 동적 계획법으로 해결하는 대표적인 형태는 각 물건을 통째로 넣거나 넣지 않아야 하는 0-1 배낭 문제이다.

해결을 위해 일반적으로 2차원 배열 DP[i][w]를 사용한다. 이 배열은 처음 i개의 물건을 고려했을 때, 배낭의 용량 w로 얻을 수 있는 최대 가치를 의미한다. 점화식은 다음과 같이 정의된다.

1. i번째 물건의 무게(weight[i])가 현재 고려하는 용량 w보다 크면, 해당 물건을 넣을 수 없다. 따라서 DP[i][w] = DP[i-1][w]이다.

2. 그렇지 않다면, 두 선택지 중 더 큰 값을 취한다: i번째 물건을 넣지 않는 경우(DP[i-1][w])와, i번째 물건을 넣는 경우(value[i] + DP[i-1][w - weight[i]]).

이 접근법은 최적 부분 구조와 중복 부분 문제를 명확히 보여준다. 최종 답은 DP[n][W] (n은 물건의 총 개수, W는 배낭의 최대 용량)에 저장된다. 시간 복잡도는 물건의 수(n)와 배낭 용량(W)에 비례하여 O(nW)이다. 이는 의사 다항 시간 알고리즘에 해당한다.

최장 공통 부분 수열(LCS, Longest Common Subsequence)은 두 개 이상의 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 여기서 부분 수열은 원래 수열에서 일부 원소를 제거하여 얻을 수 있는 수열을 의미하며, 원소들의 순서는 유지되어야 한다. 이 문제는 동적 계획법을 설명하는 데 자주 사용되는 고전적인 예시 중 하나이다.

LCS 문제는 일반적으로 두 개의 문자열 또는 수열에 대해 정의된다. 예를 들어, "ABCBDAB"와 "BDCABA"라는 두 문자열이 있을 때, LCS는 "BCBA" 또는 "BDAB" 등이 될 수 있다. 이 문제를 해결하기 위한 동적 계획법 접근법은 다음과 같은 점화식을 사용한다. 두 수열을 각각 X(길이 m), Y(길이 n)라고 할 때, LCS의 길이를 저장하는 2차원 배열 dp[i][j]를 정의한다. dp[i][j]는 수열 X의 처음 i개 문자와 수열 Y의 처음 j개 문자 사이의 LCS 길이를 나타낸다.

점화식은 다음과 같이 세 가지 경우로 나뉜다.

1. i=0 또는 j=0일 때: dp[i][j] = 0 (한 수열의 길이가 0이면 공통 부분 수열의 길이도 0이다)

2. X[i] = Y[j]일 때: dp[i][j] = dp[i-1][j-1] + 1 (현재 문자가 같다면, 이 문자를 제외한 앞부분의 LCS 길이에 1을 더한다)

3. X[i] ≠ Y[j]일 때: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (현재 문자가 다르다면, X의 한 문자를 제외한 경우와 Y의 한 문자를 제외한 경우 중 더 긴 LCS를 선택한다)

이 알고리즘의 시간 복잡도는 O(mn)이며, 공간 복잡도도 O(mn)이다. 공간을 최적화하면 O(min(m, n))까지 줄일 수 있다. LCS의 길이를 구한 후, dp 배열을 역추적(backtracking)하여 실제 LCS 문자열을 구성할 수 있다.

이 표에서 최종 결과 dp[3][2] = 2는 LCS의 길이가 2임을 의미하며, 역추적을 통해 LCS가 "AC"임을 알 수 있다. 이 문제는 파일 비교(diff) 유틸리티, 생물정보학에서의 서열 정렬(sequence alignment), 텍스트 편집기의 변경 사항 추적 등 다양한 분야에 응용된다.

최단 경로 문제는 주어진 가중 그래프에서 두 정점 사이의 가장 짧은 경로, 즉 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 대표적인 알고리즘으로는 다익스트라 알고리즘과 플로이드-워셜 알고리즘이 있으며, 이들은 모두 동적 계획법의 원리를 기반으로 한다.

다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 이 알고리즘은 각 정점까지의 현재까지 알려진 최단 거리를 저장하는 배열을 유지하며, 아직 방문하지 않은 정점 중 가장 가까운 정점을 선택해 그 정점을 경유하는 새로운 경로를 탐색하는 방식으로 진행된다. 이 과정은 각 단계에서 지역 최적해(가장 가까운 미방문 정점)를 선택하지만, 결과적으로 전역 최적해를 보장하는 그리디 알고리즘의 성격도 함께 지닌다.

플로이드-워셜 알고리즘은 모든 정점 쌍 사이의 최단 경로를 한 번에 구하는 알고리즘이다. 이 알고리즘은 3중 반복문을 사용하며, 핵심 아이디어는 정점 k를 경유할 수 있을 때, 정점 i에서 j로 가는 최단 거리를 점진적으로 갱신하는 것이다. 이를 위한 점화식은 다음과 같다.

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

여기서 D는 최단 거리를 저장하는 2차원 배열이다. 이 알고리즘은 중간 경유지 k를 하나씩 추가해 가며, 이전 단계(k-1)에서 계산된 부분 해를 활용해 새로운 해를 구하는 전형적인 상향식 접근법을 사용한다.

이들 알고리즘은 벨만-포드 알고리즘과 함께 그래프 이론과 운용과학의 핵심 도구로, 네트워크 라우팅, 지도 응용 프로그램, 교통 시스템 최적화 등 다양한 분야에 널리 응용된다.

하향식 접근법은 동적 계획법을 구현하는 주요 방법 중 하나로, 재귀 함수와 메모이제이션 기법을 결합하여 문제를 해결한다. 이 방법은 문제를 최상위 문제로 정의한 후, 이를 더 작은 하위 문제들로 재귀적으로 분해해 나간다. 각 하위 문제를 처음 풀 때 그 결과를 배열이나 해시 테이블 같은 자료 구조에 저장해 두고, 동일한 하위 문제가 다시 발생하면 저장된 값을 즉시 반환한다. 이로 인해 불필요한 재계산을 방지하여 알고리즘의 효율성을 크게 향상시킨다.

이 접근법의 핵심은 '게으른 계산'이다. 문제의 전체 구조를 미리 분석하여 모든 하위 문제를 계산하는 대신, 실제로 필요한 하위 문제만을 요청에 따라 계산하고 그 결과를 캐시한다. 예를 들어, 피보나치 수열을 계산할 때 fib(n)을 호출하면 fib(n-1)과 fib(n-2)를 재귀적으로 호출하며, 각 fib(k)의 값은 처음 계산될 때만 연산을 수행하고 이후에는 캐시된 값을 사용한다.

하향식 접근법은 문제의 논리적 구조를 직관적으로 코드로 표현하기 쉬운 장점이 있다. 특히, 모든 하위 문제를 풀 필요가 없는 경우나 문제 공간이 매우 크지만 실제로 접근하는 부분은 제한적인 경우에 유리하다. 그러나 재귀 호출의 깊이가 매우 깊어질 경우 스택 오버플로가 발생할 수 있으며, 함수 호출 오버헤드가 존재한다는 단점도 있다.

상향식 접근법은 동적 계획법을 구현하는 두 가지 주요 방식 중 하나로, 타뷸레이션 방식이라고도 불린다. 이 방법은 가장 작은 부분 문제부터 시작하여 점차적으로 더 큰 문제의 해답을 구축해 나간다. 즉, 기본적인 경우(Base Case)의 해를 먼저 계산하고, 이를 바탕으로 순차적으로 더 복잡한 문제의 해를 채워나가는 방식이다.

이 접근법은 일반적으로 반복문을 사용하여 구현된다. 예를 들어, 피보나치 수열을 계산할 때, F(0)과 F(1)의 값을 먼저 정의한 후, F(2)부터 F(n)까지 순차적으로 반복문을 통해 계산해 나간다. 각 단계에서 필요한 하위 문제의 해는 이미 계산되어 배열이나 표에 저장되어 있으므로, 빠르게 참조하여 사용할 수 있다.

상향식 접근법의 주요 장점은 모든 부분 문제를 명시적이고 체계적으로 한 번씩만 계산한다는 점이다. 이로 인해 재귀 호출에 따른 오버헤드가 없으며, 호출 스택 오버플로우의 위험이 없다. 또한, 문제의 해를 구하는 순서가 명확하여 공간 최적화가 용이한 경우가 많다. 예를 들어, 배낭 문제를 1차원 배열을 갱신하는 방식으로 최적화하여 구현할 수 있다. 단점으로는, 때로는 해결해야 할 모든 부분 문제를 미리 정의하고 계산해야 하므로, 실제로 필요하지 않은 부분 문제까지 계산할 가능성이 있다는 점을 들 수 있다.

동적 계획법은 생물정보학 분야에서 핵심적인 계산 도구로 널리 활용된다. 특히 유전체 서열 분석과 단백질 구조 예측과 같은 복잡한 생물학적 데이터를 처리하는 데 필수적이다. 긴 DNA나 단백질 서열을 정렬하여 유사성을 찾거나, 진화적 관계를 추론하는 작업은 대규모 탐색 공간을 효율적으로 처리해야 하며, 동적 계획법이 이를 가능하게 한다.

가장 대표적인 응용은 서열 정렬 알고리즘이다. 전역 정렬을 수행하는 니들만-분쉬 알고리즘과 지역 정렬을 위한 스미스-워터맨 알고리즘은 모두 동적 계획법을 기반으로 한다. 이 알고리즘들은 두 생물학적 서열을 행렬로 표현하고, 각 위치에서의 최적 정렬 점수를 이전 계산 결과를 재사용하며 누적해 나간다. 이를 통해 가능한 모든 정렬 경우의 수를 탐색하지 않고도 최적의 정렬을 효율적으로 찾아낸다.

또한, RNA의 2차 구조를 예측하는 데에도 동적 계획법이 사용된다. Nussinov 알고리즘이나 Zuker 알고리즘은 RNA 염기 서열이 주어졌을 때, 염기 쌍 형성에 의해 만들어지는 가장 안정적인 접힘 구조를 찾기 위해 동적 계획법을 적용한다. 이는 유전자 발현 조절 메커니즘을 이해하거나 RNA 신약을 개발하는 데 기초 자료를 제공한다.

동적 계획법은 자연어 처리 분야에서 여러 핵심 과제를 해결하는 데 널리 활용된다. 특히, 시퀀스 데이터를 처리하고 최적의 조합을 찾아내야 하는 문제에서 효율적인 해법을 제공한다. 대표적인 응용으로는 문장 분할, 품사 태깅, 파싱, 기계 번역에서의 단어 정렬, 그리고 음성 인식에서의 발음 네트워크 검색 등이 있다.

이러한 문제들은 종종 가능한 후보들의 조합이 기하급수적으로 많아지는 특성을 지니는데, 동적 계획법은 최적 부분 구조와 중복 부분 문제를 활용하여 이 공간을 체계적으로 탐색한다. 예를 들어, 비터비 알고리즘은 은닉 마르코프 모델 기반의 품사 태깅이나 음성 인식에서 가장 확률이 높은 상태 시퀀스를 찾는 데 사용되는 대표적인 동적 계획법이다. 이 알고리즘은 각 시점에서 최적의 경로만을 저장하고 전파함으로써 전체 경로 공간을 탐색하지 않고도 전역 최적해를 효율적으로 계산한다.

다음은 자연어 처리에서 동적 계획법이 적용되는 몇 가지 구체적인 과제와 사용 알고리즘의 예시이다.

최근에는 딥러닝과 신경망 기반의 모델이 주류를 이루면서, 전통적인 동적 계획법 알고리즘의 역할은 다소 변화했다. 그러나 어텐션 메커니즘의 기저에 있는 정렬 문제나, 신경망 기반 파싱 모델의 훈련 및 추론 과정 내부에서 여전히 동적 계획법의 원리가 중요한 구성 요소로 남아 있다. 또한, 전이 학습이나 적대적 생성 신경망과 같은 복잡한 모델의 효율적인 훈련을 위한 메모이제이션 기법에도 그 사고방식이 영향을 미치고 있다.

동적 계획법은 게임 이론에서 복잡한 다단계 의사결정 문제를 해결하는 핵심 도구로 활용된다. 특히, 완전 정보를 가진 순차적 게임에서 각 플레이어의 최적 전략을 계산하는 데 효과적이다. 대표적인 예로 체스나 바둑 같은 보드 게임에서 특정 위치에서의 최선의 수를 평가하는 데 사용될 수 있다. 게임 트리를 탐색할 때, 동적 계획법은 중복되는 하위 위치(게임 상태)의 평가 결과를 저장하여 불필요한 재계산을 방지한다.

이 방법론의 구체적인 적용 사례는 최소최대 알고리즘과 그 개선 버전인 알파-베타 가지치기에서 찾아볼 수 있다. 이 알고리즘들은 게임 트리의 말단 노드부터 상위 노드로 값을 전파하며 각 플레이어가 최적의 선택을 한다고 가정하고 점수를 계산한다. 동적 계획법을 접목하면 이미 계산된 하위 게임의 결과를 재사용할 수 있어, 동일한 게임 상태에 도달하는 여러 다른 경로를 효율적으로 처리할 수 있다.

확률과 불완전 정보가 포함된 확률 게임이나 포커와 같은 카드 게임의 전략 분석에도 변형된 동적 계획법이 적용된다. 여기서는 각 정보 집합(플레이어가 구분할 수 없는 게임 상태들의 집합)에 대해 최적의 결정을 계산하는 문제로 접근한다. 이러한 복잡한 게임에서 동적 계획법은 이론적 최적 해에 근접하는 전략을 도출하는 강력한 수학적 프레임워크를 제공한다.