[코딩 테스트 준비 - 기초] 8. 다이나믹 프로그래밍(DP)

1. 다이나믹 프로그래밍

개념

아래 두 가지 속성을 만족하는 문제를 다이나믹 프로그래밍으로 풀 수 있다.

 

1) 문제들이 겹쳐야 한다.

• 문제를 작은 문제로 쪼갤 수 있어야 한다.
• 큰 문제와 작은 문제를 같은 방법으로 풀 수 있어야 한다.

2) 최적 부분 구조를 만족해야 한다.

• 문제의 정답을 작은 문제의 정답에서 구할 수 있어야 한다.
• 한 문제의 정답은 항상 일정하다.
• 즉, 각 문제는 한 번만 풀어야 하고 그 정답을 어딘가에 메모해 놓아야 한다.

 

즉, 우선 문제가 작은 문제로 나누어지는지 확인하고,

이후 작은 문제의 정답을 이용해서 원래의 정답을 구할 수 있는지 확인한다.

이 경우, 다이나믹 프로그래밍을 이용하면 된다.

 

 

구현 방식

Top-down

• 재귀를 통해 구현
• 큰 문제를 작은 문제로 나누어 함수를 호출한다.

Bottom-up

• 반복문을 통해 구현
• 작은 문제부터 큰 문제까지 차례대로 푼다.

 

cf) 시간복잡도 = 문제의 개수 X 한 문제를 푸는 데 걸리는 시간

 

 

2. 문제 풀이 전략

1) 구하고자 하는 답을 문장으로 정의하기

• ex. N번째 피보나치 수를 구하기

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

• ex. 변수: N -> 1개 (1차원 배열 생성)

3) 문제를 작게 만들 수 있는 방법(경우의 수) 찾기

• 마지막 답을 구하기 바로 이전에 가능한 형태를 생각하면서 찾는다.
• 어떤 상황에서 가장 마지막 단계가 생기는지 찾는다(어떤 단계를 앞에서부터 하나씩 수행했다고 가정).
• ex. N번째 피보나치 수는 N-1번째와 N-2번째를 더해서 만든다

4) 점화식 세우기

• ex. D[N] = D[N-1] + D[N-2]

 

 

3. 백준 참고 문제

• 1453 1로 만들기
• 11726 2xn 타일링
• 11727 2xn 타일링2
• 9095 1, 2, 3 더하기
• 11052 카드 구매하기
• 16194 카드 구매하기 2
• 15990 1, 2, 3 더하기 5
• 10844 쉬운 계단 수
• 2193 이친수
• 11053 가장 긴 증가하는 부분 수열
• 14002 가장 긴 증가하는 부분 수열 4
• 1912 연속합
• 1699 제곱수의 합
• 14501 퇴사
• 2225 합분해