코딩테스트를 보고, 못 풀었던 문제를 복기해보면, 대부분 다이나믹 프로그래밍 문제였던 것 같다.
이번 주에 알고리즘 스터디에서 DP 문제를 풀고 있는데 다른 알고리즘에 비해 혼자서 해결하지 못하는 문제가 많다고 느꼈다.
DP 포비아를 극복하기 위해 다이나믹 프로그래밍에 대해서 알아보고, 어떻게 문제에 접근해야할지 고민해보자.
다이나믹 프로그래밍
-
간단하게 말하면, 작은 문제들의 결과를 활용해서 큰 문제를 푸는 방식
-
추가적으로 메모이제이션 기법을 사용하여 시간 복잡도를 줄일 수 있다
다이나믹 프로그래밍 기법으로 풀 수 있는 문제의 조건
-
큰 문제를 작은 문제로 나눌 수 있다.
-
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서 동일하게 사용가능하다.
실제로 문제를 맞딱드렸을 때 DP로 푸는 문제인지 판단하는 법(경험)
조금 전형적인 문제라면 바로 DP로 풀기 ex)냅색
그렇지 않다면
-
완전탐색으로 풀었을 때 시간 초과가 날 것 같다? -> PASS
-
그리디로 풀었을 때 설명하지 못하는 case가 있는 것 같다? -> PASS
-
그럼 DP를 고려해보자 (물론 DP 조건 1,2를 만족해야함)
문제 풀이 방법
-
top-down : 재귀함수 사용, 큰 문제를 작은 문제로 쪼개면서 푼다
-
bottom-up : 재귀함수 사용x, 작은 문제들을 먼저 풀고, 이를 활용하여 큰 문제를 푼다.
-
bottom-up 방식으로 주로 풀게 되는 것 같다.
DP 문제는 결국 이전 값들을 활용해서 현재 값의 결과를 얻어내는 방식이다.
무엇을 기준으로 이전 값을? → 이 기준을 잡는 것과 이전 값을 어떻게 활용하는지가 핵심이다.
백준 2293번(동전 1) 문제를 풀면서 무엇을 기준으로 잡는지에 따라 정답과 오답이 갈리는 것을 느꼈다.
처음 풀이
동전으로 만들 수 있는 합을 기준으로 삼았다.
dp[i] = 동전의 합이 i가 되는 경우의수
동전의 값이 c일 때, dp[i]+= dp[i-c]로 계산했다.
이 방법의 문제점
dp[3]에서 [1,2]와 [2,1]를 구별하지 못한다.
중복 계산한 값들을 제거하려면 또다른 코드가 필요하고, 합이 커질수록 굉장히 복잡해짐
DP 문제에서 점화식을 세울 때, min,max와 같이 과거의 값들로 단순한 계산이 아닌 다른게 필요하다면, 내가 잘못된 길을 가고 있는 것은 아닌지 의심해보자. 만약에 이런 것을 느낀다면, 기준을 다르게 잡아보자.
다음 풀이
사용한 동전의 종류를 기준으로 삼는다. 구체적으로는 특정 동전을 사용했는지 안했는지
예를 들어, 동전이 [1,2]라 하자
동전 2를 쓴 경우의 수와 안쓴 경우의 수와 같이 나눌 수 있다.
-
1짜리 동전만 쓴 경우
-
1짜리 동전과 2짜리 동전을 쓴 경우
2가지 케이스가 절대 겹칠 수가 없다.
1차원 배열에 새로운 동전을 사용할 때마다 값을 누적하는 식으로 결과를 구할 수 있다.
-
동전 1로 만들 수 있는 경우의 수 (i = 0)
-
동전 2로 만들 수 있는 경우의수 (i=1)
-
i=0일 때 계산했던 배열에 누적한다.
-
동전 1로 만들 수 있는 경우의 수 (i=0의 결과) + 동전 2를 추가해서 만들 수 있는 경우의 수
동전 사용 여부를 기준으로 두면, 이전 결과를 사용하여 현재의 답을 깔끔하게 얻어낼 수 있다.
풀이 링크
https://github.com/htogether7/algorithm/blob/main/dp/2293.py
