[ 냅색 알고리즘 ] 설명, 유형 별 풀이방법

DP(다이나믹 프로그래밍) 에서 냅색 알고리즘 이라는 것이 있다.
냅색 알고리즘이라고 이름이 붙은 이유는 이 알고리즘을 만든 사람의 이름을 딴 것이 아닌
단순하게 이 알고리즘의 가장 대표적인 문제가 배낭 문제여서 이름이 그렇게 붙여졌다고 한다

냅색 알고리즘은 조합 최적화(Combination Optimization) 문제에 사용하면 된다.

아래에 2가지 예시를 통해 자세히 알아보자.

 

* 예시 1 )

동전 1원, 2원, 5원이 주어진다. 15원을 상대방에게 거슬러 주려면 최소 몇개의 동전이 필요한가??

주어진 동전은 무한정 쓸 수 있다.

 

자. 이런식으로 가진 동전에서 조합으로 최소로 거슬러 줄 동전을 구하면 된다.
우선 정답은 3이다. 15원을 최소로 거슬러주려면 3(5원,5원,5원 으로 거슬러주면 됨) 그런데 어떠한
계산으로 이 정답이 나왔는지 알아보자. 다이나믹 프로그래밍 문제이기 때문에 문제를 작게 생각할 필요가 있다.
15원의 동전을 거슬러 줘야하면 0~15원일때 각각 거슬러줘야 할 동전을 구하면된다.
때문에 아래와 같은 배열이 필요함.  아래 코드와 주석을 확인해보자.

int [] dy = new int[16] // dy는 거슬러 줄 돈 0~15일때의 최소 동전개수를 저장하는 배열
Arrays.fill(dy,Integer.MAX_VALUE); // 최소 동전을 구해야하므로 가장 높은 정수로 초기화
dy[0]=0; // 0원을 거슬러 줄 수 없기에 0으로 초기화

 

 

냅색 알고리즘을 돌리기 전에 초기화는 이런식으로 한다. M은 MAX_VALUE,  arr={1,2,5}

for(int i=0;i<n;i++){
    for(int j=arr[i]; j<=target;j++){
        dy[j]= Math.min(dy[j],dy[j-arr[i]]+1); // 핵심코드
    }
}
return dy[target];

이렇게 입력에 따른 출력을 보면 가장 아래 3이 정답이고 위에 3개의 dy 배열이 보이는데

각 줄당

1원으로 15원을 거슬러 주려고 했을때,

3원으로 15원을 거슬러 주려고 했을때,

5원으로 15원을 거슬러 주려고 했을때

의 결과이다.! 여기서 우리가 기억해야 할 것은 이 문제는 무한정 쓸 수 있다.

무한정 쓸 수 있을때는 dy배열을 왼쪽부터 채운다.

왼쪽부터 채운다는 for(int j=arr[i]; j<=target;j++)으로 확인가능.

 

 

 

 

* 예시 2 )

당신에게 아래 5가지 문제와 20시간이 주어진다.  문제마다 풀었을때 얻는 점수와 소요되는 시간이 있다. 주어진 20시간에서 문제들을 풀었을때 얻을 수 있는가장 높은 점수를 구해라. 각 문제는 한번씩만 풀 수 있다.

 

문제1 : 점수 10 시간 5

문제2 : 점수 25 시간 12

문제3 : 점수 15 시간 8

문제4 : 점수 6 시간 3

문제5 : 점수 7 시간 4

 

자. 이번문제는 동전교환과 다르게 각 문제를 한번식만 풀 수 있다는 것이다.
문제 접근은 위 문제와 별 다를것 없다. 나에게 20시간이 주어져있다. 
그럼 내가 0~20시간 까지 시간당 가질 수 있는 점수를 구한다. 
이해가 어렵다면 종이에 그림을 그려보는 것을 추천한다.
그럼 int [] dy = new int[21]; 
핵심코드는 다음과 같다

//지금처럼 1문제만 풀 수 있다 (유한하다) j가 뒤에서 돌아야 함.
for(int i=0;i<n;i++){
    for(int j=limit; j>=time[i]; j--){
        dy[j]=Math.max(dy[j],dy[j-time[i]] + point[i]);
    }
}
return dy[limit];​

아래는 리턴한 값의 출력이다. 가장 하단에 정답, 20분동안 최대점수로 41점을 얻을 수 있다는 결과가 나온다.
정답 상단에 5줄로 배열이 출력되는데 이것은 j가 한번 돌때마다. 그러니까 더 쉽게 말하면
각 문제마다 풀 수 있는 가장 높은 점수이다.

예시1 문제에서 말한대로 무한하다 = dy배열 왼쪽부터 오른쪽으로 갱신한다. 그렇다면
이번 문제처럼 유한하다(1번만 풀 수 있다) = dy배열 오른쪽에서 왼쪽으로 갱신한다.
로 생각하면 문제풀이에 도움이 될 것 같다.

 

 

 

 

출처:자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 김태원