그리디(Greedy) 알고리즘

그리디 알고리즘의 정의

단어 그대로 번역하면 탐욕법인데 말 그대로 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

현재 상황에서지금 당장 좋은 것만 고른다.

지금 당장 가장 좋은 것만 고르기 때문에 현재의 선택이 나중에 미칠 영향에 대해 고려하지 않은 풀이를 한다.

 

그리디 알고리즘 원리

1. 여러 경우 중 하나 선택한다.
2. 선택시 마다 최적이라고 생각되는것을 선택한다.
3. 최종적인 해답에 도달한다.

그리디 알고리즘의 특징

1. 한번 선택된 것은 번복하지 않는다.
   → 대부분의 탐욕 알고리즘들은 단순하며, 제한적인 문제들에 적용한다.
2. 각 선택의 시점에서 이루어지는 결정은 지역적으로 최적이다.
   → 하지만 선택들을 계속 수집해 최종적 해답을 만들었다고 해서, 최적이라는 보장은 없다.

따라서 사용 가능유무를 잘 알아야 한다.

 

그리디 알고리즘의 과정

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

예)거스름돈 문제

문제: 카운터에는 거스름돈으로 사용한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정.

손님에게 거슬러 주어야 할 돈이 N원일 때, 거슬러 주어야 할 동전의 최소 개수는?

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이고 거슬러 주지 못할 경우는 없다.

문제 해결 과정:

1. 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐단위 부터 돈을 거슬러 준다.
2. N원을 거슬러 주어야 할 때, 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다.
3. →이후 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 된다.

풀이과정)

N = 1260원 이라면,

1. 500원 = 2개 → 남은돈: 260원
2. 500원 = 2개, 100원 = 2개 → 남은돈: 60원
3. 500원 = 2개, 100원 = 2개, 50원 = 1개 → 님은돈: 10원
4. 500원 = 2개, 100원 = 2개, 50원 = 1개, 10원 = 1개 → 남은돈: 0원

실행 가능성 검사

가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유

→ 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.

<구현>
n = 1260
count = 0

#큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
		count += n//coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 센다
		n %= coin #n = n % coin
print(count)

#시간 복잡도는 거슬러줘야 하는 금액과 무관하며, 동전의 총 종류에만 영향을 받기에 시간 복잡도는 O(화폐종류)이다.

 

➕참고

대표적인 그리디 기법의 알고리즘들

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

 

---

[참조]

https://m.blog.naver.com/sunbi5252/221977168061 #그리디 알고리즘의 개념들https://velog.io/@seongmini/Algorithm-탐욕법-Greedy-Algorithm #그리디 알고리즘 풀이https://thingjin.tistory.com/entry/그리디-알고리즘-Greedy-Algorithm-Python #그리디 알고리즘의 유형