DP
DP 에 대해서 학습 해보자!
DP Dynamic Programming 동적 계획법
중복되는 부분을 재탕하는 것이 DP 중복되는 부분 찾기!
조건
- 참조 투명성
입력을 제외한 외적요소에 결과값이 영향을 미치지 않고 동일한 입력에 대해 동일한 출력을 가지는 것
ex) 전역변수에 의해 값이 변함 (외부변수)
- 최적 부분 구조 (Optimal Substructure)
문제를 해결할 때 하위 문제들을 해결한 결과를 이용해 전체 문제의 최적 해답을 구성할 수 있는 구조를 가지는 것을 말함
ex) 피보나치 수열 - 작은 하위 문제들을 이용
- 겹치는 부분 문제 (Overlapping Subproblems)
동일한 하위 문제가 여러 번 반복해서 등장하는 경우, 이러한 문제의 해를 저장해 두고 재사용할 수 있는 구조를 가져야 함
ex) 피보나치 f(5) = f(4) + f(3) 이고 재귀적으로 밑으로 원래 쭉 계산해야 하는데 f(4)를 재귀적으로 계산할 때 f(3)을 계산했다면 f(3)값을 또 계산할 필요 X
- DAG 구조
방향성이 있고 사이클이 없는 그래프 구조
난이도 높은 DP문제에 나옴 - 크게 신경쓸 필요 없음
우리가 판단해야 하는 건 2,3번 하지만 코테에서 쓸 수 있는지 하나하나 판단하기 이것도 쉽지 않다 그래서 코테를 볼 때 유용한 방법! (밑에)
코테를 푸는 순서!
-
완탐으로 먼저 풀기! BUT 경우의 수가 너무 많으면(10억 이상) -> 2번으로
-
메모이제이션 - 경우의 수(10억) 을 오 100만개의 배열로 저장할 수 있네? -> DP로 풀자!
BUT 와 배열도 1억개가 나오네;; -> 3번으로 -
그리디 또는 다른 알고리즘
정리
DP = 완전탐색 + 메모이제이션
완전탐색을 풀듯이 모든 경우의 수를 생각하고 그 경우의 수를 메모이제이션을 한다!
- 어떠한 idx에서 모든 경우의 수를 생각
- 그렇게 완전탐색을 하는 구조를 만듬 (사실상 이 구조가 점화식)
- 그리고 메모이제이션을 검
메모이제이션
그러면 메모이제이션이 뭔데?
어떤 상태값을 자료구조에 저장하는 것 -> 맵이든 셋이든 배열이든 계산된 값을 저장!
int dp[101][2004][2] // idx 100가지, turn 2004, 짝수 or 홀수 2이런 식으로 배열을 활용해서 계산과정을 기록하여 재계산을 방지!!
if (dp[idx][turn][cnt] != -1(초기화 한 값)) return dp[idx][turn][cnt];
// 값이 있다면 return 한다!찐 정리
DP = 초기화 + 기저 사례 + 메모이제이션 + 로직
그렇게 말로만 듣던 무시무시한 DP를 맛봤다 그렇게 무시무시하지는 않은 건 같은데 문제에 적용하는 건 많이 힘들겠지..?
정말 내 식대로 단순화 하자면 메모리를 써서 계산 속도를 늘리는 방법
상태가 될 수 있는 모든 경우의 수를 배열로 공간을 확보해놓고 어떠한 값(최솟값 or 최댓값)
계산이 진행될 동안 DP배열을 확인 해 보는 거다
만약 초기화 된 아닌 계산해서 들어있는 값이 있으면 그걸 활용해서 계산 없이 값을 불러오면 된다!
재밌는 방법인 것 같고 나중에 한번 사용해보고 싶당
