문제
- 백준 12865
1-1. 약간 효율적으로 배낭 무게를 채우는 방식인 거 같은데, 예전에 비슷한 문제를 풀었던 기억이 있는데... 정확히 기억이 안난다.
1-2. 원래는 하나씩 더하는 방식을 사용하려고 했다.
-> 예를 들면 int i = 1로 두어서 배열의 처음에 저장해두고
-> for문을 통해서 1부터 마지막 - 1까지 반복하게 한다.
-> for문 안에 for문을 2중으로 두어서 j를 i + 1부터 마지막까지 반복하게 하는데
-> 이 때, 현재 배열 i의 무게랑 더해지는 무게가 K보다 적으면 다른 배열에 j를 추가시키도록 해서 배열안에 있는 것들과 기존 최대값을 비교해보도록 하였다.
- Git을 사용 중에 fork하고 clone해서 사용중인데 팀장님이 추가하신 부분을 git fetch를 하니 프로젝트에서 파일들이 보이지 않는다.
시도
- 예시는 맞는데 계속 제출하면 틀렸습니다가 나옴
1-1. 뭐가 잘 못 되었나 생각해보니까
-> 만약 1번째랑 3번째가 들어가고 5번째랑 6번째의 무게가 같은 것과 같이 현재 값이 들어가고 되고 다음 값도 들어가도 되지만, 현재 값이 들어가면 다음 값의 value가 더 커도 들어가지 못한다.
-> 아마도 이런 문제라면 각각의 무게 별로 (1~K까지) 최대 value가 몇이 더해질 수 있는지 해놓는게 맞는 거 같다. 이거를 bottom-up 방식으로 풀면 될 듯
- Project structure이랑 setting에 가서 modules를 변경해주었는데도 보이지 않는다.
2-1. 혹시 자바를 다른 것으로 해야하나 해서 팀장님이 사용하신 correto-17로 다운 받아도 안됨
해결
- 결국 해결하지 못하고 구글링을 했다...
for (int i = 1; i <= test_case; i++)
for (int j = K; j - key[i] >= 0; j--) {
dp[j] = Math.max(dp[j], dp[j - key[i]] + value[i]);
}
- bottom-up 방식으로 아래에서부터 하나씩 해결하는 방식
- 안에 있는 for문을 보면 j = K로 설정하고 j - key[i] (=> 현재 무게에서 현재 들어온 무게 값을 빼도 되는가) 을 종료 조건으로
- dp라는 배열 (1부터 K까지의 무게들 중에서 각 무게별로 최대 가치들을 저장) 에 '현재 저장된 무게에 대한 가치 값'과 '현재 저장된 무게에 대한 가치 값 - 현재 들어온 무게 값 + 현재 들어온 무게의 가치 값'을 비교해서 더 큰 값을 다시 '현재 저장된 무게에 대한 가치 값'에 저장
- Project Structure로 감
2-1. Modules에서 아까처럼 아무것도 안보여도 +를 눌러줌
2-2. Project의 root 디렉토리로 지정
2-3. next 버튼을 누르면서 넘김
2-4. 다시 correto-17과 같은 module들을 지정
-> 해결
알게 된 점
- 알고리즘의 중요성에 대해서 다시금 깨닫게 되었다. 모르고 있으면 풀 수 없거나 푸는데 시간이 더 많이 걸리고 복잡해지네...
- Git을 사용하는데 있어서 fork랑 fetch를 조금 더 익숙하게 사용해야 팀플에 용이할 듯
- git remote add upstream git@github.com:youngmin13/MemoNote.git
-> fork한 git의 original repository를 설정
- git fetch upstream
-> 원본 repository 가져오기
- 배낭 채우기 문제 (Knapsack Problem)
- 어떤 배낭이 있고 그 배낭안에 넣을 수 있는 최대 무게가 K라고 할 때, 배낭에 넣을 수 있는 N개의 물건이 각각 다른 가치 V를 가지고 있고 각 물건마다 다른 무게 W를 가지고 있을 때, 배낭이 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제
- 종류 : Fractional Knapsack (쪼갤 수 있는 문제 -> 소수점 가능), 0-1 Knapsack (쪼갤 수 없음 -> 정수)
- 해결 방법
- Brute Force Approach : 경우의 수를 모두 시도하는 방법
- Dynamic Programming : 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용, 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 시간이 오래 걸리고 비효율적인 계산을 하게 됨.(bottom-up, top-down)
오늘 푼 문제
백준 12865 (평범한 배낭) - Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int test_case = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] key = new int[test_case + 1];
int[] value = new int[test_case + 1];
int[] dp = new int[K + 1];
for (int i = 1; i <= test_case; i++) {
st = new StringTokenizer(br.readLine(), " ");
key[i] = Integer.parseInt(st.nextToken());
value[i] = Integer.parseInt(st.nextToken());
}
for (int i = 1; i <= test_case; i++)
for (int j = K; j - key[i] >= 0; j--) {
dp[j] = Math.max(dp[j], dp[j - key[i]] + value[i]);
}
bw.write(String.valueOf(dp[K]));
bw.flush();
bw.close();
br.close();
}
}
