🎀 본 게시물은 코딩테스트를 위한 자료구조, 알고리즘 공부 게시물입니다. 또한 다음 강의자료를 사용했음을 알려드립니다.

인프런강의 🎀

---

냅색 알고리즘에 대해 알아보고 예시 문제를 통해 익히자.

냅색 알고리즘이 뭐지?

냅색 알고리즘은 한정된 가방에 최대한 많은 물건을 담아야 할 때, 각 물건의 가치와 부피를 고려하여 어떤 물건들을 선택해야 최대 가치를 얻을 수 있는지를 구하는 알고리즘입니다.

냅색 알고리즘은 0/1 냅색문제와 Fractional 냅색문제로 나뉩니다. 0/1 냅색문제는 물건을 담거나 안담거나 둘 중 하나만 선택할 수 있는 문제이고, Fractional 냅색문제는 물건을 일부분만 쪼개서 담을 수 있는 문제입니다.

이 알고리즘은 동적 계획법을 사용하여 구현할 수 있으며, 시간 복잡도는 O(NW)입니다.여기서 N은 물건의 개수이고, W는 가방의 최대 부피입니다.

이 알고리즘은 대표적으로 백준 온라인 저지의 “짐 싸기 문제(Knapsack)”와 같은 다양한 문제에서 적용됩니다.

1. 가방문제 (냅색 알고리즘)

최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.

이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야 할까요? 각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.

▣ 입력설명

첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다. 두 번째 줄부터 각 보석의 무게와 가치가 주어진다. 가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

▣ 출력설명

첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.

▣ 입력예제 1

4 11
5 12
3 8
6 14
4 8

▣ 출력예제 1

28

---

설명

1. 다이나믹 테이블 dy를 가방에 담을 수 있는 무게의 한계값을 길이의 리스트로 만들고 모두 0으로 초기화
2. dy[j]는 j무게만큼 담을 수 있을때 총 가치를 저장해둔다.
3. 5kg일때 5kg하나를 넣은 가치랑 3kg, 2kg 보석 나눠서 내는 가치를 가 이득인지 업데이트하면서 11까지 가면 된다.

🚀 나의 풀이 ⭕

import sys 
sys.stdin = open('input.txt', 'r')
if __name__=="__main__":
    n,m=map(int, input().split()) # 보석 종류 개수, 무게의 한계값
    dy=[0]*(m+1)
    for _ in range(n):
      w,v = map(int, input().split()) # 보석 무게, 보석 가치 
      for j in range(w,m+1):          # j는 가방 무게 
        dy[j] = max(dy[j],dy[j-w]+v)  # w는 보석 무게, v는 보석 가치 
        # print(dy)
    print(dy[m])  # 정답 

2. 동전교환 (냅색 알고리즘)

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명

첫 번째 줄에는 동전의 종류개수 $N(1<=N<=12)$이 주어진다. 두 번째 줄에는 N개의 동전의 종 류가 주어지고, 그 다음줄에 거슬러 줄 금액 $M(1<=M<=500)$이 주어진다. 각 동전의 종류는 100원을 넘지 않는다.

▣ 출력설명

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

▣ 입력예제 1

3
1 2 5
15

▣ 출력예제 1

3

---

설명

1. 거슬러줄 금액 M 길이만큼의 dy 리스트에 1000으로 초기화해서 만들기
2. 동전 종류별로 for문 반복
3. 해당 동전값부터 거슬러줄 금액 M까지 반복하며 동전개수 dy에 넣기
4. 지금 넣어져 있는거랑 업데이트할거랑 비교하면서 업데이트

🚀 나의 풀이 ⭕

import sys 
sys.stdin = open('input.txt', 'r')
if __name__=="__main__":
    n=int(input())                            # 동전 종류의 개수  
    coins = list(map(int, input().split()))   
    m=int(input())
    dy=[1000]*(m+1)
    dy[0]=0
    for i in range(len(coins)):
      # print("coin: ",coins[i])
      for j in range(coins[i],m+1):           # 1~15, 2~15, 5~15
        dy[j]=min(dy[j],dy[j-coins[i]]+1)
        # print(dy)
    print(dy[m])

3. 최대점수 구하기 (냅색 알고리즘)

이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 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

---

설명

1. 한 유형당 하나만 풀 수 있다. 동전문제처럼 무한히 넣을 수 없다.
2. 제한시간 M 길이만큼의 dy 리스트를 만들고 뒤에서부터 진행하며
3. 점수와 시간 입력값을 받으면서 채워넣자

🚀 나의 풀이 ⭕

import sys 
sys.stdin = open('input.txt', 'r')
if __name__=="__main__":
    n,m=map(int, input().split())
    dy=[0]*(m+1)
    for i in range(n):
      score, time = map(int, input().split())
      for j in range(m,time-1,-1):
        dy[j]=max(dy[j],dy[j-time]+score)
        # print(dy)
    print(dy[m])

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기