알고리즘 - 그리디(Greedy)

 

 

 

 

 

 

 

그리디 알고리즘이란?

 

• 그리디 알고리즘은 매 순간 가장 최적의 선택을 하는 방식의 알고리즘이다.
• 계산이 빠르고 구현이 간단하다.
• DP(동적 계획법)에서 사용했던 타뷸레이션이나 메모이제이션과 같은 안전장치가 없기 때문에 결과적으로 최선의 답을 보장하지는 못한다.
• 탐욕 선택 속성(Greedy Choice Property)과 최적 부분 구조(Optimal Substructure)를 만족하는 문제에 적용이 가능한 알고리즘이다.

 

 

 

그리디 사용 예제

 

• 그리디 알고리즘은 길 찾기(다익스트라) 문제나 동전 거스름돈 문제, 혹은 최적의 적재 무게를 찾는 문제와 같이 최적의 선택이 최적의 해로 이어지는 문제들에 적합하다.

 

 

회의실 문제 예시 코드

 

• 해당 문제는 회의실을 예약을 희망하는 여러 인원 중 회의실에서 최대한 많은 회의를 배정하려면 어떻게 해야 하는지 처리하는 문제다.

 public static void Main()
 {
     // 회의 리스트 생성 (시작 시간, 종료 시간)
     List<Meeting> meetings = new List<Meeting>
     {
         new Meeting { Start = 1, End = 4 },  // 회의 1: 1시~4시
         new Meeting { Start = 3, End = 5 },  // 회의 2: 3시~5시
         new Meeting { Start = 0, End = 6 },  // 회의 3: 0시~6시
         new Meeting { Start = 5, End = 7 },  // 회의 4: 5시~7시
         new Meeting { Start = 8, End = 9 },  // 회의 5: 8시~9시
         new Meeting { Start = 5, End = 9 }   // 회의 6: 5시~9시
         new Meeting { Start = 7, End = 8 },   // 회의 7: 7시~8시
         new Meeting { Start = 4, End = 9 },   // 회의 8: 4시~9시
     };

     // 그리디 알고리즘 적용하여 최대 배정 가능한 회의 수 구함
     int maxMeetings = GreedyMeetingSchedule(meetings);

     Console.WriteLine($"최대 배정 가능한 회의 수: {maxMeetings}개");
}


 class Meeting
 {
     public int Start { get; set; }   // 회의 시작 시간
     public int End { get; set; }     // 회의 종료 시간
 }

 static int GreedyMeetingSchedule(List<Meeting> meetings)
 {
     // 회의 종료 시간을 기준으로 오름차순 정렬
     meetings.Sort((a, b) => a.End.CompareTo(b.End));

     int count = 0;
     int lastEndTime = 0;

     // for문을 사용해 회의 리스트 순회
     for (int i = 0; i < meetings.Count; i++)
     {
         if (meetings[i].Start >= lastEndTime)
         {
             // 회의 시작 시간이 이전 회의 종료 시간 이후일 때 배정
             count++;
             lastEndTime = meetings[i].End;  // 마지막 배정된 회의의 종료 시간을 갱신
             Console.WriteLine($"회의 배정: 시작 {meetings[i].Start}, 종료 {meetings[i].End}");
         }
     }

     return count; // 배정된 회의의 총 개수 반환
 }

 

 

 

 

코드 설명

 

• GreedyMeetingSchedule 함수: 그리디 알고리즘을 통해 최대한 많은 회의를 배정을 처리하는 함수
  • 회의 리스트를 종료 시간 기준으로 오름차순 정렬
  • 종료 시간이 가장 빠른 회의부터 배정하고, 이전 회의와 겹치지 않는 회의를 선택
• 회의 배정 조건: meeting.Start >= lastEndTime 조건을 사용해, 현재 회의가 이전에 선택된 회의와 겹치지 않는 경우에만 배정

 

 

 

 

 

 

 

거스름돈 문제 예시 코드

 

• 해당 문제는 잔돈을 거슬러 줄 때 가장 적은 갯수의 동전을 사용해서 잔돈을 거슬러 주려면 몇 개의 동전을 사용해야 하는지 찾아내는 문제다.

 

 public static void Main()
 {

     // 동전의 종류 (리스트로 변경)
     List<int> coins = new List<int> { 500, 100, 10, 50 };

     // 거슬러 줄 금액 입력
     Console.Write("잔돈을 입력하세요: ");
     int amount = int.Parse(Console.ReadLine());

     // 그리디 알고리즘 함수 호출
     int totalCoins = GreedyMinimumCoins(amount, coins);

     // 총 동전의 개수 출력
     Console.WriteLine($"총 사용한 동전의 개수: {totalCoins}개");
}


static int GreedyMinimumCoins(int amount, List<int> coins)
{
    int totalCoins = 0;

    // 리스트를 내림차순으로 정렬
    coins.Sort();
    coins.Reverse();

    // for문으로 동전 리스트 순회
    for (int i = 0; i < coins.Count; i++)
    {
        // 현재 동전으로 거슬러 줄 수 있는 최대 개수
        int coinCount = amount / coins[i];
        totalCoins += coinCount;

        // 남은 금액 계산
        amount %= coins[i];

        // 동전의 개수를 출력
        if (coinCount > 0)
        {
            Console.WriteLine($"{coins[i]}원 동전 {coinCount}개");
        }
    }

    return totalCoins; // 총 사용한 동전의 개수를 반환
}

 

 

 

 

 

코드 설명

 

 

• GreedyMinimumCoins 함수: 그리디를 사용해 가장 동전을 적게 사용하는 방식으로 설계했다.
  • 동전을 종류별로 정렬한 후 내림차순으로 정렬
  • 가장 큰 금액의 동전부터 사용하고 남은 금액을 계산

 

 

 

위와 같이 동전의 유형이 500원, 100원, 50원, 10원으로 이루어 진 상황에서는 효과적으로 동작한다.

 

하지만 큰 수부터 처리하다 보니 동전의 유형이 다음과 같이 바뀌면 제대로 동작하지 못한다.

 

List<int> coins = new List<int> { 500, 400, 100 };

 

 

 

 

 

• 잔돈은 여전히 800원을 거슬러 주어야 하며 500원이 아니라 400원부터 사용하면 400원 동전 2개를 사용해서 최적의 동전 갯수는 2개로 끝나야 한다.

 

• 하지만 첫번째 최적의 선택 순간에서 400원이 아닌 500원을 사용하는 것이 최적의 선택으로 판단하기 때문에 위 문제는 그리디 알고리즘을 활용하면 올바르게 문제를 해결 할 수가 없다.

 

 

 

 

 

 

 

그리디 알고리즘의 핵심

 

• 그리디 알고리즘에서 가장 중요한 점은 그리디를 구현하는 것 보다 문제를 그리디로 해결하기 좋은지 판단하는 능력이다.
• 부분 문제에서 내린 최선의 선택이 전체 문제를 해결하는 데에도 최선의 선택이 될 수 있는가를 항상 고민해야 한다.
• 따라서 문제를 분석하여 그리디 선택 속성과 최적 부분 구조가 성립하는지 판단해야 그리디로 문제를 올바르게 해결할 수 있다.