❗️ 계속해서 업데이트 될 예정...
잘못된 부분이 있다면 알려주세요 🙏
다이나믹 프로그래밍
다이나믹 프로그래밍
다이나믹 프로그래밍은 아래와 같은 특징이 있는 문제들을 풀 수 있다.
- 최적 부분 구조 (ex- 최단 경로 찾기)
- 중복된 하위 문제들 (ex - 피보나치 수열)
방법론
- 상향식(타뷸레이션) : 하위 문제 -> 상위 문제
- 하향식(메모이제이션) : 상위 문제 -> 하위 문제
재귀 VS DP
재귀와 DP는 언뜻 보기에는 똑같은 알고리즘 같지만, 재귀 같은 경우에는 이전 값을 저장하는 공간이 없고, DP의 경우 이전 값들을 list나 dict에 저장한다.
다이나믹 프로그래밍 풀이
문제 1463
점화식
dp(N) = min( dp(N//3)+1, dp(N//2)+1, dp(N-1)+1 )
✏️ 내가 작성한 코드
# 타뷸레이션(상향식)
import collections
N = int(input())
dp = collections.defaultdict(int)
dp[1] = 0
for i in range(2, N+1):
dp[i] = dp[i-1] + 1 # 1을 빼주는 경우를 default로 잡는다.
if i%2 == 0 and dp[i] > dp[i//2]+1: # 2로 나누는 경우가 1를 빼주는 경우보다 작을 경우
dp[i] = dp[i//2] + 1
if i%3 == 0 and dp[i] > dp[i//3]+1: # 3로 나누는 경우가 1를 빼주는 경우 또는 2로 나누는 경우 보다 작을 경우
dp[i] = dp[i//3] + 1
print(dp[N])
# print('계산한 숫자 :', len(dp)) -> 10(N이 10일때)collections.defaultdict
collections모듈에는 다양한 객체가 존재하는데, 이 중defaultdict이라는 객체를 사용했다.
defaultdict는 빈dict를 생성하는데dict함수와의 차이점은 키가 없는 값은 모두null로 설정된다는 점이다.
즉,defaultdict로 생성된dictionary에 새로운 키를 호출해도KeyError가 발생하지 않고 초기값인null이 반환된다.
위 상황에서는 값을 default로int로 생성했기 때문에 초기값이0이 된다. (참고로int()는0이다.)
Reference
💡 흥미로운 코드
# 메모이제이션(하향식)
def dp(N):
if N in buf:
return buf[N]
m = 1 + min(dp(N // 2) + N % 2, dp(N // 3) + N % 3)
buf[N] = m
return m
buf = {1: 0, 2: 1}
N = int(input())
print(dp(N))
# print('계산한 숫자 :', len(buf)) -> 5(N이 10일때)
N%2N%3을 더해주는 것으로 1을 빼는 경우을 대신한다.
내 코드에서는 N보다 작은 모든 수를 다 계산하는 방식이라면 이 방법은 N을 기준으로 필요한 값만 계산하기 때문에 훨씬 속도가 빠르다.
문제 11726
점화식
dp(N) = dp(N-1) + dp(N-2)
✏️ 내가 작성한 코드
# 메모이제이션(하향식)
import collections
n = int(input())
buf = collections.defaultdict(int)
buf[1], buf[2] = 1, 2
def dp(n:int) -> int:
if n in buf:
return buf[n]
m = dp(n-1) + dp(n-2)
buf[n] = m
return m%10007
print(dp(n))💡 흥미로운 코드
import collections
n = int(input())
buf = collections.defaultdict(int)
for i in range(1, n+1):
if i == 1:
buf[i] = 1
elif i == 2:
buf[i] = 2
else:
buf[i] = buf[i-1] + buf[i-2]
print(buf[n]%10007)대표적인 DP 알고리즘인 피보나치 수열과 유사하다.
내 코드보다는 이 코드가 좀 더 직관적인거 같기도 하고..🤔
문제 11727
점화식
dp(N) = dp(N-1) + 2 X dp(N-2)
✏️ 내가 작성한 코드
# 메모이제이션(하향식)
import collections
n = int(input())
buf = collections.defaultdict(int)
for i in range(1, n+1):
if i == 1:
buf[i] = 1
elif i == 2:
buf[i] = 3
else:
buf[i] = buf[i-1] + 2*buf[i-2]
print(buf[n]%10007)💡 흥미로운 코드
n = int(input())
x, y = 1, 3
for _ in range(n-1):
x, y = y, 2*x+y
print(x%10007)두 변수만 이용해 공간을 절약할 수 있는 방법이다.
앞서 푼 모든 문제들도 따로 공간에 값들을 저장하지 않고 이렇게 두 변수만을 이용해 풀 수 있다.
시간 복잡도는 그대로이지만, 공간 복잡도가 O(n)에서 O(1)로 줄어든다.
문제 9095
점화식
dp(N) = dp(N-1) + dp(N-2) + dp(N-3)
✏️ 내가 작성한 코드
num = int(input())
for _ in range(num):
n = int(input())
if n == 1:
z = 1
elif n == 2:
z = 2
elif n == 3:
z = 4
else:
x, y, z = 1, 2, 4
for _ in range(n-3):
x, y, z = y, z, x+y+z
print(z)💡 흥미로운 코드
n = int(input())
arr=[1,2,4]
for i in range(4,11):
arr.append(sum(arr[-3:]))
for _ in range(n):
T = int(input())
print(arr[T-1])문제에서 n이 11이하의 양수라고 정의를 해서 11의까지의 모든 값들을
arr이에 담는 방식.
그래도 내 코드가 모든 값들을 저장하진 않으니 공간 효율면에서 좋은 듯..🤔
문제 10844
점화식
y = 1~8일 때, dp[x][y] = dp[x][y-1] + dp[x][y+1]
y = 0일 때, dp[x][y] = dp[x][y+1]
y = 2~8일 때, dp[x][y] = dp[x][y-1]
✏️ 내가 작성한 코드
import collections
N = int(input())
s = {0:1, 1:2, 2:2, 3:2, 4:2, 5:2, 6:2, 7:2, 8:2, 9:1}
if N == 1:
print(9)
else:
for _ in range(N-2):
dp = collections.defaultdict()
for i in range(10):
if i == 0:
dp[i] = s[i+1]
elif i == 9:
dp[i] = s[i-1]
else:
dp[i] = s[i+1] + s[i-1]
s = dp
print((sum(s.values())-s[0])%1000000000)💡 흥미로운 코드
N = int(input())
dp = [[0 for i in range(10)] for j in range(101)] # 0부터 100까지의 자연수 2차원 배열
for i in range(1, 10):
dp[1][i] = 1
for i in range(2, n + 1):
for j in range(10):
if j == 0:
dp[i][j] = dp[i - 1][1]
elif j == 9:
dp[i][j] = dp[i - 1][8]
else:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
print(sum(dp[n]) % 1000000000)문제 11057
점화식
dp[x][0] = sum[ dp[x-1][y] for y in range(10) ]
dp[x][y] = dp[x][y-1] - dp[x-1][y-1]
✏️ 내가 작성한 코드
N = int(input())
dp = [[0 for i in range(10)] for j in range(N)]
answer = 0
for i in range(10): # N = 1 일 때, 모두 1
dp[0][i] = 1
if N == 1:
print(10)
elif N > 1:
for x in range(1, N):
dp[x][0] = sum([dp[x-1][y] for y in range(10)])
for y in range(1, 10):
dp[x][y] = dp[x][y-1] - dp[x-1][y-1]
if x == N-1:
answer += dp[x][y]
print((answer + dp[N-1][0])%10007)N = 1 일 때, dp[0][0] ~ dp[0][9] 이고
N = 2 일 때, dp[1][0] ~ dp[1][9] 이기 때문에
답은 dp[N-1][0] ~ dp[N-1][9] 까지 더한 값이다.
💡 흥미로운 코드
N = int(input())
answer = 1
for i in range(9+N, 9,-1):
answer*=i
for i in range(1,N+1):
answer//=i
print(answer%10007)N = int(input())
dp = [1] * 10
for _ in range(N-1):
dp = [sum(dp[:i+1])%10007 for i in range(10)]
print(sum(dp)%10007)위에 코드는 아무리 봐도 왜 저렇게 짰는 지 모르겠다.😢
밑에 코드는 정말 짧고 (내 기준엔) 직관적이고 가장 파이썬스러운 코드가 아닌가 싶다.
N = 1일 때, dp1 = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
N = 2일 때, dp2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
N = 3일 때, dp3 = [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
이걸 보면 새로운 규칙을 찾을 수 있는 데, sum(dp1[:1]) = dp2[0] 이고, sum(dp1[:2]) = dp2[1] 이다.
세상엔 정말 똑똑한 사람이 많다...👍
문제 2193
점화식
현재 마지막 자리의 숫자가 0인 개수 = 이전 마지막 자리가 0인 개수 + 이전 마지막 자리가 1인 개수
현재 마지막 자리의 숫자가 1인 개수 = 이전 마지막 자리가 0인 개수
✏️ 내가 작성한 코드
N = int(input())
x, y = 0, 1
for _ in range(1, N):
x, y = x+y, x
print(x+y)문제 9465
점화식
index 0 index 1 index 2 index 3 index 4 50 10+30 100+max(100, 30) 20+max(120, 100) 40+max(210, 120) 30 50+50 70+max(40, 50) 10+max(200, 40) 60+max(140, 200) index 0 ~ index 1까지는 (50, 50) OR (30, 50) 말고는 선택지가 없다.
index 2부터는 전전 index와 전 index 값을 비교해서 큰 값을 선택한다.
✏️ 내가 작성한 코드
def dp():
n = int(input())
dp = [[int(i) for i in input().split()] for j in range(2)]
dp[0][1] += dp[1][0]
dp[1][1] += dp[0][0]
for p in range(2, n):
dp[0][p] += max(dp[1][p-2], dp[1][p-1])
dp[1][p] += max(dp[0][p-2], dp[0][p-1])
print(max(dp[0][n-1], dp[1][n-1]))
for q in range(int(input())):
dp()문제 2156
점화식
case1 = 현재 잔을 마시지 않고 이전 잔과 이이전 잔을 마신다.
case2 = 현재 잔과 이전 잔을 마신다
case3 = 현재 잔과 이이전 잔을 마신다.
✏️ 내가 작성한 코드
import sys
n = int(input())
wine = [0]
wine += [int(sys.stdin.readline().strip()) for i in range(n)]
dp = [0, wine[1]] # 최대로 많이 마실 수 있는 포도주의 양
if n > 1:
dp.append(wine[1]+wine[2])
for j in range(3, n+1):
case1 = dp[j-1] # 현재 포도주를 마시지 않음
case2 = dp[j-3] + wine[j] + wine[j-1] # 이전 포도주 + 현재 포도주 마심
case3 = dp[j-2] + wine[j] # 이이전 포도주와 현재 포도주 마심
dp.append(max(case1, case2, case3))
print(dp[n])💡 흥미로운 코드
import sys
f, s, t = 0, 0, 0
input()
for x in map(int, sys.stdin):
f, s, t = max(f, s, t), f + x, s + x
print(max(f, s, t))세 변수만을 사용해서 공간도 절약되고 간단한 코드이다.
나름 심플하게 풀어보려고 노력하는데 참..어렵다심플하게 풀어보려고 노력하는데 참..어렵다😂
문제 11053
점화식
현재 자신보다 이전 숫자가 작을 경우,
자신보다 작은 숫자들 중 가장 긴 길이를 구한 뒤 +1
✏️ 내가 작성한 코드
N = int(input())
arr = [int(i) for i in input().split()]
dp = [1]*N
for p in range(1, N):
for q in range(p):
if arr[p] > arr[q]:
dp[p] = max(dp[p], dp[q]+1)
print(max(dp))시간복잡도가
O(N**2)이여서 아쉽지만, 더 좋은 방법은 찾지 못했다.😞
문제 11055
점화식
현재 자신보다 이전 숫자가 작을 경우,
자신보다 작은 숫자들 중 합이 가장 큰 경우를 구한 뒤 + 현재 자신
✏️ 내가 작성한 코드
import copy
N = int(input())
arr = [int(i) for i in input().split()]
dp = copy.deepcopy(arr)
for p in range(1, N):
for q in range(p):
if arr[p] > arr[q]:
dp[p] = max(dp[p], dp[q]+arr[p])
print(max(dp))mutable(변경 가능한 객체) VS imutable(변경 불가능한 객체)
- mutable 객체는 값을 변경해도 메모리 주소 값이 변경되지 않는다.
- imutable 객체는 값을 변경할 수 없어 재할당을 해야하기 때문에 메모리 주소 값이 변경된다.
- mutable 객체는 b에 a를 할당하면 값이 할당되는 것이 아니라 같은 메모리 주소 값을 갖는다.
# mutable a = [1, 2, 3] b = a b[0] = 5 a # [5, 2, 3] 메모리 주소값: 4396179528 b # [5, 2, 3] 메모리 주소값: 4396179528# imutable s= "abc" # 메모리 주소값: 4387454680 s[0] = 's' """ Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'str' object does not support item assignment """ s = 'def' # 메모리 주소값: 4388970768
class 구분 list mutable set mutable dict mutable bool immutable int immutable float immutable tuple immutable str immutable copy : 깊은 복사(deep copy)와 얕은 복사(shallow copy)
mutable 객체 : 얕은 복사
imutable 객체 : 깊은 복사# 얕은 복사(shallow copy) import copy a = [[1,2],[3,4]] b = copy.copy(a) a[1].append(5) a # [[1, 2], [3, 4, 5]] b # [[1, 2], [3, 4, 5]]# 깊은 복사(deep copy) import copy a = [[1,2],[3,4]] b = copy.deepcopy(a) a[1].append(5) a # [[1, 2], [3, 4, 5]] b # [[1, 2], [3, 4]]
문제 11722
점화식
현재 자신보다 이전 숫자가 클 경우,
이전 숫자의 최대 길이 값+1
✏️ 내가 작성한 코드
N = int(input())
arr = [int(i) for i in input().split()]
dp = [1]*N
for p in range(1, N):
for q in range(p):
if arr[p] < arr[q]:
dp[p] = max(dp[p], dp[q]+1)
print(max(dp))문제 11054
점화식
가장 긴 바이토닉 부분 길이 = max( 증가하는 수열의 길이 + 감소하는 수열의 길이 )
✏️ 내가 작성한 코드
N = int(input())
arr = [int(i) for i in input().split()]
dp1 = [1]*N
dp2 = [1]*N
for x in range(1, N):
for y in range(x):
if arr[x] > arr[y]:
dp1[x] = max(dp1[x], dp1[y]+1)
for p in range(N-1, -1, -1): # 감소하는 길이를 구하기 위해서는 arr를 뒤에서 읽어야함.
for q in range(N-1, p, -1): # 앞부분은 증가 뒷부분은 감소여야 하기 때문
if arr[p] > arr[q]:
dp2[p] = max(dp2[p], dp2[q]+1)
print(max([dp1[i]+dp2[i]-1 for i in range(N)]))문제 1912
점화식
연속 배열 중 가장 큰 값 = max( 이전 값들의 합 + 현재 값, 현재 값 )
✏️ 내가 작성한 코드
import sys
N = int(input())
arr = [int(i) for i in sys.stdin.readline().split()]
dp = [0]*N
dp[0] = arr[0]
for x in range(1, N):
dp[x] = max(arr[x], arr[x] + dp[x-1])
print(max(dp))계속 시간초과가 떠서 뭔가 했더니 바보같이 for문을 두번 돌리고 있었다.
굳이 for문을 두번 돌리지않고 이전 값과 비교하는 것이니x-1를 하면 된다.
문제 2579
점화식
case1 : N, N-1 -> dp[i] = arr[i]+arr[i-1]+dp[i-3]
case2 : N, N-2 -> dp[i] = arr[i]+dp[i-2]
case3 : N-1, N-3 -> dp[i] = arr[i-1] + dp[i-3]
마지막 계단은 꼭 밝아야하기 때문에 case3 제외
✏️ 내가 작성한 코드
import sys
N = int(input())
arr = [0]
arr += [int(input()) for _ in range(N)]
dp = [0]*(N+1)
dp[1] = arr[1]
if N == 1:
print(dp[-1])
else:
dp[2] = sum(arr[1:3])
for i in range(3, N+1):
dp[i] = max(arr[i]+arr[i-1]+dp[i-3], arr[i]+dp[i-2])
print(dp[-1])문제 1699
점화식
d[N] = min(d[N], d[N-(q)]+1)
q: 제곱근 중 N 이하인 수
✏️ 내가 작성한 코드
N = int(input())
dp = [i for i in range(0, N+1)] # 0~N까지의 수를 1를 제곱근으로 한 개수
squared = [i*i for i in range(2, int(N**0.5)+1)] # 제곱근 중 N 이하인 수
for p in range(N+1):
for q in squared:
if q > p:
break
dp[p] = min(dp[p], dp[p-q]+1)
print(dp[-1])계속 시간 초과가 뜨길래 다른 사람들의 풀이를 살펴봤는데 pypy로 제출하면 통과한다.
최소값을 구하는 min 부분을 고치면 속도가 올라갈거같아if문을 사용해봤더니 파이썬으로 제출 가능하다. (단지 좀 많이 오래걸린다.)
N = int(input())
dp = [i for i in range(0, N+1)]
squared = [i*i for i in range(2, int(N**0.5)+1)]
for p in range(N+1):
for q in squared:
if q > p:
break
if dp[p] > dp[p-q]+1:
dp[p] = dp[p-q]+1
else:
dp[p] = dp[p]
print(dp[-1])문제 2133
점화식
dp[2] = 3
dp[N] = 2 + dp[N-2] X dp[2] + sum(dp[2], ..., dp[N-4]) X (N-(N-2))
✏️ 내가 작성한 코드
N = int(input())
dp = [0] * 31
dp[2] = 3
for i in range(4, N+1, 2):
dp[i] = 2 + dp[i-2]*dp[2] + sum(dp[:i-2])*2
print(dp[N])N이 홀수 일 때는, 0을 가지니 짝수 일 때만 계산하면 된다.
N이 2 일 때를 제외하고는 매 짝수번 일 때는 새로운 유형의 배치 방식이 2개가 추가된다.
그리고 이전 배치에서 크기가 2가 늘어나니, dp[2]를 이전 배치에 곱해줘야한다.
문제 9461
점화식
dp[1:5] = [1, 1, 1, 2]
dp[N] = dp[N-1] + dp[N-5]
✏️ 내가 작성한 코드
T = int(input())
dp = [0]*101
dp[1:5] = [1, 1, 1, 2]
for _ in range(T):
N = int(input())
for i in range(5, N+1):
dp[i] = dp[i-1] + dp[i-5]
print(dp[N])각 케이스마다 값을 적어보니 생각보다 점화식을 쉽게 찾을 수 있었다.
💡 흥미로운 코드
T = int(input())
dp = [0]*101
dp[1:5] = [1, 1, 1, 2]
for i in range(5, 101):
dp[i] = dp[i-1] + dp[i-5]
for _ in range(T):
print(dp[int(input())])어차피 dp 리스트를 101 개까지 만들었으니까 모든 경우의 수인 n이 100인 경우까지 다 구해 놓자.
N이 한 개라면 내가 짠 코드가 빠를 수 있지만, 지금 문제처럼 N이 여러 개라면 후자가 더 빠르다.
전자는 새로운 N을 다시 처음부터 구하는 반면에, 후자는 이미 다 구해 놓은 값을 출력만 하면 되기 때문이다.
문제 2225
점화식
dp[i][j] = dp[i][j-1] + dp[i-1][j]
✏️ 내가 작성한 코드
N, k = map(int, input().split())
dp = [[0]*201 for _ in range(201)]
for i in range(201):
dp[1][i] = 1
dp[2][i] = i + 1
for p in range(2, 201):
dp[p][1] = p
for q in range(2, 201):
dp[p][q] = dp[p][q-1] + dp[p-1][q]
print(dp[k][N]%1000000000)💡 흥미로운 코드
N, k = map(int, input().split())
dp = 1
for i in range(min(N,k-1)):
dp = dp * (N+k-1-i)//(i+1)
print(dp%1000000000)되게 간단한 코드인데 어떤 점화식을 토대로 이런 코드가 나왔는 지 모르겠다.😓
문제 1003
점화식
피보나치 점화식 : F[i] = F[i-1] + F[i-2]
fibo[i] = [fibo[i-1][0] + fibo[i-2][0], fibo[i-1][1] + fibo[i-2][1]]
✏️ 내가 작성한 코드
fibo = [[1,0], [0,1]] + [[]]*39
for i in range(2, 41):
fibo[i] = [fibo[i-1][j] + fibo[i-2][j] for j in range(2)]
T = int(input())
for _ in range(T):
N = int(input())
z, o = fibo[N]
print(z, o)피보나치 문제는 DP로 풀기!
