백준 5350 java : DP, 배낭문제

magicdrill·2024년 12월 6일

목록 보기

502/655

백준 5350 java : DP, 배낭문제

DP를 1차원 배열 또는 2차원 배열로 만드는 경우의 차이와 구분 방법?
DP를 역순으로 하는 경우와 이유?

import java.util.Arrays;
import java.util.Scanner;

public class bj5350 {
    static Scanner scanner = new Scanner(System.in);
    static int W;
    static int [] w;
    static int [] v;


    public static void main(String[] args){
        int T, i;

        T = scanner.nextInt();
        for(i = 0; i < T; i++){
            inputData();
            System.out.println(findAnswer());
        }

        scanner.close();
    }

    public static void inputData(){
        System.out.println("inputData()");
        int n, i;

        n = scanner.nextInt();
        W = scanner.nextInt();
        w = new int[n];
        v = new int[n];

        for(i = 0; i < n; i++){
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }
    }

    public static int findAnswer(){
        System.out.println("findAnswer()");
        int i, j;
        int n = w.length;
        int [] DP = new int[W + 1];

        for(i = 0; i < n; i++){
            for(j = W; j >= w[i]; j--){
                if(j - w[i] >= 0){
                    DP[j] = Math.max(DP[j], DP[j - w[i]] + v[i]);
                }
            }

            for(j = 1; j <= W; j++){
                System.out.print(DP[j] + " ");
            }
            System.out.println();
        }

        return DP[W];
    }
}

chatgpt

배낭문제(0/1 Knapsack)에서 동적 계획법(DP) 구현 시 1차원 배열과 2차원 배열을 선택하는 것은 주로 공간 효율성과 코드의 가독성에 따라 결정됩니다. 두 방식의 차이와 구분 방법을 살펴보겠습니다.

1. 2차원 배열 사용

2차원 배열을 사용하면, dp[i][w]로 i번째 물건까지 고려했을 때, 배낭의 용량이 w인 경우 최대 가치를 명확히 나타낼 수 있습니다.

특징

구현 방식: 각 물건(i)에 대해 모든 배낭 용량(w)에 대해 점화식을 계산.
공간 복잡도: ( O(n \times W) ), ( n )은 물건 개수, ( W )는 배낭 용량.
장점:
- DP 테이블의 각 상태를 직관적으로 이해 가능.
- 물건 하나를 추가하거나 상태를 추적하는 디버깅이 용이.
단점:
- 불필요하게 메모리를 많이 사용. 사실 한 번에 한 행만 필요하므로 메모리 낭비가 생김.

2. 1차원 배열 사용

1차원 배열을 사용하면, 이전 단계의 값을 재활용하여 메모리 사용량을 줄일 수 있습니다.

특징

구현 방식: dp[w]는 현재 배낭 용량 ( w )에서 최대 가치를 나타냄.
공간 복잡도: ( O(W) )로, 물건 개수와 관계없이 배낭 용량 크기만큼의 메모리 사용.
장점:
- 메모리 효율이 뛰어남.
- 큰 용량의 배낭 문제에서도 적은 메모리로 해결 가능.
단점:
- 점화식 적용 시 이전 상태를 덮어쓰는 문제를 해결해야 하므로, 계산 순서를 조심해야 함.
  - 배낭 용량을 역순으로 순회해야 이전 값에 영향을 주지 않음.
- 디버깅 및 상태 추적이 상대적으로 어렵다.

3. 1차원 vs 2차원 배열의 차이

구분	2차원 배열	1차원 배열
공간 복잡도	( O(n \times W) )	( O(W) )
메모리 효율성	낮음	높음
구현 난이도	쉬움	어려움(역순 순회 필요)
상태 추적	명확 (이전 단계 접근 용이)	어렵다
사용 상황	- 이해와 디버깅이 중요한 경우 - ( W )가 작거나 메모리가 충분한 경우	- 메모리가 제한적이거나 공간 최적화가 중요한 경우

4. 구분 방법 및 선택 기준

문제의 크기
- ( n )과 ( W )가 작다면 2차원 배열로 작성해도 충분히 처리 가능.
- ( n ) 또는 ( W )가 매우 크다면 1차원 배열로 공간 효율성을 고려해야 함.
추적이 필요한 경우
- 2차원 배열은 특정 상태에서 이전 상태를 쉽게 확인 가능.
- 1차원 배열은 추적을 따로 구현해야 하므로 복잡해질 수 있음.
알고리즘 최적화 목표
- 단순히 최댓값만 구하고 싶다면 1차원 배열로 구현.
- 선택한 물건의 리스트를 구하는 등 추가 정보가 필요하면 2차원 배열로 구현.