동적 계획법 (Dynamic Programming) 소개
개요
동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 효율적으로 해결하기 위한 방법이다. 핵심 개념은 큰 문제를 여러 개의 작은 문제로 나누고, 이 작은 문제들을 풀어 그 결과를 이용해 큰 문제를 푸는 것이다. 이 방법은 문제를 푸는 데 걸리는 시간을 줄이고, 이미 푼 문제를 다시 풀지 않도록 도와준다.
작은 문제로 나누기
동적 계획법에서는 큰 문제를 여러 개의 작은 문제로 나눈다. 예를 들어, 큰 퍼즐을 해결하려면 먼저 퍼즐의 작은 조각들을 맞추는 것과 같다. 큰 문제를 해결하기 위해서는 먼저 이 작은 문제들을 해결해야 한다. 이 작은 문제들은 서로 비슷하거나 겹치는 부분이 많기 때문에, 한 번 풀어본 문제는 다시 풀 필요가 없도록 해야 한다.
결과 저장하기
동적 계획법에서는 문제를 풀 때 나온 결과를 저장해둔다. 이것을 메모이제이션(Memoization)이라고 부르는데, 이는 마치 우리가 어떤 일을 할 때 그 결과를 메모해 두었다가 다시 그 일을 할 때 메모한 내용을 참고하는 것과 비슷한다. 이 방법을 사용하면 같은 문제를 반복해서 풀 필요가 없게 되며, 시간을 절약할 수 있다.
위에서 아래로, 아래에서 위로
동적 계획법을 사용할 때, 문제를 풀어가는 방법에는 두 가지가 있다.
위에서 아래로 (Top-Down): 큰 문제를 풀기 위해, 먼저 큰 문제를 작은 문제로 나누고, 이 작은 문제들을 풀어가는 방법이다. 마치 큰 퍼즐을 풀기 위해 먼저 전체 그림을 보고, 그다음에 작은 조각들을 맞추는 것과 비슷한다. 이 방법에서는 필요할 때마다 작은 문제를 풀고 그 결과를 저장해 둔다.
아래에서 위로 (Bottom-Up): 작은 문제부터 차근차근 풀어 나가면서, 점점 더 큰 문제를 해결하는 방법이다. 작은 퍼즐 조각을 먼저 맞춘 후, 이들을 모아서 전체 퍼즐을 완성하는 것과 비슷한다. 이 방법에서는 모든 작은 문제들을 미리 풀어 테이블에 저장해 두고, 이를 이용해 큰 문제를 해결한다.
동적 계획법의 장점과 단점
동적 계획법은 많은 문제를 빠르고 효율적으로 해결할 수 있도록 도와준다. 하지만 이 방법이 항상 적합한 것은 아니다.
장점: 이미 푼 문제를 다시 풀 필요가 없기 때문에 시간과 노력을 절약할 수 있다. 특히, 비슷한 문제를 여러 번 풀어야 하는 경우에 유용하다.
단점: 모든 문제를 작은 문제로 나누고 그 결과를 저장하는 데 필요한 메모리가 많이 필요할 수 있다. 또한, 작은 문제들을 잘 정의하고, 이들을 어떻게 합쳐서 큰 문제를 해결할지 계획하는 것이 어려울 수 있다.
관련 자료:
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Smith, S., & Smith, A. (2003). Dynamic Programming and its Applications. Springer.
Last updated