[알고리즘] 그리디 (0) -그리디 알고리즘

 

 

 

🧐 그리디 알고리즘

그리디 알고리즘이란 매 단계마다 현재 상태에서 최적의 해를 만들어주는 것을 선택하며 진행하는 알고리즘입니다.

 

주로 최적화 문제(Optimization problem)에서 많이 사용되는 알고리즘으로,

대부분의 문제들에서 그리디 알고리즘은 최적해(global-optimal)를 보장해 주지는 않으나 일부 문제들에 한하여 global-optimal 하거나 그에 매우 근접함을 보장해 주는 경우가 있습니다.

 

 

 

 

 

 

 

 

⭐️ 그리디 알고리즘 예시

N개의 숫자가 들어있는 바구니가 있습니다.

이 중 그 수들의 합이 최대가 되도록 m개를 고르고 싶습니다.

 

이러한 경우 그리디 알고리즘을 통해 매 단계에서 현재 바구니에 남아있는 숫자들 중, 제일 큰 숫자를 고른 뒤, 이를 m 번 반복함으로써 문제를 해결할 수 있습니다.

 

 

 

 

 

 

 

 

 

🧐 그리디 알고리즘의 증명

그리디 알고리즘을 사용하는 경우, 해당 알고리즘이 반환하는 것이 정말 global-optimal 인지 증명해보아야 합니다.

 

대부분의 경우 그리디 알고리즘에 대한 증명은 귀류법(proof by contradiction)을 통해 진행됩니다.

 

예시를 통해 확인하도록 하겠습니다.

 

 

 

⭐️ Claim

위 예시의 그리디 알고리즘은 optimal solution(최적해)를 return 한다.

 

 

⭐️ Proof By Contradiction

일반적으로 다음과 같은 과정을 거칩니다.

집합 $S = \left\{ n_1, ..., n_m\right\}$ 을 그리디 알고리즘으로 뽑은 m개의 숫자( $n_1 \geq n_2 \geq ... \geq n_m$ 이라 가정)라고 하고,
S의 원소의 합이 최대가 아니라 가정하겠습니다. 

그러면  optimal solution 에 포함되는 선택되지 않은 임의의 수 $n'$ 에 대하여,
집합 $S' = S \ \left\{ n_m \right\} \cup \left\{ n'\right\}$ 의 원소들의 합은 $S$ 의 원소들의 합보다 커야 합니다.
그러나 $n_m $ 은 그리디 알고리즘에 의해 언제나 바구니에서 m번째로 큰 수이므로, 그리디 알고리즘에 대하여 모순입니다.

 

 

 

 

 

 

 

다음 포스팅부터 그리디 알고리즘에 대해 살펴보도록 하겠습니다.