동적 계획법

동적 계획법(Dynamic Programming)은 복잡한 문제를 작고 겹치는 부분 문제로 나누어 해결하고, 각 부분 문제의 해를 저장하여 중복 계산을 피함으로써 효율성을 높이는 알고리즘 기법이다. 최적화 문제를 해결하는 데 주로 사용되며, 문제의 해를 재귀적으로 구하는 방식과 유사하지만, 이미 계산된 부분 문제의 해를 저장하고 재사용하여 시간 복잡도를 크게 줄이는 것이 특징이다.

핵심 개념

• 최적 부분 구조 (Optimal Substructure): 전체 문제의 최적 해가 부분 문제들의 최적 해를 이용하여 구성될 수 있는 경우를 의미한다. 즉, 부분 문제를 효율적으로 해결하면 전체 문제도 효율적으로 해결할 수 있다는 것을 보장한다. 만약 최적 부분 구조가 존재하지 않는다면 동적 계획법을 적용할 수 없다.

• 겹치는 부분 문제 (Overlapping Subproblems): 동일한 부분 문제가 여러 번 반복되어 계산되는 경우를 의미한다. 동적 계획법은 이러한 겹치는 부분 문제의 해를 메모이제이션(Memoization) 또는 테이블을 이용하여 저장하고 재사용함으로써 중복 계산을 방지한다.

접근 방식

동적 계획법은 크게 두 가지 방식으로 구현될 수 있다.

• 탑다운 방식 (Top-Down): 재귀적 접근 방식을 사용하며, 부분 문제의 해가 필요할 때마다 계산하고, 이미 계산된 해는 저장하여 재사용한다. 이는 메모이제이션 기법을 사용하는 것과 같다. 함수 호출 스택을 사용하므로, 재귀 깊이가 깊어지면 스택 오버플로우가 발생할 수 있다는 단점이 있다.

• 바텀업 방식 (Bottom-Up): 가장 작은 부분 문제부터 순차적으로 해를 계산하고, 이를 이용하여 더 큰 부분 문제의 해를 계산한다. 일반적으로 테이블(배열)을 사용하여 부분 문제의 해를 저장하고, 이를 순차적으로 채워나간다. 재귀 호출이 없으므로 스택 오버플로우의 위험이 없다.

적용 예시

동적 계획법은 다양한 문제에 적용될 수 있으며, 대표적인 예시로는 최단 경로 문제(예: 다익스트라 알고리즘, 플로이드-워셜 알고리즘), 배낭 문제(Knapsack Problem), 최장 공통 부분 수열 문제(Longest Common Subsequence), 편집 거리 문제 등이 있다. 각 문제의 특성에 맞춰 최적 부분 구조와 겹치는 부분 문제를 찾아 적절한 동적 계획법 알고리즘을 설계해야 한다.