[Java / 알고리즘] 탐욕 알고리즘(그리드 알고리즘)

### 1. 탐욕 알고리즘 이란?
- Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움
- 최적의 해에 가까운 값을 구하기 위해 사용됨
- 여러 경우 중 하나를 결정해야할 때마다, **매순간 최적이라고 생각되는 경우를 선택**하는 방식으로 진행해서, 최종적인 값을 구하는 방식

 

1. 탐욕 알고리즘(Greedy Algorithm)

• 각 단계에서 지금 당장 가장 좋은 선택을 하는 알고리즘
• 이 선택은 그 순간에 대해 최적일지라도, 이후의 선택에 대해서는 고려하지 않는다
• 여러 가능성 중 하나를 선택할 때 마다 현재의 선택이 문제의 최적 해에 얼마나 가까워지는지를 고려하여 선택을 진행한다

 

 

2. 대표적인 문제

1) 거스름돈 문제

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int[] coins = {500, 100, 50, 10}; // 동전의 종류
        int money = 1260; // 거슬러 줄 금액

        Map<Integer, Integer> coinsCount = new HashMap<>();
        int count = 0; // 거스름돈 동전 개수 카운트

        // 큰 단위의 동전부터 차례대로 확인
        for (int coin : coins) {
            int num = money / coin;
            count += num; // 해당 동전으로 거슬러 줄 수 있는 개수를 더함
            money %= coin; // 남은 거스름돈 갱신
            coinsCount.put(coin, num);
        }

        System.out.println("거스름돈 동전 개수: " + count);
        for (Integer i : coinsCount.keySet()) {
            System.out.println("동전 개수 : " + i + "원 " + coinsCount.get(i) + "개");
        }
    }
}

 

[결과]

거스름돈 동전 개수: 6
동전 개수 : 50원 1개
동전 개수 : 500원 2개
동전 개수 : 100원 2개
동전 개수 : 10원 1개

 

 

2) 회의실 배정 문제

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class GreedyExample {
    static class Meeting {
        int start;
        int end;

        Meeting(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) {
        List<Meeting> meetings = new ArrayList<>();
        meetings.add(new Meeting(1, 3));
        meetings.add(new Meeting(2, 5));
        meetings.add(new Meeting(3, 7));
        meetings.add(new Meeting(1, 8));
        meetings.add(new Meeting(5, 9));
        meetings.add(new Meeting(8, 10));

        // 종료 시간을 기준으로 정렬
        Collections.sort(meetings, Comparator.comparingInt(m -> m.end));

        List<Meeting> selectedMeetings = new ArrayList<>();
        selectedMeetings.add(meetings.get(0)); // 종료 시간 기준 정렬중 가장 빠른것 저장됨

        int endTime = meetings.get(0).end;

        for (int i = 1; i < meetings.size(); i++) {
            if (meetings.get(i).start >= endTime) {
                selectedMeetings.add(meetings.get(i));
                endTime = meetings.get(i).end;
            }
        }

        System.out.println("선택된 회의:");
        for (Meeting meeting : selectedMeetings) {
            System.out.println("[" + meeting.start + ", " + meeting.end + "]");
        }
    }
}

 

[결과]

선택된 회의:
[1, 3]
[3, 7]
[8, 10]

 

 

 

3. 탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용
• 반드시 최적의 해를 구할 수 있는 것은 아니기 때문이다.
• 최적의 해에 가까운 값을 구하는 방법 중의 하나임

 

[예시]

 

• '시작' 노드에서 시작해서 가장 작은 값을 찾아 leaf node 까지 가는 경로를 찾을 시에
  • Grddey 알고리즘 적용시 시작 -> 7 -> 12 를 선택하게 되므로 7 + 12 = 19 가 됨
  • 하지만 실제 가장 작은 값을 시작 -> 10 -> 5 이며, 10 + 5 = 15 가 정답