다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘이다.
다이나믹 프로그래밍은 다음과 같은 가정하에 사용할 수 있다.
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정담은 큰 문제에서도 동일하다.
즉, 수학의 점화식을 구하여 그 그 값을 저장하므로써, 이전 값들을 통해 값을 빠르게 구하는 방법이다.
그럼 우리가 해야할 것은 무엇인가?
바로 일반항 구하기.
처음 dp를 만난 것은 아마도 9095번일 것이다.
이걸 그냥 풀려고 해보니, 자연수 분할인가 싶기도 하고, 경우의 수를 구하는 문제인가 싶기도 해서 엄청 해맸다.
n번항에 알맞는 규칙이 있을 거라고 생각하고 푸니까 막혀서 진행이 안됐었다.(한 3시간 넘게 고민했다.)
그렇게 구글링을 하다보니 dp에 대해 알게됐고, 노가다의 흔적들에서 규칙을 찾을 수 있었다.
N(k)=N(k-1)+N(k-2)+N(k-3)
def dp(n):
if n==1:
return 1
elif n==2:
return 2
elif n==3:
return 4
else:
return dp(n-1)+dp(n-2)+dp(n-3)
T=int(input())
for _ in range(T):
n=int(input())
print(dp(n))이건 요로코롬 재귀함수를 통해 풀었다.
다음으로 만난 dp문제
이 문제부터 경우를 갈라서 dp값을 구해줘야 했다.
위의 문제에서는
N(k)의 최소 연산수는
1. k가 2로 나눠질 경우에 N(k//2)+1(k를 이미 2로 나눴으므로)
2. k가 3으로 나눠질 경우에 N(k//3)+1(k를 이미 3으로 나눴으므로)
3. N(k-1)+1(k보다 1보다 작은 값에 1만 더해주면 되므로)
이다.
따라서 코드는
dp=dict()
dp[1]=0
dp[2]=1
dp[3]=1
n=int(input())
for x in range(4,n+1):
dp[x]=dp[x-1]+1
if x%2==0:
dp[x]=min(dp[x//2]+1, dp[x])
if x%3==0:
dp[x]=min(dp[x//3]+1, dp[x])
print(dp[n])여기서 주의점은 위의 if 두개를 if와 elif로 교체하면 안된다는 점이다. 왜냐하면 6으로 나눠지는 경우도 있기 때문이다.
재귀함수로 짜는게 생각보다 어려워서 딕셔너리를 사용했다.
다음은 9461번
그림을 그리다보면
N1 : 1
N2 : 1
N3 : 1
N4 : 2
N5 : 2
N6 : 3
N7 : 4
N8 : 5
N9 : 7
N10 : 9
N11 : 12
이고, 잘 뜯어보면 6번부터
N6=N5 + N1
N7=N6 + N2
N8=N7 + N3
N9=N8 + N4
즉, N(k)=N(k-1)+N(k-5)의 규칙을 갖는 것을 찾을 수 있다.
따라서
def dp(n):
dp=[0]*101
dp[1],dp[2],dp[3],dp[4],dp[5]=1,1,1,2,2
for x in range(6,n+1):
dp[x]=dp[x-1]+dp[x-5]
return dp[n]
T=int(input())
for _ in range(T):
n=int(input())
print(dp(n))다음은 11726번
뭔가 괴랄한 확률과 통계 문제 같은 느낌에 쫄 수 있지만 그럴 것 없이 찬찬히 풀어보자.
n(1)=1
n(2)=2
n(3)=3
n(4)=5
n(5)=8
.....
어라? 이거 어디서 많이 본 건데 싶다.
네.. 피보나치 수열이었습니다~
n=int(input())
dp=[0,1,2]
for x in range(1,n):
dp.append(dp[x]+dp[x+1])
print(dp[n]%10007)뭔가 허전한 코드...
10007로 나눈 나머지 출력하는 건지 몰라서 한 번 틀렸다.
이 문제, 내가 풀어본 dp문제 중 가장 어려웠다.(몇 문제 안풀어봤음)
숫자로 주어지면 하나하나 차근차근히 경우를 증가시켜보면서 해보는데, 이런 유형의 문제는 시도할 엄두를 못내고 구현할 생각에 빠져서 dp인지도 파악을 못한다.
솔직히 감 잡기도 어려웠다.
그래도 찬찬히 해보자면
계단의 수가 1일때는 (계산의 값을 n[x]라고 하자)
dp[1]=n[1]이다.
계단의 수가 2일때,
dp[2]=n[1]+n[2]
계단의 수가 3일때 부터 경우가 달라진다.
세개 연속으로 계단을 오르지 못하기 때문에 1,3번 계단 또는 2,3번 계단에서 구해야한다.
dp[3]=max(n[1]+n[3], n[2]+n[3])
4번째부터 좀더 상황이 구체화된다.
마지막 블록은 무조건 밟아야 하므로, 뒤에서 부터 체크한다.
두칸 올라왔을 경우(검정 경우), 그리고 세칸 밑을 거쳐 한칸 밑을 올라왔을 경우(하늘색 경로)다.
따라서 4번째의 식은
dp[4]=max(n[1]+n[3]+n[4],n[2]+n[4])
이것을 일반화 해보자.
검정의 경우 두칸 밑의 계단을 무조건 지난다.
그렇다면 두칸 밑의 계단을 최대로 올라오는 경우에 마지막 값만 더해주면 되지 않을까?
식으로 나타내면
dp[k]=dp[k-2]+n[k]
그리고 하늘색의 경우 세칸 밑과 한칸 밑을 반드시 지난다.
그렇다면 세칸 밑의 계단을 최대로 올라오는 경우에 한칸 밑의 계단값과 최종값을 더해주면 구현이 가능하다.
식으로 나타내면
dp[k]=dp[k-3]+n[k-1]+n[k]
코드로 표현하면
n=int(input())
a=[0 for t in range(n+3)]
dp=[0 for t in range(n+3)]
for t in range(1,n+1):
a[t]=int(input())
dp[1]=a[1]
dp[2]=a[1]+a[2]
dp[3]=max(a[1]+a[3],a[2]+a[3])
for x in range(4,n+1):
dp[x]=max(dp[x-2]+a[x], a[x-1]+dp[x-3]+a[x])
print(dp[n])
dp문제는 절대 쫄면 안된다.
쫄지말고 하나씩 전개하다보면 규칙을 찾을 수 있다.
