꺼내먹는지식 준
다이나믹 프로그래밍 본문
다이나믹 프로그래밍
컴퓨터로 해결하기 어려운 문제는 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제들이 해당된다.
특정 문제들을 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.
대표적 방법이 바로 다이다믹 프로그래밍이다.
(동적 할당이란 '프로그램이 실행되는 도중'에 필요한 메모리를 할당하는 기법이다. 하지만 다이나믹 프로그래밍의 다이나믹은 이 정의에 해당되지 않는다.)
다이나믹 프로그램의 대표적 예시
피보나치 수열
점화식은 수열의 항이 이어지는 형태를 간결하게 표현한다.
피보나치 수열의 점화식은 다음과 같다.
$$a_{n+2} = f(a_{a+1}, a_n) = a_{n+1} + a_n$$
$$a_1 = 1, \, a_2 = 1$$
기존 우리가 배운 방법으로 피보나치 수열을 해결한다면 재귀함수를 사용할 것이다.
해당 경우 $fib(7)$ 은 아래의 그림과 같이 해결이 된다.
동일한 연산이 계속해서 반복되는 것을 알 수 있다.
피보나치 수열의 시간 복잡도는 $/theta( 1.618...^N )$ 이라고 한다. 하지만 빅오 표현식으로 단순화 하여 $O(2^N)$ 과 같이 표현한다. 만약 N = 30 이면, 약 10억 가량의 연산이 수행된다.
즉, 반복적인 연산을 통해 10억번의 연산을 하는 것은 너무나 큰 자원낭비다. N = 100 이라면 현대 컴퓨터로는 도저히 개산이 불가능하다.
그러나 피보나치 수열을 살펴봐서 알겠지만, 사실상 N = 100 이어도 다른 숫자가 등장하는 경우는 100번 외에는 없다. 즉 동일한 수를 다시계산하는 과정이 반복된다.
이 때 다이나믹 프로그래밍을 사용한다.
다이나믹 프로그래밍은 다음의 조건을 만족할 때 사용가능하다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모이제이션
다이나믹 프로그래밍을 구현하는 방법 중 한 종류
한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
메모이제이션은 값을 저장하는 방식이므로 캐싱이라고도 한다.
예제
import sys
input = sys.stdin.readline
N = int(input())
d = [0] * 100
def fib(n):
if n == 1 or n == 2:
return 1
if d[n] != 0:
return d[n]
d[n] = fib(n-1) + fib(n-2)
return d[n]
print(fib(N))fib(1 .. 9) 가 먼저 채워지고 나면, 그 이후로는 반복할 일이 없어서 필요 연산 수가 기하급수적으로 줄어든다.
아래를 참고하자.
분할정복(divide and conquer) 즉, 큰 문제를 작은 문제로 작게 나누는 방법은 퀵 정렬에서도 소개된 적 있다. 그러나 분할 정복과 다이나믹 프로그래밍의 차이는 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다.
이 처럼 다이나믹 프로그래밍은 반복되는 연산 횟수를 기하급수적으로 줄여주는데, 다만 재귀 함수를 사용하면 컴퓨터 시스템에서 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드가 발생하곤 한다. 이에 따라 반복문을 사용하면 오버헤드를 줄일 수 있고, 반복문 자체가 성능이 주로 더 좋다.
다이나믹 프로그래밍으로 해결한 피보나치 수열 알고리즘의 시간 복잡도는 $O(N)$ 이다.
탑다운 보텀업 방식
탑다운: 큰문제를 해결하기 위해 작은 문제를 호출
보텀업: 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근 차근 답을 도출
보텀업 방식으로 피보나치 수열을 해결하면 다음과 같다.
d[1] = 1
d[2] = 1
ans = 0
for i in range(1, N-1):
d[i+2] = d[i] + d[i+1]
print(d[N])
보텀업 방식에서 사용되는 결과 저장용 리스트는 'DP 테이블' 이라고 부르며, 메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.
메모이제이션 팁
- 메모이제이션은 엄밀히 말하면 한번 계산된 결과를 어딘가에 담아놓는 행위 자체를 의미하므로 꼭 다이나믹 프로그래밍과 관련이 있지는 않다.
- 수열처럼 연속적이지 않은 경우 사전(dict) 자료형을 사용하는 것이 효과적일 수 있다.
다이나믹 프로그래밍 유형 팁
- 주어진 문제가 다이나믹 프로그래밍 조건에 해당하는지 확인한다.
- 단순히 재귀 함수로 비효율적으로 작성한 후, 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, (즉 메모이제이션이 가능하면) 소스코드를 수정한다.
- 더나아가 가능하면 재귀 함수보다는 보텀업 방식으로 구현한다. (재귀함수는 스택 크기가 한정되어있다.) sys.setrecursionlimit() 함수 호출로 재귀 제한을 완화할 수 있다.
실전 예제
1) 1로 만들기
정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.
- X가 5로 나누어떨어지면, 5로 나눈다.
- X가 3로 나누어떨어지면, 3로 나눈다.
- X가 2로 나누어떨어지면, 2로 나눈다.
- X에서 1을 뺀다.
정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려 한다. 연산 사용의 최솟값은?
재귀
import sys
input = sys.stdin.readline
N = int(input())
lst = []
def oper(n, cnt, lst):
if n == 1:
lst.append(cnt)
return lst
if n % 5 == 0:
oper(n/5, cnt+1,lst)
if n % 3 == 0:
oper(n/3, cnt+1,lst)
if n % 2 == 0:
oper(n/2, cnt+1,lst)
return oper(n-1, cnt+1,lst)
oper(N, 0, lst)
print(len(lst))
print(min(lst))
해당 문제는 X 의 범위가 (0 < X < 30,002 ) 이다.
재귀 함수로만 풀려고 하면 다음과 같은 상황이 벌어진다.
X = 50 일 때, 총 2352번의 연산이 일어나고,
X = 200 일 때, 총 791862번의 연산이 일어난다.
이미 200 번만 해도 연산이 약 100만번에 이르므로 해당 방법으로는 문제를 풀 수 없다.
해당 문제는 다이나믹 프로그래밍으로 해결을 해야 한다.
규칙은 다음과 같다.
마치 피보나치와 같이 특정 값에 여러 연산이 적용될 수 있어도 결국 같은 수에 대한 결과는 같다.
탑다운
d = [0] * 30001
def oper(n):
if n == 1:
return 0
if d[n] != 0:
return d[n]
d[n] = oper(n-1) + 1
if n % 5 == 0:
d[n] = min(oper(n//5) + 1, d[n])
if n % 3 == 0:
d[n] = min(oper(n//3) + 1, d[n])
if n % 2 == 0:
d[n] = min(oper(n//2) + 1, d[n])
return d[n]
oper(N)
print(d[N])메모이제이션 기법으로 반복되는 내용을 저장하고 푼 방식이다.
재귀만 사용한 방법과 동작 시간을 비교해보면 아래와 같다.
X = 50, 재귀 기법: 0.00233 메모이제이션: 0.000193
X = 200, 재귀 기법: 0.27059 메모이제이션: 0.00100
X = 300, 재귀 기법: 2.008 메모이제이션: 0.00095
X = 350, 재귀 기법: 4.589 메모이제이션: 0.001416
X = 400, 재귀 기법: 9.776 메모이제이션: 0.001255
시간이 지날 수록 더 큰 차이가 난다.
재귀만 사용하면 X = 500 을 구하기도 힘들지만, 메모이제이션 기법으로는 금방 구할 수 있다.
다만 문제는
X = 1000 일때를 구해보고자 하면 recursion depth 문제가 발생한다.
이 때, sys.setrecursionlimit() 함수를 사용하면 depth 를 완화하여 해결 가능하다.
sys.setrecursionlimit(10 ** 6)X = 1000 메모이제이션 0.0023200
X = 29000 메모이제이션 0.03386
X = 30000 Segmentation fault: 11 recursion depth 를 상당히 깊게 설정했음에도 불구하고 깊이가 걸렸다.
감당할 수 없는 깊이일 때 Segmentation fault가 나온다고 한다.
즉, 해당 문제는 recursion 으로 해도 tough한 케이스에서 걸리고 만다.
위에서 배웠듯이 다음의 탑다운 방식은 보텀업 방식으로도 구현 가능하므로 살펴보자.
※ 재귀로 구현할 때 유의사항
재귀함수를 구현할 때 함수를 어떻게 어디부터 짜야하나 햇갈리곤 한다. 그때 다음의 항목을 기억하면 구해야 하는 초점에서 벗어나지 않고 중점을 잘 지킬 수 있을 것 같다.
- 내가 구하고자 하는 것이 무엇인지 파악
현재 내가 구하고자 하는 것은 최소 횟수이다. 즉, 횟수를 재귀함수를 통하여 찾고자 한다.
- 종료 조건
종료 조건때 무엇을 return 할 것인가도 중요하다.
- 각 조건에 따른 return
위 문제의 경우 recursion 을 call 할 때마다 count 를 증가시켜 파라미터로 넘겨줌으로써 종료조건 때 해당하는 count 를 return 해줄 수도 있다. list 에 저장해서 min 을 취해줘도 충분히 값을 찾을 수는 있다.
하지만, 이 경우 각 조건에 따라 count 는 올려주되 최종적으로 무엇을 return 할지 명확하지 않다.
또한, 재귀함수의 철학에 맞지 않아 보인다. 물론 코딩을 통해 효율적이지 않은 방법으로도 구현을 할 수 있지만, 각 기법은 최대의 효율을 위해 고안된 방법론이다. 즉 고안될 때 특정 사용방법을 위해 고안되었는데 다른 방법으로 사용하면 비효율적일 확률이 높다. 재귀를 통해 종료조건의 return 에서 부터 stack에 있는 함수들을 차근 차근 빼내며 우리가 원하는 답에 가까워진다고 할 때, 매번 함수콜에서 count 를 키워주는 것은 재귀 함수에 대한 올바른 이해랑 거리가 멀다. 즉 위 구현과 같이 종료조건의 return 으로 부터 매번 함수 콜에서 더해나가는 것이 올바른 방법이다.
다음을 기억하고 있으면 재귀함수를 구현하는 것이 쉽다.
위 내용이 정리되지 않아 매번 재귀함수가 어려웠는데 머리속에 정리가 되고 나니 재귀함수가 오히려 다른 함수보다 쉽게 다가온다.
보텀업
#when n = 1
d[1] = 0
def oper(N):
for i in range(2, N+1):
if d[i] != 0:
continue
d[i] = d[i-1] + 1
if i % 5 == 0:
d[i] = min(d[i//5] + 1, d[i])
if i % 3 == 0:
d[i] = min(d[i//3] + 1, d[i])
if i % 2 == 0:
d[i] = min(d[i//2] + 1, d[i])
return d[N]
print(oper(N))
코드 개선
d[1] = 0해당 블록은 생략 가능 (초기화시 0으로 생성하였다.)
if d[i] != 0:
continue해당 블록은 사용하는 의미가 없다.
어차피 바톰업 방식으로 차근 차근 채워나갔기 때문에 미리 채워서 반복 사용하는 경우가 없다.
X = 29000 메모이제이션 0.03386 보텀업 방식: 0.0001070
실제 동작 속도를 비교해보면 바톰업이 훨씬 빠른 걸 알 수 있다.
코딩 테스트에서 시간이 남으면 탑다운을 바톰업으로 구현하는건 언제나 좋은 선택이 될 수 있을 것 같다.
지금까지 경험으로 미뤄봤을 때는 머리속 논리를 정리하며 탑다운으로 구현하고 그 후 바톰업으로 접근하는 것이 맞는 것 같다.
2) 바닥 공사
가로 길이 N, 세로 길이 2인 직사각형 형태의 얇은 바닥이 있다.
이 바닥을 1 X 2 덮개, 2 X 1 덮개, 2 X 2 덮개를 이용해 채우고자 한다.
이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하라.
해당 문제를 읽으면 그리디로 해결이 불가능한것이 느껴진다. brute force 로 접근해야 하지만, 모든 경우의 수를 반복하면 시간이 너무 오래걸리므로 어딘가에 내용을 저장하며 풀어야 한다는 것을 느낄 수 있다.
일단 다음의 두가지 발견을 했다.
1 X 2 는 한번 쓰이면 무조건 아래에 같이 채워 쓰여야 한다.
2 X 1 는 N 이 홀수이냐 짝수이냐에 따라 쓰일 수 있는 개수 정도가 다르다. 만약 N 이 1개가 남으면 2 X 1 로 채워야 한다.
탑다운 실패사례
import sys
input = sys.stdin.readline
import time
N = int(input())
d = [0] * 1001
start = time.time()
#저장해야 하는 것이 최소 횟수가 아니라
#가능한 경우의 수를 저장해야 한다 .
def oper(n):
if n == 0:
return 0
if d[n] != 0:
return d[n]
d[n] = oper(n-1) + 1
if n > 1:
d[n] += oper(n-2) + 2
return d[n]
end = time.time()
oper(N)첫 풀이 시도
해당 문제는 오랜 기간 고민이 필요했다. 우선적으로 해당 문제에서 구하고자 하는 바를 찾았다.
가능한 모든 경우의 수에 대해 파악이 필요하다.
별다른 점화식 없이, 2 X 1 는 ( N - 1 ) 을 재귀로 다시 호출하고 시행 시도에 + 1 하면 된다고 생각했다.
하지만 이는 치명적인 생각 오류가 있었다.
다음은 타일을 채우는 방법 중 1가지이지만, 내 알고리즘으로는 4가지 방법으로 판단한다.
이로 인해 기껏 떠올린 알고리즘은 (2 X 1) 타일이 반복될 때는 count 를 올리지 않는 것이다.
이를 구현하기 위해서는 매번 재귀함수에서 parameter를 던져 전 단계가 (2 X 1) 타일이었는지 아닌지 판별해줘야 한다.
또한 (2 X 1) 다음의 두가지 경우의 수는 기존의 경우의 수를 2배 만큼 해주는 것이지 +1 하는 것이 아니다.
전반적으로 정리가 잘 안된다.
이럴 때는 점화식을 세워야 한다고 한다.
그림을 그려 살펴보면 규칙이 보인다. 바로 전 단계의 양쪽에 한번씩 전전 단계의 타일을 붙인 것과 동일하다.
점화식을 세우면 $a_i = a_{i-1} + a_{i-2} + a_{i-2}$ 이다.
다이나믹 프로그래밍이 점화식을 세우는 것이 우선순위인 경우가 있다는 것을 배웠다.
탑다운
import sys
input = sys.stdin.readline
N = int(input())
# 2 X N
d = [0] * 1001
d[1] = 1
d[2] = 3
def oper(n):
if n == 0:
return 0
if d[n] != 0:
return d[n]
d[n] = oper(n-2) * 2 + oper(n-1)
return d[n]
oper(N)
print(d[N])재귀로 풀 때 유의점을 다시한번 정리해보자
- 종료 조건
- 메모이제이션
- d[n] 에 대한 정의
보텀업
for i in range(3, N+1):
d[i] = d[i-2] * 2 + d[i-1]
print(d[N])3) 개미전사
N개의 식량창고가 일직선으로 이어져있다. 각 식량창고는 각 정해진 수의 식량을 저장한다. 개미전사는 식량 창고를 선택적으로 약탈한다. 일직선상 식량창고 중 서로 인접한 창고를 공격할 수는 없다. 최대로 약탈할 수 있는 식량의 최댓값은?
입력: 일직선상의 식량창고
N (4)
3 <= N <= 100
1 3 1 5
출력: 최댓값
8
탑다운 첫 풀이
import sys
input = sys.stdin.readline
N = int(input())
food = list(map(int,input().split()))
food.insert(0,0)
d = [0] * 101
def oper(n):
if n == 0:
return 0
if n == 1:
return food[1]
if n == 2:
return max(food[1], food[2])
if d[n] != 0:
return d[n]
# 4개 이상일 때 가능
d[n] = oper(n-2) + food[n]
if n > 3:
d[n] = max(d[n], oper(n-3) + food[n])
return d[n]
oper(N)
tmp = d[N]
oper(N-1)
tmp = max(d[N-1], tmp)
print(tmp)처음한 구현이다. 해당 구현도 무리없이 답은 맞추는 듯 하나 다시 살펴보는 과정에서 몇가지 오류를 발견했다.
1) 시작점을 두개로 잡아야 한다는 판단
각 원을 $a_1, a_2, a_3, a_4, a_5 ... $ 라 할 때,
만약 $a_1$ > $a_2$ 라면 문제가 없다.
하지만 $a_2 > a_1$ 이라면 대소 비교가 어렵다.
$a_1 + a_3 + a_5$ 와 $a_2+a_5$ 의 대소비교를 첫번째로 해야 하고,
두번째로 $a_1 + a_3 + a_5$ 와 $a_2 + a_4$의 대소비교가 필요하다.
두번째 대소비교는 그 이후로도 $a_6$ .. 이런식으로 계속해서 구분이 필요하다.
내가 생각한 알고리즘은 시작점은 두개로 잡을 수 밖에 없다는 것을 확인
2) n == 2일 때 1번과 2번 element 대소비교 착각
n == 2 일때 1번과 2번 element 를 굳이 대소 비교하여 더 큰 element 를 반환하도록 했었다. 물론 연산 숫자에 별 차이가 없기는 하나 실제로 필요 없는 구현이다.
그림으로 살펴 보면 (n-2), (n-3) 두 재귀함수 중 한 곳에 걸린 경우이다.
일단 4번째 줄의 경우에는 (5, 3, return 1) 에 걸리므로 더 큰 경우가 발생해서 고려하지 않아도 된다.
그러면 1,2,3 번째 줄만 고민하면 된다.
1번째 줄의 경우에는 어차피 5 에서 (n-3) 재귀함수의 return 2 이므로 재외한다.
2, 3번째 줄만 고려하면 된다.
2번째 줄은 사실 4에서 (n-3) 재귀 함수에 걸린다. 즉 4 + 1 을 따로 해주지 않아도 자동으로 수행된다.
3번째 줄은 (n-2)에 걸려 n == 2 를 만든 경우인데 2번째 줄이 해결되었으므로 따로 고려해주지 않아도 된다.
즉, 별다른 고민 안해도 (n-2), (n-3) 의 재귀함수에서 다 잘 처리된다. 재귀함수에 아직도 덜 익숙해서 하는 실수같다.
결론 떠올린 알고리즘이 작동은 하는 듯 하나 비효율적인 것 같다.
결국 다른 블로그 글들을 참고해본다.
해당 문제는 결국
(n-2) 까지의 최대값과 + n 번째 원소 값 vs (n-1) 원소까지의 최대값
를 비교하면 된다.
이를 기반으로 turu 블로거 님이 작성하신 점화식은 위와 같다.
$f(n) = max(f(n-2) + a_n, f(n-1))$
즉 위와 같이 $a_1 + a_3$ 과 $a_2$ 를 비교하면 되는 문제이다.
내가 세웠던 점화식은 $max(f(n-2) + a_n, oper(n-3) + a_n)$ , $max(f((n-1)-2) + a_n, oper((n-1)-3) + a_n)$ 로 차선이긴 하지만 가장 적절한 점화식을 바로 발견하지 못했던 것이 문제였다.
이를 기반으로 다시 작성해보면
탑다운 정식 풀이
import sys
input = sys.stdin.readline
N = int(input())
food = list(map(int,input().split()))
food.insert(0,0)
d = [0] * 101
def oper(n):
if n == 0:
return 0
if n == 1:
return food[1]
if n == 2:
return food[2]
if d[n] != 0:
return d[n]
d[n] = max(oper(n-1), oper(n-2) + food[n])
return d[n]
oper(N)
print(d[N])훨씬 간단하고 명료하게 작성된다.
이번에 내가 바로 핵심을 파악하지 못했던 이유를 분석해보면
- d[n] 정의를 재대로 하지 못했다.
- d[n] 정의한 후, n 에 (1,2,3,4) 정도만 눈으로 넣어봐도 잘 작동하는지 확인 가능하도록 짜여야 한다.
바텀업
d[1] = food[0]
d[2] = max(food[0], food[1])
for i in range(3, N+1):
d[i] = max(d[i-1], d[i-2]+food[i])
print(d[N])확실히 바텀업이 짧고 명료하다.
실험 결과 무지성으로 풀이했던 첫 탑다운 시도도 제한 시간 내에 답을 찾는데는 지장이 없다는 것을 확인했다. DP 는 언제나 명확한 규칙을 확인하고, n = (1,2,3,4) 정도는 시도해보고 덤벼야 할 것 같다.
예시)
N = 10
8 3 9 1 2 7 3 9 2 7
출력: 40
N = 100
40 4 32 12 78 78 22 30 16 94 42 52 77 12 87 90 29 70 34 19 63 77 84 55 39 23 24 79 53 51 72 22 65 56 15 20 27 71 97 35 5 1 46 53 29 34 19 62 69 16 62 70 37 13 6 5 84 2 30 90 72 98 90 61 46 1 39 7 69 62 21 8 18 50 41 40 88 56 51 91 30 6 95 18 84 20 65 40 50 1 73 58 15 22 32 67 62 52 8 83
출력: 2616
4) 효율적인 화폐 구성
N 가지 종류의 화폐
화폐 개수를 최소한 활용해서 가치의 합이 M 원이 되도록 한다.
화폐는 몇개라도 사용 가능, 구성은 같지만 순서만 다른 것은 같은 것으로 구분한다.
$1 \leq N \leq 100$
$1 \leq M \leq 100,00$
입력:
2 15 (N M)
2
3
출력: 5 (3원 5장)
탑다운
import sys
input = sys.stdin.readline
N, M = map(int,input().split())
lst = []
for i in range(N):
lst.append(int(input()))
d = [10001] * (M+1)
def oper(n):
if n == 0:
return 0
if n < 0 :
return 10001
if d[n] != 10001:
return d[n]
d[n] = oper(n-lst[0]) + 1
for i in lst[1:]:
d[n] = min(oper(n-i)+1, d[n])
return d[n]
oper(M)
print(d)
print(d[M])[10001, 10002, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 10001, 5]
5
어려웠지만 처음부터 코드는 잘 짜졌다.
다만,
if n<0:
return 100001이 부분을 떠올리기 어려웠다.
즉, 해당 문제는 min 을 구하는 문제이므로 d list 초기화를 0 이 아닌 최대 값으로 해줘야 한다.
그 후, 다이나믹 프로그래밍으로 풀 때 여러 조합으로 맞춰보던 도중 실패하는 경우가 당연히 발생하고 그 경우에는 최종 목표값인 0에 도달하지 못한다.
그때는 0에 도달하지 못하고 -1 값에 도달하게 된다. 이 때는 return 값을 10001 로 처리해줘서 어떻게 해도 해당 가격에 대하여 오버된 값이 들어가지 못하도록 한다.
바텀업 첫 구현
lst.sort()
for i in lst:
d[i] = 1
print(lst[-1])
for i in range(lst[-1]+1,M+1):
d[i] = d[i - lst[0]] +1
for j in lst:
d[i] = min(d[i], d[i - j] + 1)
print(d)
print(d[i])[10001, 10001, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5]
5생각보다 탑다운에서 바텀업으로 아이디어를 전이하기 어려웠던 문제다.
아이디어를 잘 못 잡아서 완전 잘 못 구현했다.
easy case 에서는 문제가 없었지만
예를 들어 M = 1007, 화폐가 2,3,4000 이면?
for i in range(4000+1, M+1):
d[i] = d[i - 2] +1
d[i] = min(d[i], d[i - 3] + 1)
d[i] = min(d[i], d[i - 4000] + 1)
4000 부터 시작하여 앞부분의 array 가 채워져있지 않아 아예 풀 수가 없다.
즉, array를 앞부분 부터 차근 차근 채우는 것이 문제의 골자이다.
탑다운을 보텀업으로 변경할 때 유의사항은 실제 동작 횟수는 동일한가이다.
지금은 동작 횟수가 확 줄어들었으므로 문제가 많다.
d[0] = 0
#아예 0 부터 시작되도록 한 식
for i in lst:
for j in range(i, M+1):
if i > M:
continue
if(d[j-i] != 10001):
d[j] = min(d[j] ,d[j-i] + 1)
print(d[M])
다음과 같이 수정해야 한다. i 가 M 보다 큰 경우는 생략한다.
이로서 dynamic programming 기본기를 학습했다.
이제 쉬울 것 같으면서도 매번 꽤 어렵다는 걸 깨닫는다.
'코딩테스트총정리' 카테고리의 다른 글
| 최단 경로 - 플로이드 워셜 알고리즘 (0) | 2022.08.14 |
|---|---|
| 최단 경로 - 다익스트라 (0) | 2022.08.11 |
| 탐색 (순차, 이진) (0) | 2022.08.06 |
| 정렬 (0) | 2022.08.03 |
| DFS, BFS (0) | 2022.08.03 |
