[멀티캠퍼스] 풀스택 개발자 아카데미 (15) - Algorithm(4)

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

이전 알고리즘에 대한 내용에서는, 가장 단순하게 모든 경우를 "탐색"하는 것과 가장 효율적인 접근법을 "정렬"을 통해 알아보았다.

문제를 해결하기 위한 전략은 이외에도 다양한데, 그중에서도 가장 직관적이며, 빠르고, 과감한 접근법인 탐욕 (Greedy) 알고리즘에 대해 알아보고자 한다.

Greedy Algorithm은 이름처럼 '탐욕스럽게' 매 순간 눈앞에 보이는 최선의 선택을 하는 전략이다. 향후, 미래를 생각하고 내다보며 계산하는 대신, "지금 당장 가장 좋아 보이는 것을 선택하면, 결국 전체적으로도 최적의 해를 얻을 수 있을 것이다" 라는 희망적인 가정에 기반한다.

이번 글에서는 이 단순한 전략이 어떻게 최적의 해를 찾아낼 수 있고, 그 성공을 보장하는 핵심 조건은 무엇인지 알아보고자 한다.

1. Greedy Algorithm의 핵심 철학

탐욕 알고리즘은 최종 목표를 달성하기 위해 여러 단계를 거쳐야 할 때, 각 단계마다 국지적(locally)으로 최적의 선택을 한다. 여기서 가장 중요한 특징은 절대 뒤를 돌아보지 않는다는 점이다.

한번 내린 선택은 번복하지 않고, 그 선택이 미래에 어떤 영향을 미칠지 고려조차 하지 않는다. 마치 욕심쟁이처럼, 그 한 순간에 내가 얻을 수 있는 가장 좋은 것을 고르는 것이다.

예를 들어 서울에서 부산까지 가는 경로를 찾는다고 가정하면, 탐욕적인 운전자는 각 갈림길에서 '부산과 가장 가까워 보이는 길'을 선택할 것이다. 이 선택이 고속도로가 아니라 국도로 이어져 결과적으로 더 오래 걸릴지라도, 뒤돌아가지 않고 일단은 눈앞의 이정표만 보고 달리는 셈이다.

그렇다면 이러한 단순한 선택들이 어떻게 전체적으로도 최적인 해답을 보장할 수 있을까?

당연하게도, 모든 문제에 탐욕 알고리즘을 적용할 수는 없다. 탐욕법이 성공하기 위해서는 해결해야 할 문제가 다음 두 가지 핵심 속성을 만족해야 한다.

1. 탐욕적 선택 속성(Greedy Choice Property)

   • 현재 내린 국지적 최적 선택이, 반드시 전역적 최적 해의 일부가 되어야 한다.
   • 즉, 지금의 선택이 나중에 발목을 잡아 최적해를 놓치게 만드는 일이 없어야 한다. 이 속성이 탐욕 알고리즘을 적용할 수 있는 가장 중요한 전제 조건이다.

2. 최적 부분 구조 (Optimal Substructure)

   • 문제의 전역적 최적 해는, 그 문제의 부분문제(subproblem)에 대한 최적 해를포함하고 있어야 한다.
   • 예를 들어, A에서 D까지 가는 최적 경로가 A-B-C-D라면, A에서 C까지의 최적 경로는 반드시 A-B-C 여야 한다.
   • 이 속성은 분할 정복이나 동적 프로그래민(DP)에서도 나타나지만, 탐욕 알고리즘은 부분 문제의 해를 구하기 전에먼저 선택을 한다는 점에서 차이가 있다.

이 두 가지 속성이 성립할 때, 우리의 '탐욕스러운' 선택은 비로소 정당성을 얻고, 최적의 해를 얻을 수 있다.

2. Greedy - 거스름돈 문제

가장 고전적인 탑욕 알고리즘 예제는 거스름돈 문제이다.

• 탐욕적 선택: "현재 남은 금액을 초과하지 않는 가장 큰 단위의 동전으로 거슬러 준다."

• 논리적 과정:

  1. 남은 돈 3,465원. 500원 이하가 될 때까지 가장 큰 동전 500원으로 거슬러 준다. (500원 x 6) -> 남은 돈 465원
  2. 남은 돈 465원. 마찬가지로 현재 선택 가능한 가장 큰 동전 100원으로 최대한 거슬러 준다. (100원 x 4) -> 남은 돈 65원
  3. 남은 돈 65원. 가장 큰 동전 50원으로 최대한 거슬러 준다. (50원 x 1) -> 남은 돈 15원
  4. 남은 돈 15원. 가장 큰 동전 10원으로 최대한 거슬러 준다. (10원 x 1) -> 남은 돈 5원
  5. 남은 돈 5원, 가장 큰 동전 1원으로 최대한 거슬러 준다. (1원 x 5) -> 남은 돈 0원
• 결과: , 총 17개의 동전.

• Java 구현

import java.util.Map;
import java.util.LinkedHashMap;

public class ChangeCalculator {
  public Map<Integer, Integer> getMinimumCoins(int amount) {
    int[] coins = {500, 100, 50, 10, 1};
    Map<Integer, Integer> result = new LinkedHashMap<>(); // 순서 보장

    // 500원 ~ 1원 순회하면서 반복
    for(int coin: coins) {
      // 남은 돈이 0이면 종료
      if (amount == 0) break;

      // 사용할 동전 갯수
      int count = amount / coin;
      if (count > 0) {
        result.put(coin, count);
        // 남은 돈 계산
        amount %= coin;
      }
    }
    return result;
  }
}

3. 회의실 배정 문제

탐욕 알고리즘의 진가는 왜 이 탐욕적 선택이 최적인가를 증명하는 과정에서 드러난다.

• 탐욕적 선택: "가장 먼저 끝나는 회의를 선택한다." (가장 먼저 시작하거나, 가장 짧은 회의를 선택하는 것은 최적 해를 보장할 수 없음)

• 논리적 과정:

  1. 모든 회의를 종료시간 기준으로 오름차순(먼저 끝나는 것 부터) 정렬한다.
  2. 정렬된 목록의 첫 번째 회의를 선택한다.
  3. 목록을 순회하며, 바로 이전에 선택한 회의의 종료 시간 이후 시작하는 회의 중 가장 먼저 나오는 것을 선택
  4. 모든 회의를 확인할 때까지 순회

• 최적 해 증명: "가장 먼저 끝나는 회의를 선택"하는 것은 회의실을 가장 빨리 비워주기 때문 이다. 회의실을 빨리 비워야 그 이후에 남은 시간 동안 더 많은 회의를 배정할 수 있는 '기회'가 많아 지기 때문이다. 다른 어떤 회의를 선택하더라도, 이 회의보다 늦게 끝나므로, 남은 시간에 대한 기회는 줄어들거나 같을 뿐, 더 많아지지 않는다. 따라서, 이 국지적 최적 선택은 전역적 최적 해를 방해하지 않는다.

  • 예를 들어, 다음 사진에서와 같이 회의가 있을 때, 회의A와 회의C 대신 짧은 회의C를 선택해 버린다면, 2개의 회의를 진행할 시간에 1개 밖에 진행할 수 없게 된다.

• Java 구현

import java.util.*;

// 회의를 정의하는 클래스
class Meeting {
    int idx;
    int start;
    int end;

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

    @Override
    public String toString() {...}
}

class MeetingScheduler {
    // 회의를 스케줄링하여 배열로 반환
    public static Meeting[] getMaxMeetings(Meeting[] meetings) {
        // 사용하기 쉽도록 List<> 객체로 변환
        List<Meeting> meetingList = Arrays.asList(meetings);
        // 종료 시각 순으로 정렬
        meetingList.sort(Comparator.comparing(m -> m.end));

        // 결과를 담을 리스트
        List<Meeting> result = new ArrayList<>();

        // 정렬된 리스트를 순회하며 최적회 계산
        for (Meeting meeting : meetingList) {
            if (result.isEmpty()) {
                // 첫번째 회의
                result.add(meeting);
            } else {
                // 마지막으로 끝난 회의와 겹지지 않고, 빨리끝나는 회의찾기
                Meeting last = result.getLast();
                if (last.end <= meeting.start) {
                    result.add(meeting);
                }
            }
        }

        // 배열로 변환하여 반환
        return result.toArray(new Meeting[0]);
    }

    public static void main(String[] args) {
        Meeting[] meetings = {
                new Meeting(1, 1, 10),
                new Meeting(2, 5, 6),
                new Meeting(3, 13, 15),
                new Meeting(4, 14, 17),
                new Meeting(5, 8, 14),
                new Meeting(6, 3, 12)
        };

        Meeting[] result = getMaxMeetings(meetings);
        System.out.println(Arrays.toString(result));
    }
}

4. 최소 신장 트리 (Kruskal Algorithm)

탐욕 알고리즘은 그래프 문제에서도 강력한 힘을 발휘한다.

**최소 신장 트리(Minimum Spanning Tree, MST)**는 '그래프의 모든 정점을 연결하되, 간선(edge) 가중치의 합이 최소가 되는 트리'를 찾는 문제다. 통신망을 최소 비용으로 구축하거나, 도시들을 최소 길이의 도로로 연결하는 문제와 같다.

크루스칼(Kruskal) 알고리즘은 MST를 찾는 대표적인 탐욕 알고리즘입니다.

• 탐욕적 선택: "현재 그래프에서 사이클(cycle)을 형성하지 않는 가장 가중치가 작은 간선을 선택한다."

• 논리적 과정:

  1. 모든 간선을 가중치 기준으로 오름차순 정렬한다.
  2. 정렬된 간선 목록을 순서대로 확인하며, 현재 간선을 추가했을 때 사이클이 생기지 않으면 트리에 포함시킨다.
  3. 사이클 발생 여부는 Union-Find 자료구조를 통해 효율적으로 확인할 수 있다.
  4. (정점 개수 - 1)개의 간선이 선택될 때까지 2번 과정을 반복

이 전략이 최적인 이유는, 각 단계에서 가장 비용이 적은 간선을 선택하는 것이 MST의 정의(총비용 최소화)에 가장 부합하기 때문이다. 지금 당장 가장 저렴한 간선을 포기하고 더 비싼 간선을 선택해야만 나중에 더 큰 이득을 보는 경우는 발생하지 않는다는 것이 증명되어 있다.

5. 탐욕의 함정 - 언제 실패하는가?

그렇다면, 거스름돈 문제는 항상 탐욕법으로 해결할 수 있는지 의문을 가져볼 수 있다. 만약 동전 단위가 다르다면 어떻게 되는가?

• 탐욕적 접근: 10원짜리 1개 (남은 돈 4원) -> 1원짜리 4개. 총 5개의 동전.
• 최적의 해: 7원짜리 2개. 총 2개의 동전.

여기서 우리는 탐욕 알고리즘의 치명적인 약점을 발견할 수 있다.

탐욕적 선택 속성이 깨진 것이다. 첫 단계에서 "가장 큰 동전(10원)을 선택"하는 국지적 최적 선택이, 전역적 최적 해(7원짜리 2개)의 일부가 아니었다. 이처럼 대부분의 화폐 단위는 큰 단위가 작은 단위의 배수 관계를 만족하여 탐욕법이 통하지만, 그렇지 않은 경우에는 최적 해를 보장할 수 없다.

6. 탐욕 알고리즘 vs 동적 프로그래밍

탐욕 알고리즘이 통하지 않는 문제들은 어떻게 해결해야 할까. 여기서 **동적 프로그래밍(Dynamic Programming, DP)**이 등장한다.

• 탐욕 알고리즘: 각 단계에서 단 하나의 최적의 길만 보고 직진한다. 되돌아오지 않는다.
• 동적 프로그래밍: 각 단계에서 가능한 모든 선택지를 고려하고, 그 결과를 기록(메모이제이션)해 둔다. 이를 통해 모든 부분 문제의 최적 해를 구하고, 최종적으로 전체 문제의 최적 해를 도출한다.

위의 '14원 거스름돈 문제'를 DP로 푼다면, 14원을 만드는 모든 경우의 수(10원+1x4, 7원+7원, 7원+1x7, 1x14...)를 고려하여 그중 가장 동전 개수가 적은 해답을 찾아낼 것이다. DP는 탐욕법보다 더 복잡하고 많은 계산을 요구하지만, 탐욕법이 놓칠 수 있는 최적의 해를 확실하게 찾아낼 수 있다.

7. 결론

탐욕 알고리즘은 현명한 낙관주의자와 같은 철학을 가진 문제 해결법이다.

그 결과로 얻어지는 단순함과 속도는 매우 매력적이지만, 그 낙관이 통하지 않는 문제에서는 치명적인 오류를 낳는 양날의 검과 같다.

따라서 개발자에게 탐욕 알고리즘이란, 단순히 코드를 구현하는 능력이 아니다.

라는 의문에 대해 증명하고 판단하는 통찰력을 요구하는 문제이자, 그 증명 과정이야말로 탐욕 알고리즘이라고 볼 수 있다.