2022-07-12
🚩DP에 대하여
사실 문제를 풀다보면 느낌이 되게 특징적으로 다양한 알고리즘들을 적용하여 풀어야 겠다 생각을해보는데 막상 예를 들어 브루트포스 방식처럼 했을 때 절대 시간내에 불가능한 데이터 범위거나 어떤 특정 알고리즘들이 적용이 안 될 경우 결국 마지막에는 DP로 점화식을 세워 푸는 방식에 도달하는게 많은 것 같다.
대체로 DP의 문제의방식은 많이 최대,최소일 때를 물어보는 것같다
🔑DP문제의 푸는 두 가지 방법
하향식:대체로 재귀적인 방식으로 해결하는 형태
메모이제이션을 주로 사용하여 코드를 구현한다
상향식(보텀업):dp테이블을 하나 두어 반복문으로 구현
대체로 dp 테이블을 사전에 값을 초기화 해두어 내가 구할려는 숫자까지 맨 밑에서부터 올라오면서 dp테이블을 업데이트 해나가는 방식-타뷸레이션
모든 dp 문제가 그런 것은 아니겠지만 주로 기본dp문제들의
공통점을 뽑아 패턴을 만든다면
1.내가 구할려는 것을 ai로 설정을 한다.즉 문제에서 구하라는 것이 예를 들어 돈의 금액,창고의 번호 이런 거면 이와같이 밑에서 부터 올라오면서 변동될 수 있는 것을 점화식의 대상으로 삼자!
ex)n원일때의 금액이면 n원이 되기전까지의 모든 금액들을 다 보텀업방식으로 업데이트 해주면서 올라오는 거다!
2.문제에서 주로 최대,최소를 물어볼 것 이다.그럼 기본적으로 min(),max()를 사용할 생각을 갖자
3.이제 min(),max()안에 들어갈 점화식을 짜야 한다
4.그리고 어떤 특정 k에 대하여 한 번 나누어질 수 있는 상황을 분석해봐야 한다
ex)k 번째 창고에 내가 있다.그럼 주위 k-1이나 k-2에 영향을 주고 받는지 보면 인접한거와 한 칸 뛰고 하냐에 따라 달라지듯 두 가지 경우를 알 수 있다
5.해당 기준으로 나누어 점화식을 실행한다!
사실 dp 문제는 정확히 위에 패턴을 따른다고 말은 못하지만
다양하게 풀어보는게 답이긴 하다
🙋♂️대표적인 문제에 대한 정리
출처:이것이 취업을 위한 코딩테스트다.with python
👨💻1로 만들기
사실 이 문제를 딱 처음봤을 때 느낌점은 어라?이거 전에 그리디에서 풀었던 문제이고 다 똑같은데? 이런생각이 들었다.하지만 결론적으로 말해주자면 그리디로 풀 수 가 없다.예를 들어 무작정 나누기만 있었다면 정말 큰 값으로 우선적으로 쭉 나누는것이 가능할 것이다.
하지만 여기서 실제로 값을 1을 뺏을 때에는 꼭 큰 값으로 나눈다고 최적의 해가 된다는 보장이 안된다
즉 그리디와 dp의 헷갈리는 문제들이 많다!!
따라서 그리디를 접근해보고 안 될 것 같다면 dp로 생각을 옮겨보자🔑
🔑풀이 접근법
생각을 해보면 여기서 구해야하는게 연산의 최소횟수로서
지금 변동 가능한 것은 주어지는 X값이다
그럼 X값을 X값까지 밑에서부터 올려보면서 한번 봐보자!
가능한 것은
5로 나누는 방식,3으로 나누는 방식,2로 나누는 방식,1을 빼주는 방식이다
따라서 각 숫자에 대한 최소 연산횟수를 점화식이라고 했을 때
dp_table=[0]*30001
#2부터 하는 이유는 어차피 1은 0이기때문이다
for i in range(2,x+1):
dp[i]=dp[i-1]+1
#먼저 빼는 경우를 최소라고 가정해보자
#각 연산의 횟수이므로 뒤에 1을 더해주는 것
if dp[i]%5==0:
dp[i]=min(dp[i],dp[i//5]+1)
if dp[i]%3==0:
dp[i]=min(dp[i],dp[i//3]+1)
if dp[i]%2==0:
dp[i]=min(dp[i],dp[i//2]+1)
print(dp_table[x])
👨💻개미전사
개미전사 문제를 보더라두 식량의 최대값을 구하라는 것을 볼 수 있다.이 문제에서의 포인트는 인접하냐 인접하지 않냐에 따라서 나눠보는 것 이다.
그럼 먼저 구할려는 것은 식량의 최댓값!
변동되는 값은 그럼 창고의 번호로 하면 될 것 같다!
그럼 창고의 개수를 점차 늘려가면서 N까지 왔을 때 과연 어떻게 될지 점화식을 세우면 될 것 같다
경우1)k번째 창고일 때 ,k-1번 창고를 턴다면??
즉 바로 인접한 상황이라면 k번 창고를 털 수가 없을 것이다
경우2)k번째 창고일 때,k-2번 창고를 턴다면???
즉 한 칸 건너뛴 상황을 의미한다.그럼 k번 창고를 털 수 있을 것이다
타겟점화식:각 창고까지 왔을 때의 식량의 최댓값
dp=[0]*100
arr=list(map(int,input().split()))
d[0]=arr[0]
d[1]=max(arr[0],arr[1])
#1번창고까지는 둘 중에 더 큰걸 업데이트해주면된다
for i in range(2,n):
d[i]=max(d[i-1],d[i-2]+arr[i])
print(d[n-1])
👨💻화폐구성
이 문제에서도 최소한의 화폐개수로서 처음에는 그리디하게 생각을 해볼 수 있을 것 이다.하지만 생각을 해보자면
어떤 화폐구성이 들어올지 모른다.어떤 화폐구성에 따라서는 무조건 큰 수로 나눈다고 되지는 않는다
ex)340원이라는 것을 맞춰볼 때
ex)
-
동전의 구성이 '[500, 100, 50, 10, 5, 1]' 일 때
-
동전의 구성이 '[500, 100, 70, 50, 10, 5, 1]' 일 때
그리디하게 무작정 푼다면 두번째 케이스는 틀리게 된다.
좋다 그러면 dp로 접근해보자
구할려는 것은:최소화의 화폐개수
변동되는 값:금액
그럼 금액을 키우면서 M원이 될 때까지 보텀업으로 진행해보자
어떤 경우로 나눠볼 수 있는지 생각해보자
1) k원일 때 k-i원+1 방법
2) k원일 때 k-i원 까지의 방법이 존재하지 않을 경우
dp=[10001]*(m+1)
#10001은 구성이 안됨을 의미
d[0]=0
for i in range(n):
#가져온 화폐의 단위를 돌리면서
for j in range(array[i],m+1):
#해당 화폐로 가능한 금액들을 다 만들며 체크
if d[j-arr[i]]!=10001:
d[j]=min(d[j],d[j-arr[i]]+1)
if d[m]=100001:
print(-1)
else:
print(d[m])
👨💻금광문제
이 문제에서
구하고자 하는 것:얻을 수 있는 금의 최댓값
변동가능한 값:이차원 리스트에서 나의 위치
점화식:위치를 증가시키며 가질수있는 금의 최댓값
경우:
1) k번째 위치에서 왼쪽위에서 올때
2) k번째 위치에서 왼쪽 아래에서 올 때
3) k번째 위치에서 바로 그냥 왼쪽에서 올 때
dp[i][j]=dp[i][j]+max(left_up,left_down,left)
for j in range(1, m) :
for i in range(n) :
#예외처리-위쪽에서 못 올때
if i == 0:
left_up = 0
else :
left_up = dp[i - 1][j - 1]
#예외처리-아래에서 못 올때
if i == n - 1 :
left_down = 0
else :
left_down = dp[i + 1][j - 1]
left = dp[i][j - 1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n) :
result = max(result, dp[i][m - 1])
print(result)
🚩문제를 풀고 느낀점
결국 dp는 점화식을 구할려는 대상과 어떻게 하나씩 값을 변동시키며 해당 dp테이블을 업데이트 시킬까의 싸움이다
추가)bfs 같이 그래프 문제도 dp로도 풀릴 수 있다는 점!!
