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

1. 소개

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

 

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

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

 

 

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

피보나치 수는 동일한 부분 함수를 여러 번 호출하므로, 중간 결과를 저장해두면 전체 연산을 효율적으로 수행할 수 있는 대표적인 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를 마무리한 후 백트래킹 알고리즘을 공부할 예정이다.