그리디(Greedy; 탐욕) 알고리즘

> 원본 노션 페이지 보러 가기 <

🚀 탐욕 알고리즘이란?

💡 순간마다 최적을 선택해서, 문제 해답에 도달하는 방법

• 최적해를 구하는데 사용되는 근시안적인 방법
  • 선택의 순간마다 최적을 고름
• 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제
  • 일반적으로, 떠오르는 생각을 검증없이 구현하면 Greedy 접근이 됨
  • 최종 결과가 최적이라는 보장은 없음
• 한 번 선택된 것은 번복하지 않음
  • 비교적 단순한 알고리즘이 됨
  • 제한적인 문제들에 사용

 

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

1. 선택 절차(Selection Procedure)
   • 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check)
   • 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check)
   • 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

🎈 탐욕 알고리즘 필수 요소

• 탐욕적 선택 속성 (greedy choice property)
  • 탐욕적 선택은 최적해로 갈 수 있음을 보여라 (탐욕적 선택은 항상 안전하다)
  • 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조 (optimal substurcture property)
  • 최적화 문제를 정형화하라
  • → 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남는다.
  • 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

💡 [원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해] 임을 증명하라

 

🚀 그리디 알고리즘 예시

• 분할 가능 배낭 문제 (Fractional Knapsack)
  • 배낭 짐싸기
• 활동 선택 문제 (Activity-selection)
  • 회의실 배정

 

🎈 예시 1) 동전 거슬러 주기

동전의 개수를 최소한으로 사용해서 거슬러 주고 싶다.

• 액수가 큰 동전 단위부터 사용한다.

 

🎈 예시 2) 배낭 짐싸기 (Knapsack)

도둑이 배낭에 물건을 담으려고 한다. 각 물건은 무게와 값이 지정되어 있다.
배낭은 무게 제한이 있으며, 값어치가 최대가 되도록 담고자 한다.

• 0-1 Knapsack
  • 배낭에 물건을 통째로 담아야 하는 문제
  • 물건을 쪼갤 수 없는 경우
  • 해결책
    • 완전 검색 방법 (모든 부분집합 구하기) : 시간 복잡도가 지수적 증가 $O(2^n)$
    • 탐욕적 방법
      1. 값이 비싼 물건부터 채운다 → 가벼운걸 여러개 담는게 더 비쌀 수 있다.
      2. 무게가 가벼운 물건부터 채운다 → 물건 하나가 더 비쌀 수 있다.
      3. 값/무게 비율이 작은 값부터 채운다 → 배낭의 빈공간이 생길 수 있으므로 최적해가 아닐 수 있다.

💡 0-1 Knapsack은 DP로 풀이할 수 있다.

 

• Fractional Knapsack
  • 물건을 부분적으로 담는 것이 허용되는 문제
  • 물건을 쪼갤 수 있는 경우

💡 값/무게 비율 값이 작은 것부터 담으면 최적해를 구할 수 있다.

 

🎈 예시 3) 회의실 배정 (활동 선택 문제 Activity-selection problem )

회의들의 시작시간과 종료시간이 주어진다. 하나의 회의실에서 진행할 수 있는 회의 수의 최대값을 구하고자 한다.

• 종료 시간 순으로 오름차순 정렬한다. [ O(nlogn) ]
• 모든 회의를 순회해서 계산을 진행한다. [ O(n) ]
  • 현재 회의 종료 시간과 다음 회의 시작 시간을 비교한다.
  • 현재 종료 시간 < 다음 회의 시작 시간 이라면, 회의를 진행할 수 있다. (개수 +1)
  • 다음 회의를 현재 희의로 사용하고 계산을 반복한다.

 💡 정렬에 대부분의 시간이 소요되므로 시간 복잡도는 O(nlogn) 이다.

 

🎈 예시 4) 동전 자판기 (동전 거슬러주기 탐욕 기법 응용)

음료수 자판기를 사용할 때 마다 최대한 많은 동전을 사용하고자 한다.
자판기는 거스름돈을 주지 않으므로, 매번 정확한 액수만 투입해야 한다.

• 오류
  • 최대한 많은 동전 수를 사용하고 싶어하니, 작은 동전부터 사용한다.
  • ⇒ 동전이 부족한 상황이 발생한다.
• 해결 방법
  • 초기 주어진 동전의 총합을 계산한다.
  • [총합 - (동전의 개수를 최소로 사용) == 음료수 값] 이 되도록 하면 동전을 최대한 사용할 수 있다.
  • 동전의 개수를 최소로 사용하는 건 동전 거슬러주기와 같은 알고리즘이다.

 

🚀 대표적인 탐욕 기법의 알고리즘들

알고리즘	목적	설명	유형
Prim	N개의 노드에 대한 최소 신장 트리(MST)를 찾는다.	서브트리를 확장하면서 MST를 찾는다.	그래프
Kruskal	N개의 노드에 대한 최소 신장 트리(MST)를 찾는다.	사이클이 없는 서브 그래프를 확장하면서 MST를 찾는다.	그래프
Dijkstra	주오진 정점에서 다른 정점들에 대한 최단 경로를 찾는다.	주어진 정점에서 가장 가까운 정점을 찾고, 그 다음 정점을 반복해서 찾는다.	그래프

 

🚀 Reference

• [알고리즘 - 이론] 0-1 KnapSack Problem and Fractional KnapSack Problem (0-1 배낭 문제, 분할 가능한 배낭 문제)
• [알고리즘] 탐욕 알고리즘(Greedy Algorithm)
• 탐욕(그리디) 알고리즘(greedy algorithm)