[자바 알고리즘] Greedy Algorithm (그리디 알고리즘)

📘 Greedy Algorithm (그리디 알고리즘)

📖 그리디 알고리즘이란?

미리 정한 기준에 따라서 매번 가장 좋아보이는 답을 선택하는 알고리즘을 말한다. 즉, 다시 말해 백트래킹을 하여 내가 선택한 결과에 대해서 검증하지 않고, 이미 어떤 선택을 했다면 다른 선택의 가능성을 전혀 고려하지 않는다.

그래서 그리디 알고리즘은 속도가 빠르다는 장점이 있지만, 다른 선택의 가능성을 고려하지 않기 때문에 생기는 문제점이 존재한다. 그 문제점은 바로 그리디 알고리즘을 통해 나오는 결과 값이 항상 최적의 값이 될 수 없다는 것이다.

 

📖 그리디 알고리즘의 문제점

예를 들어 노드 1번에서 노드 5번까지 가는 길이 아래 그림 처럼 존재한다고 가정하고, 우리는 가장 최적의 값(가까운 거리)을 선택하면서 직진해 나갈 것이다. 이때 실제 최적의 값과 그리디 알고리즘을 통해 얻은 결과 값이 같은지 한번 확인해보자.

그리디 알고리즘을 사용하면 1번 노드에서 다음 노드로 이동할 때, 가장 가까운 경로인 3번 노드(10)를 선택해서 이동을 할 것이고, 이전에서 2번 노드와 4번 노드를 선택할 가능성을 고려하지 않고 다음 최종 목적지인 5번 노드(200)로 향하게 된다.

그럼 그리디 알고리즘을 사용하여 얻은 결과는 1 → 3 → 5 이고 그 결과 값은 210인 것을 확인할 수 있다.

하지만 실제 최적의 결과를 한번 확인해보면 결과가 105인 1 → 2 → 5 가 최적의 값임을 확인할 수 있다.

위 예시에서 확인할 수 있듯이 그리디 알고리즘에서 얻은 결과가 항상 최적의 값이 나오지는 않는 것을 확인해볼 수 있었다.

📖 그리디 알고리즘을 사용하기 위한 조건

1. 탐욕 선택 속성 (Greedy Choice Property)위 예시에서 첫 번째 선택(이전 선택)이 이후 선택(두 번째 선택)에 영향을 주게 된다. 그 이유는 최적의 값(경로)이 누적이 돼서 최종 결과를 얻을 수 있기 때문이다.
2. 탐욕 선택 속성이란 이전 선택이 이후 선택에 영향을 주지 않는 속성을 말한다.
3. 최적 부분 구조 (Optimal Substructure)위 예시에서 첫 번째 선택(부분 문제)의 결과가 두 번째 선택을 지나 최종 선택으로 갔을 때 결과에 적용되지 않는다.
4. 첫 번째(부분 문제)에 대한 결과는 최적의 결과 값이 맞지만 두 번째 선택까지 고려했을 때는 오히려 가장 좋지 않은 선택지가 된다.
5. 최적 부분 구조란 부분 문제의 최적의 결과가 최종 결과에도 그대로 적용될 수 있어야 한다.

이 두 가지 조건을 모두 만족하는지 확인하기 위해서는 대부분 수학적 증명이 함께 있어야 하고, 이는 매우 어렵다. 그래서 보통은 테스트 코드를 먼저 작성해서 원하는대로 동작을 하는지 확인하고, 반례를 1개라도 찾게된다면 그리디 알고리즘을 적용하기 힘들다는 것을 의미한다.

 

📖 그리디 알고리즘 예시

이 문제는 해당 링크에서 발췌해온 문제입니다. 개인적으로 한번에 이해하기에 좋았던 문제였습니다.

1. 활동 선택(Action Selection)활동 선택 문제는 N개의 활동이 있고 각 활동에는 시작 시간 및 종료 시간이 있을 때, 한 사람이 최대한 많이 할 수 있는 활동(Activity)의 수를 구하는 문제이다.즉, 각각의 활동(Activity)에는 시간이 소요되므로 하나를 선택했다면 그 동안 해당 시간에 다른 Activity를 할 수 없다. 이러한 상황일 때 가장 많은 활동에 참여하려면 어떻게 해야 할까?하지만 여기서 주의해야할 점은 활동 종료 시간이 빠른 활동을 선택하고나서 다음 활동을 선택할 때, 기존에 선택했던 활동 종료 시간(End Time)보다 다음 활동의 시작 시간(Start Time)이 겹치면 안 된다.

    다음 활동의 시작 시간 >= 이전 활동의 종료 시간

   이제 이런 알고리즘을 바탕으로 해서 문제를 해결해보자.
2. 다시 말해 다음 활동을 선택할 때 다음과 같은 조건을 만족하면 된다.
3. 가장 많은 활동에 참여하기 위한 알고리즘을 작성하기 위해서는 활동 종료 시간(End Time)이 가장 빠른 것을 위주로 선택을 해야 한다. 활동이 종료되는 시간이 빠른 것을 따라서 선택하다 보면 가장 많은 활동을 할 수 있기 때문이다.
4. 그리디 알고리즘의 가장 대표적인 예시인 활동 선택(Action Selection) 문제에 대해서 알아보자.

 

• 활동이 저장되어있는 배열을 정렬하기
  여기서 정렬할 때 주의해야 할 점은 우리는 “활동 종료 시간(End Time)”이 빠른 순서대로 활동을 선택할 것이다. 그럼 End Time을 기준으로 정렬(오름차순)을 하면 된다.
  
  
  
  정렬을 완료하면 위와 같은 배열을 얻을 수 있다. 그럼 이제 그리디 알고리즘을 사용해서 순서대로 데이터를 선택해보자.
• 그리디 알고리즘을 적용하기
  먼저 활동 d를 가장 먼저 선택하고 나서 다음 활동인 c가 선택될 수 있는 조건에 들어와 있는지 확인한다.
  
  
  활동 c가 끝나고 활동 b를 뽑아야 된다. 하지만 여기서 활동 c의 종료시간이 6이고, 활동 b의 시작 시간은 5이다. 그렇다는 것은 활동 c가 종료되고 활동 b를 진행할 수 없다는 것을 말한다. 그럼 다음 활동인 a를 뽑아서 조건을 확인한다.
  
  활동 f의 시작시간이 활동 a의 종료시간보다 크기 때문에 활동 f는 선택할 수 있다.
• 같은 방법으로 다음 활동 e를 뽑고, 활동 a의 종료 시간과 비교해본다. 활동 e의 시작시간이 더 작기 때문에 활동 e도 불가능하다. 그럼 다음 활동인 f를 뽑는다.
• 이전에 했던 활동 c의 종료 시간보다 활동 a의 시작 시간이 더 크기 때문에 활동 a는 선택할 수 있다.
• 활동 d의 종료 시간은 2이고, 다음 활동인 c의 시작 시간은 3이다. 즉, 활동 d 다음에 활동 c를 진행할 수 있다.

그리디 알고리즘의 최종 결과는 위 그림과 같다. 우리는 활동 `d → c → a → f` 를 선택했고, 최종적으로 4개의 활동을 할 수가 있다.

 

📖 코드로 작성해보기 (Java)

package selfstudy;

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

public class GreedyExample {
    public static void main(String[] args) {
        List<Activity> activities = new ArrayList<>(){{
            add(new Activity("a", 7, 8));
            add(new Activity("b", 5, 7));
            add(new Activity("c", 3, 6));
            add(new Activity("d", 1, 2));
            add(new Activity("e", 6, 9));
            add(new Activity("f", 10, 11));
        }};
        Collections.sort(activities); // 정의해준 compareTo에 따라서 정렬 진행

        for (Activity activity : greedy(activities)) {
            System.out.print(activity.toString() + " ");
        }
                System.out.println();
        System.out.println("최대 " + greedy(activities).size() + "개의 활동을 할 수 있습니다.");
    }

    public static List<Activity> greedy(List<Activity> activities) {
        List<Activity> result = new ArrayList<>();
        int PreviousActivityEndTime = 0;

        // 그리디 알고리즘의 선택 기준을 만족하기 위한 조건에 맞으면 선택
        for (Activity activity : activities) {
            if (activity.startTime >= PreviousActivityEndTime) {
                result.add(activity);
                PreviousActivityEndTime = activity.endTime;
            }
        }
        return result;
    }
}

class Activity implements Comparable<Activity> {
    String activityName;
    int startTime;
    int endTime;

    public Activity(String activityName, int startTime, int endTime) {
        this.activityName = activityName;
        this.startTime = startTime;
        this.endTime = endTime;
    }

    // Activity 객체의 정렬 기준을 설정한다. endTime 기준으로 오름차순 정렬을 진행
    @Override
    public int compareTo(Activity activity) {
        return this.endTime - activity.endTime;
    }

    @Override
    public String toString() {
        return this.activityName;
    }
}

우리가 이미 사전에 정의해뒀던 조건들이 위 코드에 모두 들어간다. 먼저 End Time 기준으로 오름차순 정렬에 대해서 알아보자.

@Override
public int compareTo(Activity activity) {
    return this.endTime - activity.endTime;
}

위 코드를 보면 우리는 List에 Activity라는 객체를 넣어서 정렬을 할 것이고, Comparable 인터페이스를 상속받아 compareTo의 기준을 재정의해줄 것이다.

위 코드대로 내 endTime과 비교 대상으로 들어온 객체의 endTime을 빼서 return 해주면 된다. 여기 까지하면 오름차순 정렬이 완성되고 다음은 다음 활동을 선택하는 기준에 대한 코드를 확인해보자

for (Activity activity : activities) {
    if (activity.startTime >= PreviousActivityEndTime) {
        result.add(activity);
        PreviousActivityEndTime = activity.endTime;
    }
}

정렬된 List인 activities를 for each문을 이용하여 하나씩 뽑아서 확인한다. 뽑아서 이전 활동의 endTime과 같거나 크다면 선택 기준을 만족하고, 선택된 활동을 새로운 List인 result에 넣는다.

위 코드를 실행해보면 다음과 같은 결과를 얻을 수 있다.

우리가 그림으로 그려서 확인해봤던 결과와 동일한 d → c → a → f 가 나오는 것을 확인할 수 있다.

🔎 Reference

알고리즘 - 그리디 알고리즘(Greedy Algorithm)