😀 냅색 알고리즘 활용
문제와 함께 이해하자
👻 동전교환 (냅색 알고리즘)
다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.
▣ 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다.
▣ 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.
▣ 입력예제 1
3
1 2 5
15
▣ 출력예제 1
3
코멘트
가방 문제(냅색 알고리즘)과 동일하게 적용하면 된다.
dp 테이블을 1차원으로 그려준 후에 dp[j]값이 무엇인지 생각해보자.
- j원을 거슬러주는데 사용된 동전의 최소 개수를 의미한다.
최솟값을 저장하기 때문에 처음에는 가장 큰 값을 dp 테이블에 저장해놓으면 된다 !
역시 똑같이 생각해보자. 1,2,5원이 있을 때 먼저 1원을 가지고 판단하자.
dp[j] 즉 j원을 거슬러줄 때 1원으로 거슬러주는 방법을 먼저 dp 테이블에 쭉 쓰는거야
dp[j-coin[i]] coin[i]가 1, j가 3이면 2원을 거슬러 주는데 사용되는 동전의 개수(dp[2]) + 1을 해준다. (+1은 coin[i]를 확정적으로 사용하는거니깐.)
-
1원이 끝나고 이제 2원에 대해서 다시 진행한다. 예를 들어 dp[j-coin[i]] j가 2원, coin[i]가 2원이면 dp[0] + 1의 값은 1이다. 이 값이 기존 dp[2]보다 작으니까 갱신된다.
-
이 과정을 모든 동전에 대해서 수행하면 된다 !
😀 그리고 dp 테이블 작성할 때 먼저 자명한건 값 초기화하고 시작하자 !
✈️ 해당 문제 코드
import sys
sys.stdin = open("input.text", "rt")
# input = sys.stdin.readline
n = int(input())
coin = list(map(int, input().split()))
m = int(input()) # 거슬러 줄 금액
INF = 2424242424
dp = [INF] * (m+1)
dp[0] = 0 #0원을 거슬러 주는데 0개가 필요. 자명한건 미리 초기화하고 시작.
for i in range(len(coin)):
for j in range(coin[i], m+1):
dp[j] = min(dp[j], dp[j-coin[i]] + 1) #기존의 값과 현재 적용하는 코인을 사용하는 경우의 최소값 중에 더 작은 값으로 갱신해
print(dp[m])🏈 최대점수 구하기(냅색 알고리즘)
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
▣ 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=100)과 제한 시간 M(10<=M<=1000)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다.
▣ 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다.
▣ 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4
▣ 출력예제 1
41
import sys
# sys.stdin = open("input.text", "rt")
# input = sys.stdin.readline
#제한시간 m안에 n개의 문제 중 최대점수 얻기
n, m = map(int, input().split())
#제한시간까지의 최대점수... dp 냅색 알고리즘?
#dp 테이블에는 제한시간 내 최대점수가 들어가야겠다.
data = []
for _ in range(n):
a,b = map(int, input().split()) #점수, 시간
data.append((a,b))
dp = [0] * (m+1)
for i in range(len(data)):
score, time = data[i][0], data[i][1]
for j in range(m, time-1, -1): # 제한시간 m부터 해당 문제의 시간인 time까지
dp[j] = max(dp[j], dp[j-time] + score) #현재 문제를 푼다고 가정했을 때의 최대점수 dp[j-time] + score
print(dp[m])💨 유형 분석
지금까지 풀어본 냅색 알고리즘 문제들, 가방문제, 동전교환 문제를 보면 가방문제는 한 종류의 보석을 무한개씩 써도 상관없고, 동전교환 문제 역시 한 동전을 무한개씩 써도 상관없었다.
- 이번에 알아볼 문제는 한 유형의 물건을 한개만 사용하는 조건이 붙은 문제이다 !!!
위 문제를 보면 한 유형의 문제는 딱 한번만 풀 수 있다 !!
이런 유형의 문제는 dp 테이블 2차원으로 풀어야 한다.
dp[i][j]에서 i는 i번째 문제까지 적용했다는 것을 의미하고, j는 주어진 시간을 의미한다.
- dp[i][j]는 i번째 문제까지 적용했을 때 j분까지 제한시간을 둘 때 얻을 수 있는 최대점수를 가진다.
⚽ 즉 dp[3][15]는 3번째 문제까지 적용했을 때 그렇게 해서 나한테 주어진 시간이 15일 때 얻을 수 있는 최대점수를 기록하는 것이다 !!
- dp[i]에 대해 구할 때 dp[i-1]에 대해서 참조해야해
⚽ 원래는 중복을 피하기 위해 2차원으로 푸는게 맞아. 하지만 n,m이 너무 커지면 푸는데 공간복잡도 시간복잡도가 복잡해진다. 실전에서는 1차원 dp 테이블로 풀어야 해 !
- 그렇다면 어떻게 1차원 dp 테이블로 풀어야할까?
🏈 먼저 1차원 dp 테이블을 준비하자. dp[j]는 j라는 시간이 나에게 주어졌을 때 얻을 수 있는 최대 점수를 기록하는 것이다.
-
앞에서부터 전진하면서 dp를 적용하면 무조건 중복 적용이 된다. 그런데 뒤에서부터 적용한다면 ?
-
뒤에서부터 앞으로 오면서 다이나믹 프로그래밍을 적용하면 중복이 되지 않는다.
- 참조를 뒤에서부터 하면 아직 바뀌지 않은 값을 적용하기 때문에 (즉 이전 문제까지의 최대 점수들만 참조 가능) 중복이 안돼. 그렇기에 원하는 결과 도출 가능하다.
- 예를 들어 j == 15, 15분이 주어졌을 때의 최대 점수를 구할 때 이미 j>15인 dp값들은 적용이 됐기 때문에 중복이 되지 않는다 !
-
그래서 앞전 문제에서부터 중복 가능한 문제더라도 반복문을 뒤에서부터 적용해줬던 것이다.
