Greedy Algorithm(탐욕 알고리즘)

탐욕 알고리즘 이란?

• 'Greedy'는 '탐욕스러운, 욕심 많은'이란 뜻.
• 말 그대로 선택의 순간마다 추후의 일은 생각하지 않고, 최적의 상황만을 쫓아 해답에 도달하는 방법.
• 단순하고 직관적인 접근 방식을 갖고 있으며, 최적의 해를 찾는 데 효과적일 수 있다.
• 하지만, 선택의 순간에 대해 지역적으로만 최적.
• 선택들을 수집하여 최종적인 해답을 만들었다고 그것이 최적이란 보장이 없다.

탐욕 알고리즘 문제를 해결하는 방법

1. 선택할 수 있는 후보군 정의하기: 각 단계에서 어떤 선택을 해야 할지 후보군을 정의. 이때, 후보군은 가능한 해 중에서 최적의 선택을 의미.
2. 선택 기준 정의하기: 후보군 중에서 어떤 기준으로 선택할지 정의. 이는 문제의 최적화 조건에 따라 달라짐.
3. 선택하기: 선택 기준에 따라 후보군 중에서 최적의 선택을 하고, 해당 선택을 해결책에 추가.
4. 제약 조건 확인하기: 선택을 한 후에도 문제의 제약 조건을 만족하는지 확인. 제약 조건을 위반하는 선택이라면 해당 선택을 버리고, 다른 후보를 고려.
5. 반복하기: 1~4 단계들을 반복하면서 최종 해결책을 구성. 각 단계마다 최적의 선택을하여 해결책을 점진적으로 구축.

탐욕 알고리즘을 적용하기 위한 선제조건

1. 탐욕 선택 속성(Greedy Choice Property): 각 단계에서의 선택이 현재 상황에서 가장 최적인 선택이여야 함.
   다른 선택을 고려할 필요 없이 현재 상황에서의 최적 선택만을 고려해야 함.
2. 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제의 최적해들로부터 구성될 수 있어야 함. 큰 문제를 작은 부분 문제로 나누어 해결할 수 있어야 함.

• 위의 조건이 성립하지 않을 경우, 탐욕 알고리즘은 최적해를 구하지 못함.
• 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있음.
• 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요함.
• 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있음.
• 이러한 구조를 '매트로이드'라고 함.

매트로이드란?

• 매트로이드(Matroid)는 조합 최적화 문제를 다루는 수학적 구조 중 하나로, 독립성과 교환성의 개념을 기반으로 정의되는 추상적인 개념.
• 여러 개의 원소로 구성된 집합과 그 집합의 부분집합들 간의 관계를 표현하는 수학적 구조로도 사용됨.
• 매트로이드의 특징
  • 독립성: 매트로이드 내의 각 원소들은 서로 독립적으로 선택될 수 있음.
    즉, 매트로이드 내의 어떤 부분집합이 다른 부분집합의 원소들로 표현되지 않는 경우 그 부분집합은 독립적인 부분집합.
  • 교환성: 매트로이드 내에서 원소를 교환해도 독립성을 유지. 즉, 한 원소를 추가하고 다른 원소를 제거하여 독립성을 유지하는 조작이 가능.

탐욕 알고리즘의 예시

1. 거스름돈 문제

   • 주어진 돈을 가장 적은 동전 개수로 거슬러 주는 문제. 각 동전의 가치가 배수 관계가 아니더라도, 가장 큰 가치의 동전부터 사용하여 거스름돈을 줄일 수 있음.
   • 매트로이드의 독립성: 각 동전은 독립적인 단위. 하나의 동전을 선택하더라도 다른 동전에는 영향을 주지 않음.
   • 매트로이드의 교환성: 선택된 동전 중 하나를 다른 동전으로 교체하더라도 여전히 최소한의 동전 개수로 돈을 거슬러 줄 수 있음.
     가령 1원 동전을 5원 으로 교체하여도 여전히 총 돈전 개수를 최소로 유지하면서 돈을 거슬러 줄 수 있음.

2. 회의실 배정 문제

   • 여러 개의 회의가 주어지고, 회의실 하나만 사용할 수 있을 때, 최대한 많은 회의를 진행하는 문제. 회의의 종료 시간을 기준으로 정렬한 뒤, 가능한 많은 회의를 선택.
   • 매트로이드의 독립성: 각 회의가 시작 시간과 종료 시간을 가지며, 매트로이드의 독립성을 시작 시간을 기준으로 활용. 각 회의는 독립적으로 선택될 수 있으며, 선택된 회의들은 다른 회의들과 겹치지 않은 독립적인 관계.
   • 매트로이드의 교환성: 시작 시간이 빠른 회의부터 선택, 선택된 회의들과 겹치지 않는 다른 회의로 교체하면서 최대한 많은 회의를 배정. 이때, 교환성에 의해 선택된 회의를 배정하더라도 최대한 많은 회의를 배정할 수 있음.