다이나믹 프로그래밍은 컴퓨터 과학과 알고리즘 분야에서 중요한 기법 중 하나로, 큰 문제를 작은 하위 문제로 나누어 풀고, 중복되는 부분 문제들을 한 번만 계산하여 효율적으로 해결하는 방법입니다. 이를 통해 지수적으로 증가하는 실행 시간을 줄여보다 복잡한 문제들을 효율적으로 해결할 수 있게 됩니다.
다이나믹 프로그래밍의 배경
컴퓨터 과학에서 많은 문제들은 재귀적인 방법으로 해결할 수 있습니다. 하지만 재귀적인 방법은 중복 계산을 초래하며, 이로 인해 지수적인 실행 시간이 발생합니다. 이를 해결하기 위해 다이나믹 프로그래밍이 개발되었습니다.
다이나믹 프로그래밍은 초기에는 수학자인 리처드 벨만(Richard Bellman)이 연구하는 최적화 문제에 적용하면서 등장했습니다. 그 후로 다이나믹 프로그래밍은 컴퓨터 과학과 다른 분야에서 널리 사용되며, 최적화, 최단 경로, 문자열 처리 등 다양한 문제들을 해결하는데에 활용됩니다.
다이나믹 프로그래밍 구조
중복 부분 문제 (Overlapping Subproblems)
중복 부분 문제란, 큰 문제를 해결하기 위해 작은 부분 문제들을 반복적으로 해결해야 할 때, 동일한 작은 부분 문제들이 여러 번 중복해서 발생하는 현상을 의미합니다. 즉, 같은 부분 문제를 반복해서 해결해야 하기 때문에 중복 계산이 발생합니다.
다이나믹 프로그래밍에서 중복 부분 문제는 효율적으로 해결하기 위해 메모이제이션(memoization)이라는 기법을 사용합니다. 메모이제이션은 작은 부분 문제들의 해결 결과를 저장해두고, 이후에 동일한 작은 문제가 등장하면 미리 저장한 결과를 재활용하여 중복 계산을 피하는 방법입니다.
최적 부분 문제 (Optimal Substructure)
최적 부분 문제란, 큰 문제의 최적해(optimal solution)가 작은 부분 문제들의 최적해로부터 구해질 수 있는 성질을 가리킵니다. 큰 문제를 작은 부분 문제들로 분할하여 풀 때, 작은 부분 문제들의 최적해를 이용해서 전체 문제의 최적해를 구할 수 있어야 합니다. 이런 특성을 최적 부분 문제라고 합니다.
다이나믹 프로그래밍을 사용하는 많은 문제들이 최적 부분 문제를 가집니다. 최적 부분 문제를 가지는 문제는 작은 부분 문제들을 풀어놓고 이를 조합하여 전체 문제의 최적해를 구하는 것이 가능해집니다.
다이나믹 프로그래밍 종류
상향식 접근법 (타뷸레이션)
상향식 접근법은 작은 부분 문제들을 해결한 뒤, 이를 이용하여 큰 문제를 해결하는 방법입니다. 작은 부분 문제들을 순서대로 풀어가며 그 결과를 배열 등에 저장해두면, 이후에 큰 문제를 푸는 데에 이용할 수 있습니다. 이러한 방식은 반복문을 사용하여 구현되는 경우가 많습니다.
하향식 접근법 (메모이제이션)
하향식 접근법은 큰 문제를 해결하기 위해 재귀적으로 작은 부분 문제들을 호출하면서, 이미 계산한 값을 메모리에 저장하여 중복 계산을 피하는 방법입니다. 즉, 한 번 계산한 값을 메모리에 저장해두고 필요할 때마다 확인하여 중복 계산을 방지합니다. 이러한 방식은 보통 재귀 함수와 함께 사용되며, 재귀 호출을 통해 작은 부분 문제들을 해결합니다.
다이나믹 프로그래밍의 전형적인 문제들
피보나치 수열(Fibonacci Sequence): 피보나치 수열은 자신의 바로 앞 두 수를 더해서 다음 수를 만들어가는 수열입니다. 재귀적으로 풀면 지수 시간이 소요되지만, 다이나믹 프로그래밍을 사용하여 선형 시간에 해결할 수 있습니다.
배낭 문제(Knapsack Problem): 물건들의 가치와 무게가 주어졌을 때, 배낭의 최대 용량을 초과하지 않으면서 최대 가치를 가지도록 물건을 선택하는 문제입니다. 이 역시 다이나믹 프로그래밍을 사용하여 해결할 수 있습니다.
최장 공통 부분 수열(Longest Common Subsequence, LCS): 두 문자열이 주어졌을 때, 두 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제입니다. 이 또한 다이나믹 프로그래밍을 통해 효율적으로 해결할 수 있습니다.
최장 증가 부분 수열(Longest Increasing Subsequence, LIS): 주어진 수열에서 순서를 유지하면서 부분 수열을 만들었을 때, 가장 긴 증가하는 부분 수열을 찾는 문제입니다. 다이나믹 프로그래밍을 이용해 해결할 수 있습니다.
최단 경로 문제(Shortest Path Problem): 주어진 그래프에서 두 정점 사이의 최단 경로를 찾는 문제로, 다이나믹 프로그래밍을 사용하여 해결하는 방법도 있습니다.
