[알고리즘] 동적 계획법 (Dynamic Programming) + 메모이제이션(Memoization)

1. 소개

동적 계획법은 해결하려는 문제를 작은 단위로 쪼개어 접근하는 방식이다. 사전 계산된 값을 여러 번 재활용할 때 효율적이다.

(DP를 정의할 때 '문제를 쪼개는 것'에 초점을 맞추는 것이 DP 이해에 방해가 된다고 판단하여 아래 내용으로 수정합니다.)

 

동적 계획법은 연산 속도를 개선하기 위해 문제를 재설계하는 기법이다.

사전에 계산된 값을 재연산 하지 않기 위하여 결과를 저장해둔다. 이를 위해 적절한 단위로 문제를 쪼개는 것이다.

즉, 동적 계획법에서 중요한 포인트는 문제를 쪼개는 것이 아니라, 연산이 여러 번 되는 것을 막기 위하여 문제를 재설계하는 것이다.

이 과정에서 메모리를 활용하거나 더 작은 단위의 문제로 쪼개어지는 과정이 필요할 수도 있다. (2025.04.28 수정)

 

나무위키에 와닿는 정의가 있어 아래에 추가한다.

동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다. ( 출처: 나무위키 - 동적 계획법 )

 

 

대표적인 예시로는 피보나치 수가 있다.

피보나치 수는 동일한 부분 함수를 여러 번 호출하므로, 중간 결과를 저장해두면 전체 연산을 효율적으로 수행할 수 있는 대표적인 DP 문제이다.

 

피보나치 수의 정의부터 알아보자. 피보나치 수열은 첫 번째, 두 번째 항이 1이고 그 외의 모든 항은 이전 두 항의 합으로 구성된 수열이다. 즉, n번째 피보나치 수를 구하기 위해서는 n-1번째, n-2번째 피보나치 수를 구해야 한다.

 

피보나치 수열 n=6일 때 재귀 호출 횟수

 

위 그림은 피보나치 수열의 6번째 항을 구하는 알고리즘을 시각화한 것이다.

피보나치 함수를 F()라고 정의할 때, F(6)=F(5)+F(4) 이므로 F(6) 항을 구하기 위해서는 F(5), F(4)가 호출되어야 한다. 또한 F(5)=F(4)+F(3)이므로 F(4)와  F(3)이 호출되어야 한다.

여기서, F(6)과 F(5)를 구하는 과정에서 F(4)가 두 번 호출된 것을 알 수 있다.

위 이미지를 자세히 보면, F(6)을 구하는 과정에서 F(4) 외에도 부분 함수들이 여러 번 호출되고 있음을 확인할 수 있다.

 

동적 계획법에서는 이렇게 동일한 값을 여러 번 계산해야 하는 경우, 처음에만 연산한 후 메모리에 저장해두고 재사용한다.

 

 

2. 세부 방식

Dynamic Programming ❘ Top-down vs Bottom-up

2-1. Top-Down 방식

1. 정의

큰 문제를 계속해서 작은 문제로 분할하며 푸는 방식이다. 위 소개에서 보여준 예시가 Top-Down 방식이라고 볼 수 있다. F(6)을 구하기 위해 F(5)와 F(4)로 쪼개고, 다시 F(5)를 F(4)와 F(3)으로 쪼개고... 이 과정을 반복하며 가장 작은 문제로 분할한다.

대체적으로 재귀함수를 많이 활용한다.

 

2. 장점

직관적인 접근 방식으로 특정한 규칙을 찾기 어려운 경우에도 적용이 가능하다.

메모이제이션 기법과 결합하여 시간 복잡도를 개선할 수 있다.

 

3. 한계점

코드를 실행하는 환경의 스택 크기가 한정되어 있어 재귀 함수의 사용이 일부 제한될 수 있다.

메모리를 과도하게 사용하지 않도록 주의해야 한다.

 

2-2. Bottom-Up 방식

1. 정의

가장 작은 문제부터 쌓아 올려 점점 큰 문제를 푸는 것이다. 피보나치 문제를 예로 들자면 낮은 항부터 점차 상위 항으로 구해가는 방식을 예로 들 수 있다. 피보나치는 F(1)과 F(2)가 1이라는 특성이 있는데, 이 특성을 이용해서 작은 값부터 목표하는 값까지 구할 수 있다.

전체 문제를 통달하는 점화식이 존재하는 경우 이 방식을 적용할 수 있다. 피보나치 수열의 점화식은 F(n) = F(n-1) + F(n-2) 이다.

 

2. 장점

반복문을 이용하여 구현할 수 있으므로 메모리 측면에서 자유롭고, 속도가 빠르며, 코드가 간결하다.

점화식을 이용하므로 부분 식을 통해 전체 문제를 이해할 수 있다.

 

3. 한계점

점화식을 찾지 못 하는 경우 구현이 어렵다.

* Top-down 방식을 통해 문제를 풀어본 후 점화식을 찾는다면 Bottom-up 방식으로 변경하는 것도 좋은 방법!

 

 

3. 관련 개념: 메모이제이션(Memoization)

동적 계획법은 과거에 구한 해를 활용하여 문제를 해결하는 기법이다. 이 때, 이 과거에 구한 해를 다시 구하지 않도록 저장해두는(메모해두는) 기법을 "메모이제이션" 이라고 한다. 캐싱(Caching)이라고 부르기도 한다.

동적 계획법에서 메모이제이션과 결합하여 메모리를 활용하는 대신 시간 복잡도를 개선할 수 있다.

 

메모리에 값을 저장하는 기법도 세분화하자면 Top-down 방식에서 사용하는 방식이 메모이제이션이고, Bottom-up 방식에서는 타뷸레이션(Tabulation)이라는 별도의 방식이 존재한다. 

 

그러나 아직 두 개념을 구분해야 하는 필요성을 명확하게 인지하지 못 했기에 두 개념에 대한 설명은 생략한다.

 

 

4. 다음 학습할 내용: 백트래킹(Backtracking)

동적 계획법으로 구할 수 있는 알고리즘은 모두 백트래킹을 이용하여 풀 수 있다고 한다.

동적 계획법이 시간은 더 빠르지만 메모리를 과도하게 사용하는 경향이 있기에, 메모리 제한이 있는 상황에서 백트래킹 알고리즘을 사용하면 좋다고 한다.

DFS, BFS, DP를 마무리한 후 백트래킹 알고리즘을 공부할 예정이다.