[Algorithm] 탐욕(Greedy) 알고리즘이란

안녕하세요. Harry입니다.

 

본 포스팅의 목적은, 코딩테스트를 준비함에 있어 스스로 공부한 지식을 정리하고자 합니다.

 

- 무슨 개념인지?

- 개념이 나오게 된 배경은?

- 그 개념은 왜 쓰는지?

- 장점/단점은 무엇인지?

- (유사한 것이 있다면) 서로 차이는 무엇인지?

 

를 최대한 고려하여 정리해보겠습니다.

 

1. 그리디 알고리즘이란?(what?)

what is greedy algorithm?

그리디 알고리즘은, 당장 좋은 것만을 고르는 알고리즘이다. 즉, 당장 주어진 선택지 중에서 눈앞에 보이는 가장 최적의 상황을 고르는 것으로, 그 이후에 발생할 상황을 고려하지 않는다는 것이다. 

그러므로 직관적이지만 국소적(local)이므로 결과론적(global)으로 봤을 때 항상 최적의 해답을 보장하지 않는다.

예를 들어, 현재 선택할 수 있는 선택지 중에서 '가장 큰 순서 선택, 또는 가장 작은 순서 선택' 등이 있다.

 

문제를 유심히 보면, 가장 큰, 가장 작은, 가장 높은 등 최적을 표현하는 어휘가 등장한다.

 

 

2. 어떤 것이 불편해서/또는 무엇을 위해서 그리디 알고리즘이 나오게 된거야?(배경)

동적 프로그래밍 & 그리디 알고리즘 모두 특정 문제에 대한 최적의 해를 찾기 위한 방법이다. 

 

동적 프로그래밍(Dynamic Programming)은 전체 문제를 여러 개의 작은 하위 레벨의 문제로 나눈 후, 각 하위 레벨 문제의 해결방안을 합하여 최적의 해를 도출하는 방식이다.

허나 동적 프로그래밍의 특성 상 전체 방법을 두고 비교하여 최적의 방법을 찾는 것이기 때문에 시간 측면에서 비효율적이다.

 

알고리즘 활용 시 시간 복잡도 측면에서 최대한 시간을 줄이는 방법을 고려해야하는데, 시간 측면에서 동적 프로그래밍은 비효율적이기 때문에, 최적해 방법을 찾는 문제에서 동적 프로그래밍의 시간 효율을 개선하고자 그리디 알고리즘이 탄생하게 됐다.

 

3. 그리디 알고리즘 왜 써?(why?)

비교적 빠른 시간 내 계산을 완료하여 어느 정도 최적의 해와 근사한 답을 찾기 위해 사용한다.

 

4. 그리디 알고리즘의 장/단점은?

장점 : 빠른 시간 내 계산을 통해 시간복잡도를 줄일 수 있다.

단점 : 항상 최적의 해를 보장하지 않기 때문에 사용 가능한 조건이 성립하는지 검증하는 과정이 필요하다.

 

5. 그리디 알고리즘을 통해 최적의 해를 도출하기 위한 조건

1) 탐욕스러운 선택 속성(Greedy Choice Property)

앞에서 선택한 것이 타 선택 과정에 영향을 미치지 않는 독립 사건이어야 한다.

2) 최적의 부분 구조(Optimal Substructure)

문제의 최적의 해는 각 부분 문제에 대한 최적의 해로 구성되어야 한다.

 

6. 그리디 알고리즘을 활용하기에 적합한 유형은?

1) 매트로이드(Matroid) (Metroid 게임 아님)

- 매트로이드가 정확히 무엇인지 아직 제대로 알지 못했다,,,,너무 어렵

2) 최소 신장 트리 구하기(프림 알고리즘,크루스칼 알고리즘)

- 최소 신장트리 란, 그래프 내 N개의 정점은 그대로 두고, N-1개의 간석으로 모든 정점을 잇는 트리를 만드는 것이다.
이때 최소 신장 트리의 가중치 최소값을 구해야하는 경우, 매 선택마다 가장 작은 가중치를 가진 간선을 골라야하기 때문에 그리디 알고리즘을 활용하기 적합하다.

3) 회의실 시간 배정

- 공용 회의실에서 최대한 많은 팀이 공용회의실을 사용하기 위한 방법을 찾을 때 가능하다.
회의 시간이 적은 팀을 우선적으로 배치하면 되기 때문이다.

4) 거스름돈

- 단, 거슬러 줄 수 있는 동전 중에서 큰 단위의 동전이 항상 작은 단위의 동전의 배수여야 한다. 즉, 큰 단위의 동전을 배제하고 작은 단위의 동전으로만 조합하여 다른 해가 나오면 안된다는 말이다.

이 문제의 경우, 거스름돈에서 큰 단위의 동전 순대로 거슬러 줄 수 있는 만큼 거슬러 준 후, 그 아래 단위 동전에게 바통을 넘기는 식이기 때문이다.

5) 큰 수의 법칙

- "특정 리스트 내 구성된 요소를 이용하여 7번 더했을 때 최대값을 구하시오. 단,같은 인덱스의 값이 3번 이상 반복되면 안됨"

위와 같은 문제도 그리디 알고리즘을 이용하여 풀어야하는데, 리스트를 정렬하여 가장 마지막에 있는(즉, 리스트 내 가장 큰) 수를 더할 수 있을 만큼 더하고, 2번째로 큰 수를 한번 더하고, 다시 반복할 수 있을 만큼 가장 큰수를 더하는 식으로 계산해야한다.

4번의 거스름돈 문제하고 같은 원리이다.(바통 터치!!)

6) 숫자 카드 게임(최소,최대의 숫자가 포함된 카드의 행/열 찾기)

- 입력받은 전체 행에서 중 가장 작은 수가 포함된 행은 몇번째 행인지 출력하시오.

7) 특정 수(N)를 1이 될때까지 주어진 조건을 최소한으로 사용하여 수행

- 여러 조건 중 가장 빠르게 숫자를 떨어뜨릴 수 있는 조건을 가장 먼저 쓸 수 있을만큼 쓰고, 그 다음으로 빠르게 숫자를 떨어뜨릴 수 있는 조건을 쓸 수 있을 만큼 써야한다.

 

예를 들어, 

- 조건 1 : N에서 -1 한다.

- 조건 2 : N을 x로 나눈다.

- 조건 3 : N과 x를 더한다.

라고 한다면, 조건 3은 쳐다도 보지말고, 조건 2를 최대한 활용할 수 있는 것을 먼저 생각해야한다.

만약 N = 29, x = 3 이라면, 조건 1을 두번 써서 29 -> 27로 만들고 빨리 3으로 나뉘버리는 것이다.

 

7. 결론

아직 코드 구현까진 거의 안해봤지만, 어느 정도 개념은 잡힌 것 같다.

내가 이해하기론, 대다수의 문제가 바통터치가 키워드. 순서는 가장 쎈 놈부터.

가장 쎈 놈이 할 수 있는 최선을 다하고 그 다음 쎈 놈에게 바통터치. 그 다음에 다시 가장 쎈 놈이 받아서 끝낼지, 아니면 힘이 강한 순서대로 순차적으로 바통터치하여 끝낼지..는 문제에 따라 다를 것.

또는 가장 쎈 놈이 최적의 힘을 발휘할 수 있는 수준까지 빠르게 도달하고, 가장 쎈 놈이 슈슈슉 빠르게 끝내버리는 것.

(가장 쎈 놈 = 목표값에 도달하기 위해 가장 효율적인 조건)

 

감사합니다.