[코테]12-다이나믹 프로그래밍

• 다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나눠서 푸는 것.

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

1. Overlapping Subproblem 겹치는 작은 문제
2. Optimal Substructure 최적 부분 구조

• Overlapping Subproblem

• 피보나치 수
  F0 = 0
  F1 = 1
  FN = FN-1+FN-2 (N>=2)
  큰문제 작은문제
  FN-1 = FN-2 + FN-3
  큰문제 작은문제

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

*Optimal Substructure

• 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
• 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.
Optimal Substructure를 만족하기 때문에, 문제에 대한 정답이 변하지 않음.
정답을 한 번 구했으면, 정답을 어딘가에 메모해놓는다.
이런 메모를 배열에 저장하면 됨.
메모를 한다고해서 Memoization이라고 함.

• memo[i] = 피보나치(i)의 값.

1) 모든 문제를 풀어야 함.
2) 모든 문제는 1번만 풀어야 함.
시간복잡도 = 문제의 개수 * 문제 1개를 푸는 시간
-> O(N)

1.Top-down
어떤 문제를 풀기 위해서 문제를 작은문제로 쪼갬.
작은문제로 나눌 수 있으면 또 나눔.
가장 작은 크기의 문제로 나누어졌을 때 return 하면서 원래문제를 풀다가 가장 큰 문제를 푸는 방식임.
주로 재귀함수 이용.
2.Bottom-up
모든 문제의 경우에는 가장 작은 문제가 있음.
가장 작은 문제로 그 다음 문제,, 그리고 그 다음.
작은 것 부터 하나씩 푸는 방식임.
반복문을 이용.

• 점화식 : 문제를 푸는데 필요한 재귀식.

1) 점화식의 정의.
코드가 아니라 글로 작성함.
D[N] = N번째 피보나치 수.
2) 문제를 작게 만들 수 있는 방법을 찾아야 함.
N번째 피보나치 수는 N-1번째와 N-2번째를 합쳐서 만든다.

최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.