Colin's Blog
[java] 스택을 이용한 탐욕 알고리즘 구현하기

탐욕 알고리즘은 현재 상황에서 가장 최선의 선택을 하는 알고리즘입니다. 이 알고리즘은 매 순간의 선택이 최종적인 최적해를 보장하지는 않지만, 일부 문제에서는 효과적인 해답을 제공합니다. 이번 글에서는 자바에서 스택을 이용하여 탐욕 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

문제 설명

주어진 N개의 아이템 중에서 무게와 가치가 주어진다고 가정해봅시다. 최대 무게 W까지만 아이템을 가져갈 수 있을 때, 최대의 가치를 가지는 아이템 조합을 찾는 문제입니다.

알고리즘 설계

  1. 주어진 아이템을 무게별로 정렬합니다.
  2. 빈 스택을 생성합니다.
  3. 정렬된 아이템을 순서대로 스택에 추가합니다.
  4. 스택의 요소를 하나씩 꺼내서 무게를 비교합니다.
  5. 만약 현재 요소의 무게가 최대 무게 W보다 작거나 같다면 해당 요소를 선택합니다.
  6. 선택한 요소의 가치를 결과값에 더하고 현재 무게를 갱신합니다.
  7. 만약 현재 무게가 최대 무게 W를 초과하면 선택한 요소를 제외합니다.
  8. 모든 아이템을 확인할 때까지 반복합니다.

자바 코드

import java.util.*;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        int[] weights = {1, 3, 2, 5, 4};
        int[] values = {10, 15, 30, 20, 25};
        int maxWeight = 7;

        int numItems = weights.length;

        // 아이템을 무게별로 정렬
        Item[] items = new Item[numItems];
        for (int i = 0; i < numItems; i++) {
            items[i] = new Item(weights[i], values[i]);
        }
        Arrays.sort(items);

        Stack<Item> stack = new Stack<>();
        int currentWeight = 0;
        int totalValue = 0;

        // 아이템 선택
        for (int i = 0; i < numItems; i++) {
            if (currentWeight + items[i].weight <= maxWeight) {
                stack.push(items[i]);
                currentWeight += items[i].weight;
                totalValue += items[i].value;
            }
        }

        // 결과 출력
        System.out.println("최대 가치: " + totalValue);
        System.out.println("선택된 아이템:");
        while (!stack.isEmpty()) {
            Item item = stack.pop();
            System.out.println("무게: " + item.weight + ", 가치: " + item.value);
        }
    }

    static class Item implements Comparable<Item> {
        int weight;
        int value;

        public Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }

        @Override
        public int compareTo(Item other) {
            return Double.compare((double) other.value / other.weight, (double) this.value / this.weight);
        }
    }
}

실행 결과

최대 가치: 65
선택된 아이템:
무게: 4, 가치: 25
무게: 3, 가치: 15
무게: 2, 가치: 30

참고 자료

위의 코드는 주어진 아이템의 무게와 가치를 스택을 이용하여 탐욕 알고리즘으로 해결하는 예제입니다. 참고 자료를 통해 더욱 자세한 내용을 확인할 수 있습니다.

© 2018 Colin. All rights reserved.