DP- 동적 계획법

- DP란?

DP는 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법을 의미한다. 알고리즘의 분류로 넣긴 했으면 이는 사실 방법론이라고 하는 게 더 맞는 것 같다. 이름의 뜻이 뭔가 깊은 의미가 담겨 있어 보이지만, 그냥 멋있어서 지은 이름이므로 이름과 해당 방법에 연관이 있다는 생각은 버리는 것이 좋다.

 

 

- 왜 쓰나요?

결론부터 말하자면 최적화다. 후에 설명될 Momozation 기법을 사용하여 처음 값을 보관해놓고 이를 활용하는 방식이기 때문에 같은 연산을 여러 번 반복할 필요가 없어 최적화에 용이하다.

 

 

- 언제 쓰나요?

DP를 적용해보기 위해서는 2가지 조건이 필요하다.

1. 겹치는 소문제

작은 문제로 나누었을 때, 중복되는 부분이 없이 각 소문제의 결과를 활용할 수 없다면 DP를 적용하기 어렵다.

2. 최적 부분 구조

소문제들의 각 최적의 값을 이용하여 만든 전체 문제의 값이 최적이 되면 DP를 적용할 수 있다.

 

 

-  DP의 적용

DP를 적용할 수 있는 문제는 모두 특정한 규칙을 따른다.

 

• 규칙 1. 큰 문제를 작은 문제로 나누어 작은 문제를 해결하여 큰 문제의 답을 도출할 수 있다.
• 규칙 2. 점화식은 모든 값 n에 대해 항상 성립해야 한다.
• 규칙 3. Memozation: 반복되는 동일 연산 값은 메모리에 저장, 필요할 때 호출한다.
• 규칙 4. 데이터 테이블(규칙 3을 저장할 실제 메모리 공간 구성)

피보나치의 수 문제 중, f(5)의 값을 구한다고 가정해 보자 

 f(5) = f(4) + f(3)

로 정의될 수 있다. 여기서 핵심은 f(4)와 f(3)역시도 같은 형식으로 표시할 수 있다는 것이다.

f(4) = f(3) + f(2)

f(3) = f(2) + f(1)

결국 피보나치의 수 문제에서 N을 구하고자 할때는

f(N) = f(N-1) + f(N-2)

라는 식을 항상 대입하면 되는 것이다. 해당 식을 점화식이라고 칭한다.

여기서 f(1)과 f(2)의 값을 지정해 주고, 3,4,5,... 를 따로 연산한 후에 데이터 테이블에 저장하게 되면 f(N)를 계산하기 위해 f(N-1)와 f(N-2)을 또 계산할 필요가 없게 되는 것이다. 

 

 

- DP의 풀이 방식

Bottom-Up: 데이터가 차곡차곡 쌓아가며 본래 문제의 결과를 도출하는 기법이다.

1~ N까지의 저장 공간 dp [N]이 있다고 하면 dp [1], dp [2], dp [3],..., dp [N]까지 처음부터 차근차근 구하는 것이다.

피보나치의 경우 f(1) 구하고.. f(2) 구하고…f(n)구하고...

=> 보통 반복문을 이용하며, 순차적 DP 풀이라고 할 수 있다.

 

Top-Down:  어떠한 특정 패턴을 이용하여 연산(점화식)

 => 재귀함수를 보통 이용함(Recursion, Momozation)