[Advanced] 3. 탐욕 알고리즘 - 이론편

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

여러 경우 중 하나 선택 → 최적이라고 생각되는 것을 선택 → 최종 해답에 도달

• 최적화 문제를 해결하는 알고리즘
  • 탐욕 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법
• 최적화 문제 : 최적(최대값이나 최소값같은) 값을 구하는 문제
  • 여러 해가 있을 수 있음
• 한 번 선택된 것은 번복하지 않음
  • 단순, 제한적인 문제들에 적용
• 각 선택의 시점에서 이루어지는 결정은 지역적으로 최적의 값
  • 최종적 해답이 최적이라는 보장은 없음!

 

탐욕 알고리즘 수행과정

1. 해 선택
   현재 상태에서 부분 문제의 최적해를 구한 뒤, 부분 해 집합에 추가
2. 실행가능성 검사
   새로운 부분 해 집합의 실행가능 여부 확인, 문제의 제약 조건 위반 검사
3. 해 검사
   새로운 부분 해 집합이 문제의 해가 되는지 확인 
   전체 문제의 해가 완성되지 않았다면 1로 돌아가 다시 시작

 

동전 거스름돈 문제에 적용

❔ 문제 : 손님이 지불한 금액에서 지폐와 동전의 개수를 최소화하여 거스름돈을 지불하는 방법 찾기

1. 해 선택
   가장 좋은 해 선택 → 현재 고를 수 있는 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가
2. 실행가능성 검사
   거스름돈이 손님에게 줄 액수를 초과하는지 확인,
   초과할 경우 마지막에 추가한 동전을 거스름돈에서 빼고, 1로 돌라가서 한 단계 작은 단위 동전 추가
3. 해 검사
   "거스름 돈 문제의 해 = 손님에게 줄 액수"가 맞는지 확인,
   일치하면 종료, 불일치하면 1로 돌아가 과정 반복

 

문제점

❓ 거슬러 줄 금액이 800원이고, 동전의 종류가 {500, 400, 100, 50, 10}이라면 ?

400원 2개가 최적의 해이지만, 탐욕 알고리즘은 500원 1개+100원 3개를 택하게 된다.

❗ 완전 검색을 이용!
800원에서 완전 검색 → 나머지 금액에서 완전 검색 → 0보다 작거나 같은경우 리턴 (재귀)
0인 리프 노드의 깊이가 가장 작은 방법 채택

---

배낭문제

❔ 문제 : 도둑이 물건을 훔치기 위해 보관 창고에 침입 → 물건은 배낭에 담음(배낭은 담을 수 있는 물건의 무게가 고정) → 창고에는 여러개의 물건들이 있고 각각의 물건에는 무게와 값이 정해져 있음 → 경비원들에게 발각되기 전에 배낭의무게를 초과하지 않으면서 값의 총합이 최대가 되도록 물건을 선택해서 담기.
즉, 배낭이 수용할 수 있는 무게를 초과하지 않으면서, 값의 총합이 최대가 되도록 하려면?

• S = {item1, item2, ... ,itemn}
• wi = itemi의 무게, Pi = itemi의 값
• W = 배낭이 수용가능한 무게

❕ Knapsack 문제 유형

• 0-1 Knapsack
  물건을 쪼갤 수 없고 통째로 담아야 함
• Fractional Knapsack
  물건을 쪼개어 부분적으로 담을 수 있음

 

0-1 Knapsack

❗ 0-1 Knapsack : 완전 검색

1. 완전 검색으로 물건들의 집합 S에 대한 모든 부분집합을 구함
2. 부분 집합의 총 무게가 W를 초과하는 집합 버림
3. 나머지 집합에서 값이 가장 큰 집합 선택

※ 물건의 개수가 증가하면 시간 복잡도가 지수적으로 증가 
   부분집합의 수 : 2^n

❗ 0-1 Knapsack : 탐욕 알고리즘1

1. 값이 비싼 물건부터 채움
2. 무게가 W 초과하면 중단

※ 최적해를 구할 수 없음

❗ 0-1 Knapsack : 탐욕 알고리즘2

1. 무게가 가벼운 물건부터 채움
2. 무게가 W 초과하면 중단

※ 최적해를 구할 수 없음

❗ 0-1 Knapsack : 탐욕 알고리즘3

1. 무게 당 값이 높은 순서로 물건 채움 (1kg 당 가격)
2. 무게가 W 초과하면 중단

※ 최적해를 구할 수 없음

탐욕 알고리즘으로는 최적해를 구할 수 없음

 

Fractional Knapsack

위에서 본 탐욕 알고리즘3으로 구할 수 있음

❗ 0-1 Knapsack : 탐욕 알고리즘3

1. 무게 당 값이 높은 순서로 물건 채움 (1kg 당 가격)
2. 무게가 W 초과하면 중단

---

활동 선택 문제 - 회의실 배정 문제

❔ 문제 : 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태.
    회의는 시작 시간과 종료 시간 존재. 시간이 겹치면 동시에 개최 불가능.
    최대한 많은 회의가 열리기 위해 어떻게 배정하면 될까?

• 집합 A = {a1, a2, ... , an} 
• ai = (si, fi) # 시작 시간, 종료 시간
• A에서 서로 겹치지 않는 최대 개수의 활동집합을 구하는 문제

❗ 종료 시간 순으로 활동들 정렬

S0,n+1 은 a0의 종료 시간부터 an+1의 시작 시간 사이에 포함된 활동들
S0,n+1 = {a1, a2, a3, a4, a5, a6, a7, a8, a9, a10}

❗ 탐욕 알고리즘

공집합이 아닌 문제 Si,j가 있고 Si,j에 속한 활동 am은 종료 시간이 가장 빠른 활동

1. 종료 시간 순으로 활동들 정렬
2. 문제 Si,j에서 종료 시간이 가장 빠른 활동 am을 선택
3. Si,m은 공집합이므로, am을 선택하면 공집합이 아닌 하위 문제 Sm,j가 생김
4. 2,3 의 과정을 반복

항상 최적해를 구할 수 있음!

 

최적해를 구한다는 것에 대한 증명

• 탐욕적 선택 속성(Greedy choice property)
  • 탐욕적 선택은 항상 안전하다는 것을 보여야 함
• 최적 부분 구조(Optimal substructure property)
  • 최적화 문제를 정형화 - 하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남음
  • "원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해" 임을 증명

 

탐욕 알고리즘과 동적 계획법의 비교

탐욕 알고리즘	동적 계획법
매 단계에서, 가장 좋아 보이는 것을 빠르게 선택 - 지역 최적 선택	매 단계의 선택은 해결한 하위 문제의 해를 기반으로 함
하위 문제를 풀기 전에 (탐욕적)선택이 먼저	하위 문제가 우선 해결되어야 함
Top-Down 방식	Bottom-Up 방식
일반적으로 빠르고 간결	좀더 느리고 복잡

 

Baby-Gin 다시보기

Baby-Gin 문제 탐욕 알고리즘으로 풀기

1. 6개의 숫자를 0~9 숫자를 나타내는 counts 리스트에 개수로 표시한다.
   

   

2. run(연속숫자 3개)을 조사후 run 데이터 완전 삭제
   

   

3. Triplete 조사후 Triplete 데이터 완전 삭제
   

   

4. 리스트가 전부 0이 되면 Baby-Gin!

 

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

알고리즘	목적	설명
Prim	N개의 정점으로 구성된 최소 신장 트리(MST)를 찾음	정점을 하나씩 선택하는 과정에서 트리를 확장하면서 MST를 찾음	그래프
Kruskal		싸이클이 없는 서브 그래프들을 확장하면서 MST를 찾음	그래프
Dijkstra	주어진 정점에서 다른 정점들에 대한 최단 경로를 찾음	주어진 정점에서 가장 가까운 정점을 선택하면서 출발점에서 다른 모든 정점들의 최단경로를 찾음	그래프
Huffman coding	문서의 압축을 위해 문자들의 빈도수에 따라 코드 값을 부여함	출현 빈도가 낮은 문자부터 선택해서 이진 트리를 완성하고 코드값을 부여함	문자열