[Algorithm] 동적 계획법(Dynamic Programming)이란?

 

안녕하세요 Foma 💻 입니다!

 

그 동안 알고리즘 문제를 풀면서 동적 계획법 관련된 문제가 나오면 어려움을 겪곤 했는데요..

 

오늘은 동적 계획법에 대해서 제대로 정리를 해보려고 합니다.

 

바로 시작할게요!

 

---

동적 계획법(Dynamic Programming)이란? 

 

다이나믹 프로그래밍은 1950년대 미국의 수학자인 리처드 벨맨이 최적화 문제(Optimization Problem)를 해결하기 위해서 고안되었다. 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말하며 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키 백과 -

 

즉, 분할 정복 알고리즘과 같이 큰 문제를 작게 쪼개서 문제를 해결해 나가는 알고리즘입니다.

 

다이나믹 프로그래밍이 되기 위한 조건은 3가지가 있습니다.

 

1. Simple subproblems

 

큰 문제를 작은 문제로 나눌 수 있어야 합니다.

 

2. Optimal substructure

 

최적의 해를 찾는 구조를 만들 수 있어야 합니다.

 

3. Overlapping problems

 

작은 문제들이 중복되어야 합니다.

 

이렇게 세 가지 조건을 만족해야 다이나믹 프로그래밍이라고 정의할 수 있습니다.

---

분할 정복(Divide and Conquer) 알고리즘과의 차이점

 

그렇다면 분할 정복 알고리즘과 차이점은 무엇일까요?

 

분할 정복 알고리즘에 의해 분할된 작은 문제들은 서로 독립적입니다. 즉 서로 관계가 없다는 뜻이죠.

 

하지만 다이나믹 프로그래밍 알고리즘으로 분할되는 작은 문제들은 서로 독립적이지 않고 한번 해결된 문제들을 서로 공유합니다.

 

쉽게 예를 들어 설명해 드리겠습니다.

 

먼저 분할 정복 알고리즘의 가장 대표적인 합병 정렬의 과정을 살펴보겠습니다.

 

아래 그림과 같이 서로 분할된 정보는 다른 곳에 사용되지 않고, 사용될 때마다 계산을 해줘야 합니다.

 

 

그 다음으로 다이나믹 프로그래밍의 가장 대표적인 피보나치 수열을 살펴보겠습니다.

 

아래 그림과 같이 분할되더라도 동일한 함수 ex) F(1)을 공유합니다.

 

위 그림을 보면 F(2)를 구하기 위해서 F(1)과 F(0)이 계산되어야 합니다. 그리고 F(3)을 구하기 위해선 F(2)와 F(1)이 계산되어야 합니다.

 

즉, 동일한 문제를 여러번 구해야 하는 문제점이 생기죠?

 

다이나믹 프로그래밍은 이러한 문제를 메모이제이션(Memoization) 기법으로 해결합니다.

 

이것 때문에 비효율적인 분할 정복을 개선한 알고리즘이라고 불립니다.

---

메모이제이션(Memoization)

 

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. - 위키 백과 -

 

즉, 앞서 해결된 문제를 메모리에 저장해놓고 똑같은 문제가 발생했을 때 꺼내서 사용하는 것이죠.

 

다른 말로는 캐싱(Caching)이라고도 불립니다.

---

Top Down vs Bottom up

 

다이나믹 프로그래밍으로 문제를 해결해나가는 방법은 두 가지가 있습니다.

 

바로 바텀업 방식과 탑다운 방식이죠. 

 

Top Down

 

탑다운 방식은 말 그대로 위에서 아래로(큰 문제에서 작은 문제로) 해결해 나가는 방식입니다.

 

아래 그림과 같이 F(6)을 해결하기 위해서 F(5)와 F(4)를 구하고 F(5)를 구하기 위해 F(4)와 F(3)을 구하고....

 

이런 식으로 가장 작은 문제 F(0)과 F(1)이 될 때까지 재귀 알고리즘을 사용하는 방식입니다.

 

재귀를 이용하기 때문에 앞서 호출했던 결과를 저장해 놓아야 합니다.

 

즉, 위에서 언급했던 메모이제이션 기법은 탑다운 방식일 때 사용됩니다.

 

 

 

Bottom Up

 

바텀업 방식은 단순히 반복문을 통해서 가장 작은 문제에서 해결해야 하는 문제에 도달할 때까지 반복합니다.

 

즉 해결해야 하는 문제가 F(6)이라면 0부터 6까지 차례대로 문제를 해결해 나가는 방식이죠.

---

다이나믹 프로그래밍의 과정 

 

1. 최적해를 구할 수 있는 구조를 정의합니다.

2. 최적해의 값을 재귀적으로 정의합니다.

 

3. 캐싱을 사용하는 탑다운 방식이나 바텀업 방식으로 값을 계산합니다.

4. 계산된 값으로 최적의 해를 구합니다.

 

쉬운 이해를 위해 예를 들어 다이나믹 프로그래밍 과정을 설명드리겠습니다.

 

동전 수집 로봇(Coin collecting robot)

 

• 동전 수집 로봇은 (1,1)에서 출발하여 길(Cell)의 끝인 (6,5)까지 이동할 수 있습니다.
• 로봇은 오른쪽이나 아래로밖에 이동할 수 없습니다.
• 최대한 많은 동전을 수집하기 위한 경로를 구합니다.

 

 

 

1. 최적해를 구할 수 있는 구조를 정의합니다.

 

길(Cell)이 ixj로 구성되어 있다면 최적해는 가장 마지막 부분인 F(i,j)가 됩니다. 즉(F(6,5)가 가장 최댓값이 됩니다.

 

2. 최적해의 값을 재귀적으로 정의합니다.

 

오른쪽으로 내려갔을 때 또는 아래로 내려갔을 때 중에 더 큰 값을 정하면 되겠죠?

 

즉, 아래 점화식을 재귀 호출합니다. (c는 길(Cell)을 의미합니다.)

F(i, j) = max{F(i-1, j), F(i, j-1)} + cij

 

3. 캐싱을 사용하는 탑다운 방식이나 바텀업 방식으로 값을 계산합니다.

 

2번에서 정의해놓은 점화식을 사용하여 탑다운 방식으로 값을 구해나가면 아래와 같이 값이 계산됩니다.

 

 

4. 계산된 값으로 최적의 해를 구합니다.

 

가장 마지막번 쨰 값인 (6,5)의 값이 5이므로 최적해(최댓값)은 5가 됩니다.

---

오늘은 이렇게 다이나믹 프로그래밍에 대해서 알아보았습니다.

 

혹시라도 틀린 점이나 궁금하신 사항이 있다면 댓글로 알려주세요!