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

다이나믹 프로그래밍(Dynamic Programming)

• 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘

문제를 해결하기 위한 점화식을 찾아낸 후, 점화삭의 항을 밑에서부터 차례대로 구해나가서 답을 알아내는 형태의 알고리즘

ex. 피보나치 문제

• 1.재귀적 방법 활용시 => 피보나치 수열의 n번쨰 항을 재귀적으로 구하면 중복된 연산이 계속 발생해서 O(1.618^n) 이 발생한다.

int fibo(int n){
  if(n <= 1)
    return;
  return fibo(n-1) + fibo(n-2);
}

• 2. DP 활용시 => 미리 배열을 만들어두고, 0번째 인덱스부터 하나씩 채워나가는 방식으로 해결 가능. n+1 칸을 채우고나면 답을 알 수 있으므로, O(n) 에 답을 알아낼 수 있다.

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

DP를 푸는 과정

1.테이블 정의하기
2.점화식 찾기
3.초기값 정하기

• 코테에 나올 DP 수준은 일단 점화식만 찾고나면 그 뒤는 초기값을 채워넣은 후에
  반복문을 돌면서 배열을 채우면 끝이여서 구현이 굉장히 쉽다.