[실전 알고리즘] 다이나믹 프로그래밍

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

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

 

ex. 피보나치

 

ex. DP

피보나치 문제를 DP로 해결하면 미리 배열을 만들어두고 0번째 인덱스부터 하나씩 채워가는 방식으로 해결할 수 있고 N+1칸을 채우고 나면 답을 알 수 있으니 O(N)에 답을 알아낼 수 있다.

중간 결과를 저장해서 이용하는지 그렇지 않은지에 따라 극적인 시간복잡도의 차이가 발생

 

 

DP를 푸는 과정

1. 테이블 정의하기

 

2. 점화식 찾기

 

3. 초기값 정하기

 

연습 문제

 

BOJ 1463: 1로 만들기

[백준 1463] 1로 만들기 (tistory.com)

 

BOJ 9095: 1,2,3 더하기

[백준 9095] 1,2,3 더하기 (tistory.com)

 

BOJ 2579: 계단 오르기

[백준 2579] 계단 오르기 (tistory.com)

 

BOJ 1149: RGB거리

1149번: RGB거리 (acmicpc.net)

 

BOJ 11726: 2 x n 타일링

[백준 11726] 2 x n 타일링 (tistory.com)

 

BOJ 11659: 구간 합 구하기 4

[백준 11659] 구간 합 구하기 4 (tistory.com)

 

BOJ 12852: 1로 만들기 2

[백준 12852] 1로 만들기 2 (tistory.com)

 

 

 

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x10강 - 다이나믹 프로그래밍 (encrypted.gg)