[BK] 알고리즘 기초 - 다이나믹 프로그래밍

다이나믹 프로그래밍(DynamicProgramming)

- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

- 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있음

1. Overlapping Subproblem

2. Optimal Substructure

- DP를 푸는 두 가지 방법

1. Top-down

2. Bottom-up

Overlapping Subproblem

- 큰 문제와 작은 문제는 상대적

- 큰 문제와 작은 문제를 같은 방법으로 풀 수 있음

- 문제를 작은 문제로 쪼갤 수 있음

(ex) 피보나치 수

Fn = Fn-1 + Fn-2 (n>=2)

문제: N번째 피보나치 수를 구하는 문제

작은 문제: N-1, N-2 번째 피보나치 수를 구하는 문제

Optimal Substructure

- 문제의 정답을 작은 문제의 정답에서 구할 수 있음

Memorization

- DP에서 각 문제는 한 번만 풀어야 함

- Optimal Substructure를 만족하기 때문에, 정답을 한 번 구했으면 정답을 메모 = 베열에 저장

Top-down

1. 문제를 작은 문제로 나눔

2. 작은 문제를 품

3. 작은 문제를 풀었으니, 문제를 픔

* 재귀 호출을 이용해 쉽게 풀 수 있음

Bottom-up

1. 문제를 작은 문제부터 차례대로 품

2. 문제 크기를 조금씩 크게 만들면서 문제를 점점 품

3. 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있음

4. 그러다보면 언젠간 풀어야 하는 문제를 풀 수 있음

DP 문제 풀이 전략

(1) 문제에서 구하려고 하는 답을 문장으로 나타냄

(ex) N번째 피보나치 수

(2) 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만듬

(ex) Top-down의 경우 재귀 호출의 인자 개수

(3) 문제를 작은 문제로 나누고, 수식을 이용해서 문제 표현