다이나믹 프로그래밍

 

 

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누고 효율적으로 푸는 방법이다.

효율적으로 풀기 위해서는 중복되는 작은문제에 대한 처리를 Memorization을 통해 간단히 해결할 수 있다.

---

다이나믹 프로그래밍

다이나믹 프로그래밍은 큰 문제를 작은문제로 바꾸어 푸는 것이다.

다이나믹 프로그래밍으로 문제를 해결하기 위해서는 Overlapping Subproblem과 Optimal Substructure라는 두가지 조건을 만족해야한다. 그리고 위의 조건에 의해 불필요하게 중복처리해야하는 문제들이 있다. 이를 해결하기 위해 Memorization을 사용한다.

다이나믹 프로그래밍의 대표적인 예로 피보나치 수열이 있으며 다이나믹 프로그래밍의 두가지 조건과 효율적으로 해결하기 위한 Memoriation을 알아보도록 하겠다.

 

Overlapping Subproblem

Overlapping subproblem은 큰 문제 안에 작은문제가 겹쳐있는 것을 의미한다.

피보나치 수열을 예로 들어보자.

$$F{n} = F{n-1} + F{n-2}$$

위 수식을 보면 n번째 수열을 구하기 위해 n-1번째와 n-2번째 수열을 사용하는 것을 알 수 있다.

 

F(5)을 구하는 예시에서 중복되는 연산을 색으로 표시하였다.

F(5) = F(4) + F(3)

F(4) = F(3) + F(2)

F(3) = F(2) + F(1)

F(2) = F(1) + F(0)

F(1) = F(0) = 1

 

중복되서 호출되는 것을 확인할 수 있다. F(5)가 아니라 훨씬 큰 수의 피보나치라면 더 많은 중복이 있을 것이다.

Optimal Substructure

Optimal Substructure는 문제의 정답을 작은 문제에서 해결할 수 있다는 것을 의미한다.

우리나라의 지형을 예로 들어 설명해보겠다.

서울에서 부산을 가는 가장 빠른 방법을 "서울 -> 대전 -> 대구 -> 부산"이라고 한다면,

대전에서 부산 가는 가장 빠른 방법은 "대전 -> 대구 -> 부산"일 것이다.

만약 대전에서 부산을 가는 가장 빠른 방법이 "대전 -> 경주 -> 부산"이라면 서울에서 부산을 가는 가장 빠른 방법은 잘못된 방법이다.

이렇게 문제의 정답을 찾기 위해 항상 작은문제를 사용할 수 있는 것을 Optimal Substructure라고 한다.

Memorization

Memorization은 다이나믹프로그래밍에서 중복을 해결하는 방법이다. 위 두가지 조건으로 인해 발생하는 문제는 중복된 처리이다.

중복된 처리를 제거하기 위하여 사전에 구한 값들을 저장하고 꺼내 쓰는 방법을 활용하여 중복된 처리를 제거하도록 한다.

문제 해결 방법

문제를 해결하는 방법으로는 Top-down 방법과 Bottom-up 방법이 있다.

Top-down은 큰문제를 작은문제로 나누는 방법으로 재귀를 사용해 구현가능하다.

Bottom-up은 작은문제를 활용해 큰 문제를 푸는 방법으로 반복문을 사용해 구현 가능하다.

 

어느 방법을 사용하든 시간복잡도는 동일하기 때문에 편한 방법을 사용해 구현하면 된다.

우리는 문제를 해결하기 위해 2가지를 고민해야한다.

1. 점화식을 정의 (F(n) = 피보나치의 n번째 수)

2. 문제를 작게 만들수 있는 방법을 찾기(F(n) = F(n-1) + F(n-2)

---

배운내용

1.  다이나믹프로그래밍을 위해서는 Overlapping Subproblem, Optimal Substructure을 만족해야한다.

2.  중복을 제거하기 위해서는 Memorization 기법을 사용한다.

3. 문제를 해결하기 위해 우리는 점화식을 세우고, 문제를 작게 만들 수 있는 방법을 구현해야한다.