[DP] Dynamic Programming

정의 : Optimal substructure + Overlapping problem 의 구조인 문제를 memoization을 이용해서 푸는 것

 

1. ★ Optimal substructure

주어진 문제에 대한 최적해를 구하고자 할 때, 좀 더 작은 sub-problem들에 대한 optimal solution들을 찾은 후 그것들을 결합하면 결국 전체 문제의 optimal solution 이 되는 경우

(https://cpuu.postype.com/post/3698892)

 

어떤 문제의 최적해가 그 부분문제들의 최적해들로 구성(construct)될 수 있다면 해당 문제는 optimal substructure를 가진다고 말합니다.

(https://ratsgo.github.io/data%20structure&algorithm/2017/11/25/shortestpath/)

 

Optimal substructure가 성립하면, 앞으로의 남은 조각들에 대한 값을 반환하는 함수를 만든 후 재귀로 굴리면 답 찾기 가능

 

 

💡 종만북에 따르면 + 경험상,

현재의 부분 문제를 풀 때, 이전에 푼 부분 문제들에 대한 정보가 필요 없는 경우 

Optimal substructure 구조를 만족하는 듯

 

 

다음 세 가지로 정보를 나눌 수 있음.

 

현재 주로 다루는 정보, 구해야 하는 목표, 이전 문제들에 대한 정보

 

여기서 DP 정의를 요리조리 잘 바꿔서, 이전 문제들에 대한 정보가 필요 없도록 만드는게 핵심 (= optimal substructure).

(⭐️'이전 정보'를 문제 정의에 포함시키려고 노력해봐!)

예를 들어 knapsack 문제에서는 weight가 제한되어 있으므로,

'이전에 어떤 weight의 물건을 선택했는지'라는 이전 정보가 필요.

이건 문제 정의에 '남은 weight'를 포함시키면 해결 가능

 

그리고 보통 이게 만족되면, 중복되는 문제들이 많아짐 (Overlapping subproblem)

(p.226~ DP를 활용한 전통적 최적화 문제)

 

ex) BOJ 2618 - 경찰차

현재 다루는 정보 : 어느 경찰차가 사건 맡을 지, 그에 따른 최단 시간
목표 : 모든 사건 마쳤을 때 최단 시간
이전 정보 : 상대 차량에 대한 위치 정보 (ex. 1-2-2 순으로 움직인다고 할 때, 맨 마지막 2 입장에서 1의 위치는?)

 

dp(m, p) : m번째 사건을 p가 맡을 떄 최단 시간? (1 <= m <= M, p = 1 or 2)

→ 이전 정보 (상대 경찰차의 위치) 를 따로 처리해줘야 해서 optimal substructure X

 

dp(p1, p2, idx) : 가장 마지막으로 해결한 사건이 각각 p1, p2일때 새 사건 idx를 해결하는 최단 시간

→ 각 경찰차가 마지막으로 해결한 사건을 알면, 어디 위치하는지 알 수 있음.

이전 정보를 정의에 포함시켜 문제 해결

ex) SWEA8935 - 스팟마트

현재 다루는 정보 : n 혹은 m을 선택함에 따라 얻을 수 있는 최대 과자 수
목표 : 모든 선택을 마쳤을 때 최대 과자 수
이전 정보 : 바로 이전 과자 (n이든 m이든)를 선택했는가? (했다면 바로 다음 과자는 선택 불가하므로)

 

dp(n, m, picked) : 바로 이전 과자를 picked 했는지에 따라 n, m 번째 과자를 선택해서 얻을 수 있는 최대 과자 수

 

 

2. Overlapping problem

중복되는 Subproblem이 발생 -> memoization으로 시간 단축

 

 

[memoization]

: 이미 전에 풀었던 문제가 다시 나타나면, 새로 풀지 않고 구해놓은 답을 가져다가 쓰는 개념. 

Top-down : Memoization list 같은곳에 푼 결과 기록해나가며 recursion 진행

Bottom-up : DP table 처음부터 쌓아올리기

* 둘을 따로 구분하지 않기. Bottom-up 방식에서도 DP 함수를 이용해 재귀를 사용할 수 있다

 

❗ 그러나, 특정 방식에 특화된 문제들도 있는 모양.
Top-down으로는 문제가 생기는데, Bottom-up으로는 쉽게 풀린다던지

 

* Optimal substructure를 만족해야 하기 때문에, 반드시 점화식을 세울 수 있다.

Top-down의 경우, 점화식대로 쉽게 코드를 짤 수 있는 반면에,

Bottom-up은 언뜻 보면 코드에 점화식이 explicit하게 나타나지 않는 경우가 많다.

 

 

⭐️ [Time complexity]

부분 문제의 수 (주로 Bottom-up DP 테이블 크기) * 각 부분 문제 푸는데 걸리는 시간 (Loop 몇 개?)

 

 

 

✨ Bottom-up 테이블 채울 때 필수 꿀팁

점화식 세우면, 어느 방향으로 테이블을 채워나가야 하는지 알 수 있다.

 

ex) 

Longest Common Subsequence 문제

점화식 : dp[i][j] = max(dp[i][j+1], dp[i+1][j], dp[i+1][j+1] + 1 (if s1[i] == s2[j]) )
base case : i == s1.size() || j == s2.size()

왼: 점화식 봤을 때 채워나가야 하는 방향 / 오: 테이블의 어느 부분이 초기화가 필요한지

 

 

---

유형 정리

 

Normal DP (1~2차원)

1053 팰린드롬 공장 문자열을 팰린드롬으로 만들기 위해, 삽입/삭제/교환/서로 위치 변경 (단 1회) 등 연산 있

dp[i][j] : 문자열 중 i부터 j까지 palindrome으로 만들기 위해 필요한 최소 연산 수

 

★ 왜 2차원 테이블로 구성하는지 생각해봐야 함.

→ 하위 문제 찾기에 유리하기 때문. 제시된 4개의 연산 중 하나를 사용해서 dp[i][j]를 만들었다고 할 때, 하위 문제는 어떻게 될까? 맨 앞/뒤에만 연산을 한다고 하면, dp[i-1][j] 혹은 dp[i][j-1] 등이 하위문제가 되지 않을까?

 

 

1509 팰린드롬 분할 주어진 문자열을 작은 팰린드롬들로 분할했을 때, 그 작은 팰린드롬들 개수의 최솟값

ex) ABBA = {ABBA}, {A, BB, A}, {A, B, B, A} -> 1개짜리 ABBA가 있으므로 분할 최솟값 1

 

문자열을 다루니까 dp[i][j] 처럼 2차원 테이블을 구성해야 할 것 같지만, 1차원이 더 깔끔한 하위문제 정의 가능

dp[k] : 0~k 까지의 팰린드롬 분할 최솟값

0~k-1까지의 문자열이 팰린드롬이었냐 아니냐에 따라 점화식 다르게 정의해서 처리 가능

 

★ 주어진 문자열이 팰린드롬인지 아닌지 확인하는 isPalindrome도 DP식으로 구현할 수 있는데,

이때 테이블은 2차원이여야 한다. 왜 그럴까?

→ 길이 N인 문자열 A가 팰린드롬인지 확인하려면? 가장 먼저 맨 앞과 뒤 문자가 같은지 확인. s[1]==s[N]

만약 같다면? 2~N-1의 범위가 팰린드롬인지 확인하면 되잖아? isPalindrome(2, N-1)

따라서, dp[i][j]로 구성하는게 좋음.

 

 

다차원 DP

2518 회전테이블 3명이서 회전테이블에 놓인 음식을 먹는데, 각자 먹어야 하는 음식 순서가 정해져있음.

테이블 회전을 최소로 하여 음식을 모두 먹을 수 있는 방법?

> BF X (후보 3명, 최대 300번 시뮬), 구현/그리디 X (특정 규칙 세우기 힘듦), DP 의심

 

dp[i][j] : i번째 사람의 j번째 요리를 처리했을 때, 최소 테이블 회전 수 (i : 0 아빠, 1 엄마, 2 현아)

→ 동일한 i에 대해서는 dp[i][j] = dp[i][j-1] + alpha 같은 관계를 정할 수 있지만, i가 달라지면 관계 규명 힘듦

(ex. dp[0][3]이라고 할때, 엄마나 현아가 몇 번째 음식까지 먹었다고 정할 수 없음 → 다 따져야 함; 무리)

 

★ Q. 각 사람간 관계에 대한 constraint를 추가할 수 없을까? a가 3번째 음식을 먹은 뒤 b가 2번째 음식을 먹은 걸 조사할 수 있도록

 

dp[a][b][c][d] : 첫 둘 셋째가 각각 a, b, c 개의 음식을 먹었고, 마지막으로 사람 d가 음식을 먹은 상황에서 최소 회전 수

→ d가 0이라면, dp[a][b][c][d]는 dp[a-1][b][c][0, 1, 2] 와 관계가 있음; 점화식 세우기 가능

 

 

Top-down DP

BOJ 1937 욕심쟁이 판다 판다가 대나무를 먹으러 보드 위를 이동하는데, 현재 위치보다 대나무가 많은 곳으로만 이동 가능.  판다가 이동할 수 있는 최대 거리는 (= 최대 생존 기간)?

 

dp[i][j] : (i, j)에서 판다가 멈췄을 때 이동한 최대 거리

당연히 주변 좌표와 연결해서 점화식을 세울 수 있는데, 문제는 주변 값들이 unknown일 경우가 있다는 것

→ Top-down 식으로 재귀 호출해서 해결

 

 

'취직하려는데 DP가 필요할까요? 코딩인터뷰에도 잘 안나온다는데' 라고 물으신다면

수 많은 알고리즘, 다양한 세상의 문제들을 DP를 이용해서 풀 수 있다.

부분 구조, 메모이제이션 (캐싱) 등은 여러 문제 해결에 흔히 쓰이는 기법이다.

프레임워크나 깨작깨작 만지는 코더에서 멈출거면 필요 없겠지만, 스스로 문제 해결을 하고싶은 '개발자'라면 공부

https://www.reddit.com/r/csMajors/comments/p50dt1/is_dp_something_i_should_heavily_prepare_for_or/

 

 

 

---

문제 유형 정리

knapsack류

0/1 knapsack - 선택에 제한 (ex. 무게), cost 최대화

문제 ex) SWEA3282 내 풀이 35번

 

* Fractional knapsack → items are divisible; 그래서 Greedy로 풀림

 

LCS 

Longest Common Subsequence, 

Longest Common Substring 

https://goldenriver42.tistory.com/153?category=923015 

 

LIS (Longest Increasing Subsequence)

https://goldenriver42.tistory.com/146?category=923015 

 

스케쥴링

시간이 겹치면 선택 못함, profit 최대화

https://leetcode.com/problems/maximum-profit-in-job-scheduling/

https://www.acmicpc.net/problem/15486