알고리즘_부산코딩대회준비_03.동적계획법(DP)

 이전까지 간단한 정렬과 dfs, bfs, 백 트래킹까지 살펴봤다. 이번에 해볼 동적계획법(Dynamic Programming)은 쉽게 말하자면 어렵거나 큰 문제를 간단하고 작은 여러 개의 문제로 나누어서 풀고 작은 문제의 답들을 이용하여 원래 문제의 답을 구하는 방식이다. 

 

 DP는 메모이제이션이라는 기법을 사용한다. 메모이제이션은 미리 구해둔 정답을 메모해놓고 다음번에 다시 해당 문제를 풀고자 한다면 미리 메모해둔 정답을 가져와서 쓰는 기법이다. 흔히 점화식으로 표현한다. DP는 잘 쪼개서 점화식을 만드는게 핵심이다. 그래서 평소 수학을 잘하는 사람이 DP도 잘한다고 흔히 얘기한다. 

 

DP의 가장 기본 문제는 피보나치 수열이다. 간단하게 코드만 올려놓고 DP 다른 문제를 풀어보자.

int fibo[];
fibo[0] = 1;
fibo[1] = 1;
for(int i = 2; i <= n ; i++){
 fibo[i] = fibo[i-1] + fibo[i-2];
}