DP_백준_이론

동적계획법(Dynamic Programming)

큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 아래의 2가지 속성을 만족해야 DP로 문제를 풀 수 있다.

1. Overlapping Subproblem

- 예를 들어 피보나치 함수를 보자. f(6)을 구하기 위해서는 f(4), f(5)가 필요하고 f(5)의 값을 알기 위해서는 f(4), f(3)의 값이 필요하다. 즉 여기서 f(4)와 같이 부분문제들이 겹치고 n의 값에 상관 없이 작은 문제를 푸는 방법은 같다. 여기서 알 수 있는 것은 n의 값에따라 값이 일정하다는 것이다. 이로 인해 정답을 한 번 구했으면 정답을 어딘가에 메모 해놓자. 이 것을 Memoization(보통 배열)이라고 한다. 이로 인해 함수 호출 횟수를 줄일 수 있다.

2. Oprimal Substructure

- 문제의 정답을 작은 문제에서 일정히 구할 수 있다.

DP 구현 방식

1. Top-Down : 큰 문제 -> 작은 문제 

보통 재귀함수로 푼다.

2. Bottom-Up : 작은 문제 -> 큰 문제

보통 for문으로 푼다. 작은 문제를 빠짐 없이 다 푼다.

※재귀 함수의 시간 복잡도

채워야하는 칸의 수 (배열의 개수 Memo[n]의 n) * 1칸을 채우는 시간복잡도(함수 코드)

문제 풀이 전략

1. 문제에서 구하려고하는 답을 문장으로 나타낸다.

2. dp[i] : i번째 피보나치 함수 처럼 memoization을 나타내는 배열이 무엇인지 정의한다.

3. 점화식을 세운다.

4. n=0, n=1, n=2 처럼 초기값을 설정한다.

5. 반례를 확인한다.

<+ 배열의 초기값으로 이 값이 계산된건지 아닌건지를 확인한다.>

출처 백준 온라인 강의_알고리즘 기초