알고리즘 이론 16강 - 그리디 알고리즘(Greedy Algorithm)

 

[그리디 알고리즘의 개요]

: 다이나믹 프로그래밍과 같이, 최적화 문제 해결에 사용된다.

: 다이나믹 프로그래밍은 종종 과잉될기도 하는데, 그럴때 그리디 알고리즘이 좀더 쉬운 형태의 코드이기도 하다.

: 문제가 그리디-선택 방법으로 해결된다

# 그리디-선택 특성 : 선택을 해야될때, 현 시점에서 가장 이득인 선택을 하는 방법

 

 

 

[그리디 전략(Greedy Strategy)]

: 각 결정 시점에서, "지역적(locally)"으로 가장 최선의 선택을 한다.

: 선택이 잠재적인 미래를 생각한 평가나 부분 문제 해결에 의존하지 않는다.

: 탑-다운(재귀) 알고리즘 구조 : 각 단계에서 문제를 더 작은 문제로 감소시킨다.

: 지역적 최선의 선택(당장 좋은거 선택 방법) => 결국 전역적으로도 최선 이라는 생각 기반

 

 

 

[그리디 알고리즘의 종류]

- Fractional knapsack 알고리즘(16)

- 허프만(Huffman) 코드(16)

- Kruskal's MST 알고리즘(23)

- Prim's MST 알고리즘(23)

- Dijkstra's Single Surce Shortest Path(SSSP) 알고리즘 등..

 

 

 

[그리디 알고리즘 실 예시]

# 액티비티 선택 문제 : 최대한 많은 놀이기구 타는 방법

# 투어 계획

# 손님 만족 계획

# 회의 스케쥴링 문제 등..

 

 

 

[그리디 알고리즘 예시1 - 돈 세기(Counting money)]

: 최소한의 동전과 지폐를 사용해 주어진 금액 맞추는 문제

주어진 돈의 단위 : $5, $1, 25c, 10c, 1c  이를 가지고 $6.39를 맞추기위한 최소한의 돈(지폐나 동전)의 개수는?

# 해결

  : 위와 같은 US 돈은 그리디 알고리즘을 사용해도 항상 최적화된 해결책이 나온다.

  : 하지만, 일부 가상의 통화체계(ex. 돈의 단위가 1kron, 7kron, 10kron로 15kron만들기)같은 경우에는 그리디 알고리즘이 최적의 해결책이 아니다.

# 이 예시에서 그리디 알고리즘이 최적 해결법이 아닌 이유   그리디 알고리즘으로 풀면 우선 10kron을 뽑기때문에 총 10korn 1개, 1kron 5개 => 6개의 동전이 필요.   하지만 최적의 풀이로 풀면, 7kron 2개, 1kron 1개 => 3개의 동전이 필요하다로 나온다.

 

 

 

[그리디 알고리즘 예시2 - 놀이기구 선택 문제(Activity-selection Problem)]

놀이기구의 집합 S안에 놀이기구 a1, a2 ... an이 있다. 이때 각 놀이기구의 시작시간 si과 종료시간 fi가 주어질때, 최대한 많은 놀이기구를 타기위한 집합 S의 부분집합 A를 구해라.

# 해결

1. 부분구조 최적화

최적 해결책이 놀이기구 ak를 가지고 있다고 가정하자 => 두개의 부분문제를 생성   1) a1... ak-1의 놀이기구에서 ak 시작 전에 끝나는 놀이기구 선택   2) ak+1 ... an의 놀이기구에서 ak 끝난 이후에 시작하는 놀이기구 선택 => 이 두개의 부분문제들이 최적화되어야 한다.

 

2. 재귀적 풀이법

Sij = S안의 놀이기구중, ai 놀이기구가 끝나고, aj 놀이기구 시작전에 있는 놀이기구들의 부분 집합 c[i,j] = Sij 안의 놀이기구들중 최대로 탈수있는 개수 # 재귀적 해결식   c[i,j] =                0                      if Sij = ⊙         =  max{ c[i,k] + c[k,j] + 1 }     if Sij ≠ ⊙ (단, k는 i<k<j)

 

3. 재귀적 풀이의 문제점(위가 기존 동적 프로그래밍 방식)

: 위와 같은 재귀적 알고리즘을 사용해 모든 가능한 부분집합을 확인하고, 반복되는 부분문제들이 존재한다..

 

4. 그리디 알고리즘 사용

우선 놀이기구를 종료시간 기준으로 정렬한다. 첫번째 놀이기구를 선정한뒤, 그 이후로는 정렬된 목록에서 이전 놀이기구 끝난 이후에 시작하는 다음 놀이기구 설정 놀이기구 더이상 없을때까지 반복   # 직감 : 그때그때 가능한 시간내에서 가장 짧은 놀이기구를 선택한다.

  # 그리디 알고리즘 해결법 의사코드

Greedy-Activity-Selection(s,f)   n := length[s]   A := {a1}    // 첫번째 놀이기구로 a1 놀이기구 선택   j := 1         // j는 직전에 탄 놀이기구 번호    for k:=2 to n do      // 종료시간대로 정렬된 놀이기구기때문에, 반복문 통해 직전 놀이기구 다음으로 탈수 있는 놀이기구 고르면     // 자동으로 쿨타임 짧은 놀이기구 선정     if sk >= fj       then A := A U {ak}     // 놀이기구 목록에 추가       j := k   Return A

  # 그리디 알고리즘 해결 예시

11개의 놀이기구 : (1,4),(3,5),(0,6),(5,7),(3,8),(5,9),(6,10),(8,11),(8,12),(2,13),(12,14)  일때, 결론 : (1,4),(5,7),(8,11),(12,14) : 이와 같은 결론이 최선의 선택인가?? # 증명 생략

 

 

 

[그리디 알고리즘 vs 다이나믹 프로그래밍]

: 둘다 최적화 부분구조를 찾는데 사용되는 기법

1) 다이나믹 프로그래밍 : 부분문제의 해결 기반으로 해결된다. (최적의 부분문제 탐색하는 방식으로)

2) 그리디 알고리즘 : 주어진 순간에서 최선의 선택을 하는 방식 기반으로 해결된다. (미래 생각 X, 과거 선택 변경 X)

 

# 그리디 알고리즘 ⊂ 다이나믹 프로그래밍

  : 그리디 알고리즘으로 풀수있는문제는 다이나믹 프로그래밍 방법으로 풀수있다. (하지만 반대로는 안됨)

 

# 어느 방법이 더 나은지 알기 어렵다..

  : 우선 다이나믹 프로그래밍 방법을 사용해 choice를 이해한다.

  : 그리고 그 선택이 지역적 최선 선택인지 확인한다.

  : 만약 그러면, 그리디 알고리즘 사용한다.