해당 문제를 다 풀고 나서 알아보니 배낭(Knapsack) 문제라고 유명한 문제였다. 대표적인 DP(Dynamic Programming) 알고리즘 문제 라고한다. 진짜 맨땅에 헤딩하듯이 문제를 풀다 보니 시행착오가 많이 있었다. 또한 가볍게 시작한 알고리즘 문제 풀기가 개발 사고를 넓혀주고 실무에도 도움이 될 것 같다고 생각을 하게 된 계기가 되었다. 푸는 과정이 재밌어서 게임은 줄이고 심심할 때 놀이 삼아 계속해서 문제를 풀어봐야겠다.
아래에 문제를 보여주고, 해당 문제 해석, 동작은 하지만 시간초과로 실패한 로직, DP알고리즘을 고려하여 작성한 로직으로 설명하겠다.
백준 12865번 평범한 배낭 문제
이 문제는 아주 평범한 배낭에 관한 문제이다.
한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.
준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.
첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.
입력으로 주어지는 모든 수는 정수이다.
한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.
4 7
6 13
4 8
3 6
5 12
14
문제분석
문제가 되게 명확했다. 가방에 최대로 넣을 수 있는 무게가 정해져 있고 주어진 물건들의 무게와 가치를 고려해서 가방에 넣을 수 있는 최대 가치를 찾는 문제다.
알고리즘 분류를 나중에 보았는데 다이나믹 프로그래밍(DP)으로 접근해야 하는 문제였다.
전반적인 로직을 순서대로 풀면 아래와 같다.
1. 첫번째 줄에 물품의 수(N)와 최대 무게(K)를 입력 받는다.
2. N만큼 반복하며, 물건의 무게(W)와 가치(V)를 입력 받는다.
3. 입력 받은 물건들을 조합하여 최대 가치를 구한다.
무게별로 최대 가치를 저장하는 일차원 배열을 생성하고, 물건을 입력받을 때마다 기존에 저장되어 있는 최대 가치와 해당 물건이 들어갔을 때의 가치를 비교해서 더 큰 가치를 최대가치로 덮어쓰기 하는 방식으로 문제를 해결했다. 아래에 최대가치를 계산하는 식과 예시를 작성하였다.
저장하는 무게의 최대 가치 = 기존 저장된 최대 가치 vs (최대무게 - 넣으려는 물건의 무게)의 최대가치 + 넣으려는 물건의 가치
예시) 4개(N)의 물건을 받고 최대무게 7kg(K)라고 했을때 (w는 무게, v는 가치)
첫번째 6w-13v의 물건을 넣을 경우 (연보라색)
그림과 같이 7kg, 6kg일 때 13의 가치가 저장되고, 5kg 경우 6kg보다 적기 때문에 더 이상 가치를 계산하고 넣지 않는다.
두 번째 4w-8v의 물건을 넣을 경우 (녹색)
7kg, 6kg 제한일 경우 6kg 물건 또는 4kg 물건 둘 중 하나만 넣을 수 있으므로 넣었을 때 더 가치가 높은 [13]이 남게 된다.
세 번째 3w-6v의 물건을 넣을 경우 (붉은색)[중요!!]
7kg 제한일 때 기존 최대 가치[13]와 (7-3)kg의 가치[8] + 3kg물건의 가치[6] = [14]를 비교하여 [14]로 덮어쓰기 하게 된다.
6kg 제한일 때 기존 최대 가치[13]와 (6-3)kg의 가치[6] + 3kg물건의 가치[6] = [12]를 비교하여 덮어쓰지 않고 넘어간다.
5kg~3kg까지는 위 과정과 동일하다.
마지막 5w-12v의 물건을 넣을 경우 (회색)
7kg 제한일 때기존 최대 가치[14]와 (7-5)kg의 가치[0] + 5kg물건의 가치[12] = [12]를 비교하여 덮어쓰지 않고 넘어간다.
6kg 제한일 때 기존 최대 가치[13]와 (6-5)kg의 가치[0] + 5kg물건의 가치[12] = [12]를 비교하여 덮어쓰지 않고 넘어간다.
5kg 제한일 때 기존 최대 가치[8]와 (5-5)kg의 가치[0] + 5kg물건의 가치[12] = [12]를 비교하여 [12]로 덮어쓰기 하게 된다.
위 과정이 마무리되면 7kg 가방의 최대 가치는 14가 나오게 된다. 응용하여 6kg 가방의 경우 같은 물건인 경우 13이 최대 가치가 된다.
문제 풀이 - 재귀함수 사용 (시간초과)
해당 풀이는 예제를 돌렸을 때 정상 동작은 하지만 시간초과로 인해 통과하지 못 한 문제 풀이다.
문제에 통과한 답을 보고 싶다면 "동적 프로그래밍(DP) 방식으로 접근"을 참고하길 바란다.
처음에는 단순히 생각했고, 물건의 개수에 따라 유동적으로 가방에 물건을 넣는 행위를 반복하면 되지 않을까?라는 생각에 재귀함수를 이용하여 코드를 작성해 보았다.상세한 설명과 코드를 보고 싶다면 아래 "더 보기"를 눌러서 확인하길 바란다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
// BufferedReader를 사용해 입력을 효율적으로 받기 위한 설정
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer str = null;
// 첫 줄에서 물품의 개수와 최대 무게를 입력받음
str = new StringTokenizer(br.readLine());
int quantity = Integer.parseInt(str.nextToken()); // 물품의 개수 n
int maxWeight = Integer.parseInt(str.nextToken()); // 최대 무게 k
// 입력받은 물품의 정보를 저장할 Item 배열 초기화
Item[] items = new Item[quantity];
int weight = 0;
int value = 0;
// 각 물품의 무게와 가치를 입력받아 items 배열에 저장
for (int i = 0; i < quantity; i++) {
str = new StringTokenizer(br.readLine());
weight = Integer.parseInt(str.nextToken());
value = Integer.parseInt(str.nextToken());
items[i] = new Item(weight, value);
}
// 결과 값을 저장할 Set 초기화 (중복 제거를 위해 Set 사용)
Set<Integer> resultHashSet = new HashSet<>();
// 모든 조합을 찾아서 최대 이익을 구함
findMaxValue(items, maxWeight, 0, new ArrayList<>(), resultHashSet);
// Set에서 가장 큰 값을 출력 (최대 이익)
System.out.println(Collections.max(resultHashSet));
}
/**
* 주어진 아이템 목록에서 가능한 모든 조합을 찾아서
* 최대 무게 이하의 경우 해당 조합의 가치를 Set에 추가하는 함수
*
* @param items 아이템 배열
* @param maxWeight 최대 허용 무게
* @param startIndex 현재 조합의 시작 인덱스
* @param currentCombination 현재 조합된 아이템 리스트
* @param resultHashSet 가능한 조합의 가치들을 저장할 Set
*/
private static void findMaxValue(Item[] items, int maxWeight, int startIndex,
List<Item> currentCombination,
Set<Integer> resultHashSet) {
int weightSum = 0;
int valueSum = 0;
// 현재 조합된 아이템들의 무게와 가치를 계산
for (Item item : currentCombination) {
weightSum += item.weight;
valueSum += item.value;
}
// 현재 조합의 무게가 최대 무게 이하라면 그 가치를 Set에 추가
if (weightSum <= maxWeight) {
resultHashSet.add(valueSum);
}
// 현재 인덱스부터 아이템 배열의 끝까지 모든 조합을 시도
for (int i = startIndex; i < items.length; i++) {
// 아이템을 현재 조합에 추가
currentCombination.add(items[i]);
// 재귀 호출을 통해 다음 아이템을 조합에 추가
findMaxValue(items, maxWeight, i + 1, currentCombination, resultHashSet);
// 현재 조합에서 마지막 아이템을 제거하여 다음 조합을 시도
currentCombination.remove(currentCombination.size() - 1);
}
}
}
// 아이템 클래스: 무게와 가치를 가지고 있는 객체를 정의
class Item {
int weight; // 아이템의 무게
int value; // 아이템의 가치
// 생성자를 통해 아이템의 무게와 가치를 설정
Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
해당 코드의 핵심은 재귀 함수를 사용하여 가방에 들어갈 수 있는 모든 조합을 구하고, 해당 조합의 가치를 "중복"을 허용하지 않는 Set에 담은 뒤 Collection.max()를 이용하여, 최대 가치를 구하는 거였다. 제공된 예시 값을 넣고 돌려보니 잘 작동하였다. 바로 제출을 하였으나, 결과는 "시간초과"였다.
재귀 함수를 사용해서 모든 조합을 구하는 것은 문제의 의도와는 다르게 브루트포스 알고리즘으로 풀었다고 할 수 있다. 최적화된 방법 없이 가능한 모든 경우를 다 시도하는 말 그대로 무식한 방식이었다. 하지만 수확이 없는 건 아니었다. 위 과정을 통해 해당 코드를 참고하고, 다듬어서 보다 효율적이고, 최적화된 로직을 작성할 수 있었다.
문제 풀이 - 동적 프로그래밍(DP) 방식으로 접근
위 방식은 가방에 들어갈 수 있는 최대 무게를 초과해도 재귀함수가 돌면서 모든 조합을 구하는 것이기에 더 효율적인 로직을 구성할 수 없을까 고민했다. 고민 결과 무게별 최대가치를 저장하는 배열을 만들고 (최대무게 - 넣으려는 물건의 무게)의 최대 가치 + 넣으려는 물건의 가치를 반복문을 통해 입력받을 때마다 비교해서 각 무게에 대한 최대 가치를 저장하도록 로직을 작성하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 12865번 - 평범한 배낭 (DP알고리즘)
public class Main {
public static void main(String[] args) throws IOException {
// 입력을 효율적으로 처리하기 위해 BufferedReader를 사용하여 입력을 받음
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 첫 번째 줄에서 물품의 개수와 최대 무게를 입력받음
StringTokenizer str = new StringTokenizer(br.readLine());
int quantity = Integer.parseInt(str.nextToken()); // 물품의 개수 N
int maxWeight = Integer.parseInt(str.nextToken()); // 최대 무게 K
// 최대 무게에 따라 각 무게에서 얻을 수 있는 최대 가치를 저장하기 위한 배열 초기화
int[] back = new int[maxWeight + 1]; // 무게가 0부터 maxWeight까지의 배열을 생성
// 물품의 개수만큼 반복하여 각 물품의 무게와 가치를 입력받고 처리
for (int i = 0; i < quantity; i++) {
str = new StringTokenizer(br.readLine());
int weight = Integer.parseInt(str.nextToken()); // 현재 물품의 무게 W
int value = Integer.parseInt(str.nextToken()); // 현재 물품의 가치 V
// DP 알고리즘 적용
// maxWeight부터 현재 물품의 무게까지 순회하면서 최대 가치를 업데이트
for (int j = maxWeight; j >= weight; j--) {
// 현재 무게 j에서 물품을 포함하는 경우와 포함하지 않는 경우 중 최대 가치를 선택하여 저장
// back[j]는 현재까지 고려한 물품들로 얻을 수 있는 무게 j에서의 최대 가치
// back[j - weight] + value는 현재 물품을 포함했을 때의 새로운 가치
back[j] = Math.max(back[j], back[j - weight] + value);
}
}
// 최대 무게에서 얻을 수 있는 최대 가치를 출력
System.out.println(back[maxWeight]);
}
}
재귀함수를 사용했을 때와 비교했을 때 코드의 가독성과 효율이 확실히 높아졌다. 문제를 풀고 나서 검색해 보니 다들 비슷하게 푼 것 같았다. (재귀함수..후...)
마무리
최근에 기존에 개발한 저장 로직이 100만 건을 저장하는 데 20분이 소요되어, 로직 개선이 필요했었는데, 비효율적인 로직을 더 효율적으로 개선하기 위해 고민하고, 여러 시행착오를 거쳐 결국 100만 건을 1분 36초 만에 저장되도록 개선했었다. 이번 문제를 풀면서 그때가 떠올랐었다.
문제를 해결하면서 이런저런 고민하는 게 생각보다 재미있어서 앞으로도 알고리즘 문제를 꾸준히 놀이 삼아 풀어야겠다는 생각이 든다.
'코딩테스트 > Java' 카테고리의 다른 글
| [백준 Beakjoon 1157번] 단어 공부 - 문제 해석 및 Java풀이 (0) | 2024.09.05 |
|---|---|
| [백준 Beakjoon 23971번] ZOAC 4 - 문제 해석 및 Java풀이 (2) | 2024.09.03 |
| [백준 Beakjoon 3190번] 뱀 - 문제 해석 및 Java풀이 (1) | 2024.08.23 |
