12865 평범한 배낭

드디어 블로그를 만들고 첫 글을 작성하네요.

 

23년에는 부지런하게 살겠다고 마음을 먹었지만, 23년 2월부터는 부지런히 살아야겠다로 다시 마음을 먹어야겠습니다.

 

화이팅..

 

백준 12865 - 평범한 배낭 

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

알고리즘 수업에서 다이나믹 프로그래밍 강의를 듣고 자신감 있게 도전한 문제였는데 시간초과에 늪에 빠져서 결국 검색의 힘을 빌려서 해결하게 되었습니다. (교수님 죄송해오)

 

-나의 풀이-

 

저는 정말 배운대로 했습니다.

 

다이나믹 프로그래밍은 점화식이다! 라고 교수님이 알려주셨기 때문에 문제를 읽고 나름의 점화식을 도출했습니다.

 

solution(Number , capacity) : 물건의 번호와 현재 가방의 용량을 입력하면 그 상황에서 가치를 계산해주는 함수

 

w[i] : 물건의 무게가 저장되어있는 배열 , p[i] : 물건의 가치가 저장되어 있는 배열

 

solution(number,capacity) = Math.max(solution(number+1), capacity - w[number] +p[number],

solution(number+1, capacity))

 

이런거 보면 Dp는 그냥 Bruthforce와 별 다른거 없어 보인다고 생각했습니다. 아 이 주제는 일단 문제 포스팅을 다하고 하는 것이 좋겠습니다. 

 

아무튼 위의 solution 메소드를 돌리면 최고의 가치를 구할 수 있었습니다.

import java.util.Scanner;

public class Main {
	static int[] p;
	static int[] w;
	public static int solution(int n, int i, int m) {
		if(m<0) {
			return -p[i-1];
		}
		if(i==n) {
			if(m>=w[i]) {
				return p[i];
			}
			return 0;
		}
		return Math.max(solution(n,i+1,m-w[i])+p[i],solution(n,i+1,m)) ;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		p = new int[n+1];
		w = new int[n+1];
		for(int i=1;i<=n;i++) {
			w[i] = sc.nextInt();
			p[i] = sc.nextInt();
		}
		sc.close();
		System.out.println(solution(n,1,m));
	}
}

그리고 당당하게 제출 후, 그대로 시간초과와 만나게 되었습니다.  그래도 당황하지 않았습니다. 저에게는 민경하 교수님이 주신 비장의 코드가 존재했기 때문입니다.

 

그것은 degeneratecase를 설정 해주는 것.

 

solution 메서드를 반복하다가 두 가지의 경우가 나오면 바로 return 해주는 2가지 경우를 만들었습니다.

 

1. 만일 남아있는 물건 중 가장 작은 무게보다 현재 남아있는 무게가 더 적다면, 멈춘다

2. 만일 남아있는 무게의 총량보다 현재 남아있는 무게가 더 크다면, 멈춘다

 

이 두가지의 경우를 확인하기위해서 추가적인 메서드와 물건의 정렬이 필요했습니다. (이때 멈추어야 했습니다.)

 

저는 굴하지 않고 1. 물건의 정보를 객체화하였고

                            2. 물건을 무게에 따라 정렬하였으며 

                            3. 현재 물건의 순서에 입력한다면, 현재 가장 작은 무게를 구하는 메서드와

                            4. 현재 남아있는 무게를 구해주는 메서드와

                            50. 현재 남아있는 가치의 합을 구해주는 메서드를 구현하였습니다. (체감상 50번이라서)

 

그리고는 결과로 다시 시간초과를 받았습니다. 그 후 노트북을 닫고..

 

- 2번째 도전 - 

 

왜 나는 Big-O 를 배우고 그것을 이용하지 않았을까. 민경하 교수님에 대한 신뢰로 위장한 나의 게으름이였다는 사실을 눈치 챘습니다.

 

문제에 시간제한은 2초이고, N(주어지는 물건의 수) 는 100입니다. 2와 100이라는 숫자는 마음의 안정을 주지만 꼼꼼하게 생각할 필요가 있습니다. 

 

N = 2일때, 1번 물건 2번 물건이 각각 포함 ,미포함을 체크해야하니 4번 체크가 필요합니다.

 

N = 3일때는 8번.. 결국 O(n) = 2^n 으로 최악의 시간복잡도가 나옵니다. 

 

2^100은 126,7650,6002,2822,9401,4967,0320,5376입니다. 비장의 코드 따위로 해결될 문제가 아니였습니다. 

 

짧은 코딩 공부 간, 시간을 줄이는 방법은 " 1. memoization , 2. 다시한다 " 가 전부였습니다. 

 

memoziation을 사용하고 싶었지만, 어떤식으로 사용해야하는지는 생각이 떠오르지 않았습니다. 그래서 다시해보다가 결국 구글링을 하게 되었습니다.

 

우선 제가 memoziation을 못한 이유는 아마 1차 배열에서만 해야한다는 아주 비겁한 생각 덕분이였습니다.(물론 1차배열로만을 이용하여 구현이 가능하기도 합니다)

 

-해설-

 Dp문제는 모든 케이스를 확인을 해야합니다. Greedy는 하나의 기준을 통한 정렬을 이용하여 해결이 가능하지만, Dp는 단순히 하나의 기준으로 문제를 해결하기에는 불가능한 경우가 존재합니다. 결국 모두 확인해야합니다.

 

그렇다면 어떤 방식으로 모든 케이스를 확인해야하는지가 문제의 핵심이라는 생각이 듭니다. 제가 공부한 방법은 앞서 말씀드린 memoziation을 이용합니다. 

 

memoziation을 고심하며 가장 어려웠던 것은 어떻게 저장해야 하는지에 대한 고민였습니다. 저장을 해야하는 요소는 당연히 "최대가치"인데, 어떤 경우의 최대가치를 저장해야하는지 몰랐습니다. 

 

여러 검색을 통해 해설을 보았지만, 쉽게 이해하기가 힘들어서 꽤 고민을 했습니다. 저는 보이지 않는 것은 잘 믿지 못해서 직접 해보아야 마음이 놓입니다. 머리가 나쁘면 몸이 고생하는 스타일이죠.

 

	무게 : 1	2	3	4	5	6	7
번호: 1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4

번호	1	2	3	4
무게	6	4	3	5
가치	13	8	6	12

우선 2차원 배열에 memoziation을 해줘야 합니다. 여기서 포인트는 어떤 기준으로 저장해줘야 하는지입니다. 

세로행인 번호 이하의 물건 번호를 사용하여 무게내 최대 가치를 저장해주는 방식입니다.

 

예로 번호 1을 채우면 1번 짐은 무게가 6이니 0 , 0 , 0 , 0 , 0 ,13 , 13 으로 채워집니다. (파랭이)

다음으로 2번째 줄을 채우면 0, 0, 0, 8, 8, 8 ,8 으로 채우는 것이 아니라 세로행 번호이하 즉 1번 물건도 사용이 가능하니 둘 중에 무엇이 더 가치가 있는지 비교해주어야 합니다. 그 결과 0, 0 ,0 , 8, 8, 13, 13 입니다 (빨갱이)

 

무엇이 더 가치있는지에대한 연산 과정을 보고 제가 처음 쓴 점화식이 기억나신다면, 부럽습니다. 저는 오래걸렸습니다ㅠ

solution(Number , capacity) : 물건의 번호와 현재 가방의 용량을 입력하면 그 상황에서 가치를 계산해주는 함수 W[i] : 물건의 무게가 저장되어있는 배열 , P[i] : 물건의 가치가 저장되어 있는 배열 solution(number,capacity) = Math.max(solution(number-1, capacity - w[number]) +p[number], solution(number-1, capacity))

즉 solution(n , c) = Math.max( solution(n-1,c) , solution(n-1,c -W(n) ) + P(n) ) 이라는 점화식이 도출됩니다. DP는 점화식이라는 교수님의 말이 사실입니다. 

 

점화식을 풀어서 해석하자면, 해당번호의 물건을 포함하지 않는 최고 가치와 해당물건을 포함한 최고 가치의 비교입니다. 이해가 될듯..말듯한 기분입니다. 

 

위와 같은 과정을 구현한 코드입니다. 

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st =new StringTokenizer(bf.readLine());
        int casenumber = Integer.parseInt(st.nextToken());
        int capacity = Integer.parseInt(st.nextToken());
        int[] value = new int[casenumber+1];
        int[] weight = new int[casenumber+1];
        int[][] memo = new int[casenumber+1][capacity+1];
        for(int i=1; i<=casenumber ; i++){
            st = new StringTokenizer(bf.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }
        for(int i=1 ; i<=casenumber ; i++){
            for(int j=1 ; j<=capacity; j++){
                memo[i][j] = memo[i-1][j];
                if(j>=weight[i]){
                    memo[i][j] = Math.max(memo[i][j],memo[i-1][j-weight[i]]+value[i]);
                }
            }
        }
        System.out.println(memo[casenumber][capacity]);       
    }    
}