dp

종만북 정리

교훈 1. 구현 패턴과 팁

- 항상 기저 사례를 젤 먼저 처리한다. 이를테면 입력이 범위 밖을 벗어나는 경우, 종료 조건, 예외 조건(짝수만 취급되는데 홀수가 나온다던지 등) 등.

- 다음에, 먼저 이 문제를 재귀적으로 해결하는 완전 탐색 알고리즘으로 문제를 단순화, 경량화 해본다. 완전 탐색으로 구현할 경우 어떻게 될지를 먼저 정리한다.

- 완전 탐색이 처리하는 경우의 수 총 개수와, 입력 조건상 주어지는 입력 가능 경우의 수를 비교해본다. 후자가 전자보다 적으면 반드시 중복 처리하고 있는 것이 있다는 것이다('비둘기집 원리').

 

아래는 책에 직접 제시된 dp 레시피.

1 '모든 답을 만들어 보고' 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.

2 전체 답의 점수를 반환하는 게 아니라, '앞으로 남은 선택들'에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.

3 재귀 호출 입력에 이전의 선택에 대한 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 여기서 목표는 중복되는 부분 문제를 많이 만드는 것이다. 입력 종류가 줄어들수록 부분 중복 문제가 많이 생기며 메모이제이션을 최대한 활용할 수 있다. 

4 메모이제이션 적용.

 

 

 

---

- 리트코드 2140: https://leetcode.com/problems/solving-questions-with-brainpower/

다시 풀었을 땐 완탐 가정했을 때의 점화식 세우는 것까진 성공! 하지만 좀 모자란 풀이로 결국 답 봄. 답 보고 완전 이해했음. 완전 메모이제이션으로만은... 못풀고 아마 이렇게 하려면, "정석 대로면" 2중 이상의 배열을 사용해야 할 거다 - 이 문제는 아님. <알고리즘 퍼즐 69>의 1번 문제를 보면 알 수 있음. 따라서 캐싱&재귀 둘다 써야 하는데, 기존 이해 못했던 포인트가 어디서 재귀를 써야 하는 가임. 답은, 현재 알 수 있는 값은 메모 돼있는 dp 배열로부터 구할 수 있으니 메모이제이션 사용하고, 알 수 없는 값에 대해선 재귀를 호출해야 함. 이를 바탕으로 2140_1 풀이 이해 가능. 그렇게 하면 내가 두려워 하는 건 재귀 호출 횟수 땜에 에러 나는 게 두려운건데, 이건 나도 컨트롤 법을 모르겠음.

 

- 리트코드 2222: https://leetcode.com/contest/biweekly-contest-75/problems/number-of-ways-to-select-buildings/

이정도는 뭐랄까 출제해도 완전 오리지널리티 디피처럼 생기지 않았다고나 할까... 풀이는 정말 경이로운 수준이다 난 진짜아예 감을 못잡은 문제였다.

 

- 2156: https://www.acmicpc.net/problem/2156

아깝게 못풀어서 첨에 블로그풀이 공부했다 백준 풀이 공부했는데, 백준 풀이에서 문제가 i번째 잔을 0~2번 '연속' 마신다는 말을 한번에 이해 못해서 다시 풀어도 또 못 풀었음(연속이란 단어땜에 헷갈려서). 그래서 이해한걸 적어보려함.

일단 1,2차원 배열 써서 푸는 2가지 풀이가 있음. 둘다 필요한 개념은 똑같음. 2차원 배열이면 d[n][3] 에서 열 수에 해당하는 3칸은 각각 i번째 잔을 0~2번 연속 마시는 경우에 대한 것임.

i번째 잔을 0번 연속 마신다: i번째 잔을 안마신단 말임. → i-1번째건 마시든 말든, 2연속이든 1연속이든 상관없다는 말임. 그래서 d[n][0] = max(d[n-1][0], d[n-1][1], d[n-1][2]). 1차원인 경우는 

i번째 잔을 1번 연속 마신다: i번째 잔을 마신단 말임. 근데 1번만 연속되어야 해서 i-1번째는 안 마신다는 말임. 그래서 d[n][1] = d[n-1][0] + wine[n]

i번째 잔을 1번 연속 마신다: i & i-1번째 잔을 마신단 말임. 그래서 d[n][2] = d[n-1][1] + wine[n]

 

- 9465: https://www.acmicpc.net/problem/9465

풀이: https://m.blog.naver.com/occidere/220786307316

그냥 dp 그리고 이 문제 자체에 대한 이해가 부족해서 틀린듯.. 나중에 또 다시 풀어야 함

 

- 10844: https://www.acmicpc.net/problem/10844

아하 2차원 배열을 사용해서 푸는 문제구나... 사실 그전까진 감이 도대체가 안왔고 백준 강의 보고 품. 다시 풀어야함 ㅠ

 

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

제일 잘푼 사람 풀이 저장해뒀는데 복잡도를 엔제곱에서 엔으로 줄여서 매우 혁신적임...

글고 유제로 11054(골4) 풀기. 이건 고민하다 답본 문제임

 

- 1912: https://www.acmicpc.net/problem/1912

고민하다 답 봄. 답이 이렇게 단순하다는게 믿기지 않...

 

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

고민하다 답 봄. 포도주 문제랑 매우 유사하며 더 쉬운 버전인데도 결국엔 못풀고 흠... 2번째 시도엔 품. 아 이제 좀 원숙해졌나보다 이정도는 푸는군.

 

- 11053: https://www.acmicpc.net/problem/11053

발상을 고민해봤는데 내 발상이 안바뀌길래 20분 고민하고 풀이봄. 직관적인 풀이 방향이 있긴 했는데 그 이상에서 발전이 없길래 복습을 하는게 낫겠단 생각이었음. 일단 시간 복잡도 O(N**2)인걸 파악하지 않은게 잘못이고, 설마 다프일까 그리디 아닐까 했는데 다프였음. 엔제곱 시간 복잡도로 다프일 거란 생각을 못함 그런 다프를 본 기억이 없어서... 머릿속에 고착된 다프 패턴이 있어서 이럼. 머릿속 풀이로는 큐 랑 배열 하나 써야할 줄 알았는데 다프로 이렇게 풀면 되는구나 하고 오히려 배운게 있었음.

 

 

 

 

---

종만북 217쪽에 비둘기집 원리 이론을 어떻게 문제 풀이, 즉 메모이제이션이 있는게 반드시 효율적인 이유를 증명할 때 쓰는데 이 사고법은 정말 배울 만하다!

jump에 주어지는 입력 개수 = jumpSize 개수 = 가로개수*세로개수 (=여기서는 10000개) 인데,

경로개수는 아마 순열조합? 같은걸로 계산할수있으려나 싶은데 아무튼 만개보다는 많잖아? 아하 이것도 수학적으로 이해해야 하겠네 흠

아무튼 그 이유 때문에 비둘기집 원리에 의해 중복 검사가 반드시 포함된다 (책에선 "중복으로 해결되는 부분 문제가 항상 존재한다"라 써있음).