동적 프로그래밍

동적 프로그래밍 이란?

DP는 문제에 대한 모든 경우의 수를 효율적으로 탐색하는 프로그래밍 패러다임.

 

1. 문제를 원래 문제의 더 작은 중첩 하위 문제로 나눈다.

2. 중첩 하위 구조에서 최적 솔루션이 형성될수있다. (작은 단위에서 문제를 해결할 솔루션 찾는걸 말하는듯?)

 

이 두가지 특성을 좀 더 자세히 봐보자.

 

피보나치 수열 - DP 를 설명하는 고전적인 예다.

앞의 두 수를 더하면 다음 수열이 나오는구조.

 

피보나치 수 f(n) 이 있다면 작은 하위 문제로 나눌수 있다.

f(n-1) , f(n-2) 그럼 f(n-1) , f(n-2) 이 하위 문제에서 솔루션을 찾고

 

f(n-1) + f(n-2) 로 f(n) 을 구할수있다.

 

핵심은 작은 단위로 잘라서 거기서 해결책을 찾자

 

DP 알고리즘 구현 방법

1. bottom - up (상향식) tabulation (표) 라고도 한다.

2. top - down (하향식) memoization 라고도 한다.

 

Bottom up (상향식)

상향식은 iteration 반복으로 구현해서 가장 아래에서 부터 시작한다.

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

F(0)부터 시작해서 F(n) 까지 반복해서 구한다.

 

Top Down (하향식)

하향식은 재귀로 구현한다.

F(n) 부터 시작해서 재귀로 들어간다. F(n-1) , F(n-2) 계속 재귀로 들어가서

마지막에 있는 F(0) = 1을 찾고 회수되면서 결과를 찾는다.

이 방법에 문제는 너무 많은 반복 계산이 생긴다는것.

근데 여기서 문제는 위 이미지처럼 F(2) 가 3번있다는거다  

만약 우리가 F(100)을 계산한다면 기하급수적으로 계산량이 많아진다.

이걸 해결하기위해 결과를 메모하는것이다.

 

결과를 메모한다는건 함수 호출의 결과를 해시맵이나 배열에 저장을 해둔 후,
동일한 호출인 경우 결과를 다시 계산하지 않고 결과를 반환시켜서 빠르게 해결할 수 있다.

 

F(2)를 어딘가(일반적으로 해시맵)에 저잘해두면, 찾을 필요가 있을때마다 다시 탐색할 필요 없이 계산한 값을 참조해서 쓴다.

 

무슨 방법이 더 좋을까?

각 방법은 장점들이 있다.

 

- 상향식은 일반적으로 재귀 같은 오버헤드가 없어서 더 빠르다.

- 하향식은 작성하기가 더 쉽다. 재귀에서는 하위 문제의 순서가 중요하지 않다. 상향식은 하위 문제를 해결하는 논리적 순서를 생각해야한다.

 

하향식은 재귀를 쓰고

상향식은 반복을 쓴다고 알아두자