10.dp

동적 프로그래밍

문제의 크기를 변화하면서 정답을 계산

작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘

 + memoization

 

1. 문제가 원하는 정답을 찾기 위해 가장 먼저 완전탐색 접근을 시도

2. 완전탐색과정에서 탐색하게 되는 경우가 지나치게 많아서 도저히 안 될것같다

3. 모든 경우를 빠르게 탐색하는 방법으로 dynamic programming접근을 시도해본다

 -> 규격화된 문제 풀이 순서를 외워서 훈련하..?

 

풀고싶은 가짜 문제 정의 -> 가짜 문제를 풀면 진짜 문제를 풀 수 있는가?

-> 초기 값은? -> 점화식 구해내기 -> 진짜 문제 정답 출력

상태 공간의 정의와 상태 파악.status  

반복되는 상태공간이라면 고려해볼만하다. 또한, 무엇의 상태에 따라 변화되는지 파악하는 것이 중요하다.

ex) d[i] = 1~i 원소에 대해 조건을 만족하는.

     d[i][j] i~j번 원소에 대해서 조건을 만족

     d[i][j] ij의 계산값 등

가짜 문제의 예시는

진짜 문제가 수열 A[1...N]에서 조건을 만족하는 부분 수열의 개수라면

D[i]는 수열A[1..i] 에서 조건을 만족하는 부분 수열의 개수

D[N]에 정답이 있을 것

 

초기값 : 쪼개지 않아도 풀 수 있는 작은 문제들의 정답

점화식 구하기 : 계산에 필요한 탐색 경우를 공통점끼리 묶어내기(partitioning) 

                    묶어낸 부분의 정답을 배열을 이용해 빠르게 계산하기

 

가짜 문제의 정의

1) 문제 크기 N을 변수로 만들어 표기하는 경우

 ex) 1,2,3 합 || 2n 타일링

 

2) 문제크기 N과 마지막 상태를 기록해주는 경우

 계단오르기, 오르막 수

 ex) D[i][0] : i-1 안밟고 i번째 계단에 도착한 최대 점수

      D[i][1] : i-1 밟고 i번째 계단에 도착한 최대점수

      D[i][last] : 길이가 i이며 last로 끝나는 오르막수의 개수

3) 구간 L~R에 대한 문제를 해결할 때

4) 2차원 격자 배열에서 문제를 해결할 때

5) 트리 구조에서 문제를 해결할 때.

 

추천 문제)

 

이런 dp 풀어본적 있나요?

- 원형 dp

  https://www.acmicpc.net/problem/17404 (백준, RGB거리 2)

 https://programmers.co.kr/learn/courses/30/lessons/42897

코딩테스트 연습 - 도둑질

- 트리 dp