04. 그리디(Greedy) 알고리즘

• 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

---

04. 그리디(Greedy) 알고리즘

• 최적화 문제를 해결하는 알고리즘이다.

• 입력 데이터 간의 관계를 고려하지 않고, 수행 과정에서 최솟값 또는 최댓값을 가진 데이터를 선택한다.

  • 근시안적 선택으로 부분적인 최적해를 찾고, 이를 모아서 문제 전체의 최적해를 찾는다.

• 한번 선택하면 번복하지 않아서 알고리즘들이 비교적 단순하다.

---

4.1 동전 거스름돈

• 거스름돈의 동전 개수를 가장 적게 받는 방법

• 남은 액수를 초과하지 않는 조건에서 가장 큰 액면의 동전을 취하는 방법을 사용한다.

  Pseudo Code

  int CountCoin(int change)
  {
    int n500 = n100 = n50 = n10 = n1 = 0;
    while (change >= 500)
    {
      change -= 500;
      n500++;
    }
    while (change >= 100)
    {
      change -= 100;
      n100++;
    }
    while (change >= 50)
    {
      change -= 50;
      n50++;
    }
    while (change >= 10)
    {
      change -= 10;
      n10++;
    }
    while (change >= 1)
    {
      change -= 1;
      n1++;
    }
    return (n500 + n100 + n50 + n10 + n1);
  }

• 만약 160원짜리 동전이 추가된다면, 이 알고리즘은 최적해를 보장하지 못한다.

  • 어떤 경우에도 최적해를 찾고 싶으면 동적 계획 알고리즘을 사용해야 한다.

---

4.2 최소 신장 트리(Minimum Spanning Tree)

4.3 최단 경로 찾기(Shortest Path)

4.4 부분 배낭 문제(Fractional Kanpsack Problem)

4.5 집합 커버 문제(Set Cover Problem)

4.6 작업 스케줄링(Task Scheduling)

4.7 허프만 압축(Huffman Coding)