📘그리디 알고리즘란?
탐욕 알고리즘이라고도 하는 그리디 알고리즘은 문제를 해결할 때마다 그 순간에 최적이라고 생각되는 선택을 해나가는 방식으로 문제를 해결하는 방법이다. "탐욕스럽게" 각 단계에서 최선의 선택을 하여 최종적인 해답에 도달하는 것이다. 이 방식은 매 선택 시점에서 지역적으로 최적인 결정을 하기 때문에 각 단계에서의 최선의 선택이 전체적으로도 최선이라는 보장은 없다.
✅그리디 알고리즘의 특징
- 단순하고 직관적: 문제를 해결하는 데 있어서 간단하게 접근할 수 있다.
- 구현이 용이: 복잡한 기법보다 코딩하기 쉽다.
- 지역 최적화: 각 단계에서 최적의 해를 선택하기 때문에, 전체적으로는 최적이 아닐 수도 있다.
✅그리디 알고리즘 구현 방법
- 해 선택: 현재 상황에서 가장 좋아 보이는 해를 선택한다.
- 실행 가능성 검사: 선택된 해가 문제의 조건을 만족하는지 확인한다.
- 해 검증: 전체 문제의 해결이 될 때까지 위 두 과정을 반복한다.
✅그리디 알고리즘 문제 예시
문제 설명
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬로 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 10의 배수이다.
예를 들어 입력으로 주어진 N이 1,260이라면 다음과 같이 가장 큰 화폐 단위로부터 거슬러 주는 과정을 통해 1,260원을 모두 거슬러 줄 수 있다.
문제 해결
step 0 초기 단계 - 남은 돈: 1,260원
| 화폐 단위 | 500 | 100 | 50 | 10 |
|---|---|---|---|---|
| 손님이 받은 개수 | 0 | 0 | 0 | 0 |
step 1 남은 돈: 260원
| 화폐 단위 | 500 | 100 | 50 | 10 |
|---|---|---|---|---|
| 손님이 받은 개수 | 2 | 0 | 0 | 0 |
step 2 남은 돈: 60원
| 화폐 단위 | 500 | 100 | 50 | 10 |
|---|---|---|---|---|
| 손님이 받은 개수 | 2 | 2 | 0 | 0 |
step 3 남은 돈: 10원
| 화폐 단위 | 500 | 100 | 50 | 10 |
|---|---|---|---|---|
| 손님이 받은 개수 | 2 | 2 | 1 | 0 |
step 4 남은 돈: 0원
| 화폐 단위 | 500 | 100 | 50 | 10 |
|---|---|---|---|---|
| 손님이 받은 개수 | 2 | 2 | 1 | 1 |
따라서 N이 1,260일 때 손님이 받은 동전의 최소 개수는 6개이다.
n= 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]
for coin in coin_types:
# 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
count += n // coin
n %= coin
print(count)코드를 보면 화폐의 종류만큼 반복을 수행해야 한다. 따라서 화폐의 종류가 N개라고 할 때 시간 복잡도는 O(N)이다. 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.
📚그리디 알고리즘 vs 다이나믹 프로그래밍
그리디 알고리즘과 다이나믹 프로그래밍은 모두 최적화 문제를 해결하기 위한 알고리즘 기법이지만, 접근 방식과 적용하는 문제의 유형에서 차이를 보인다.
1. 접근 방식
- 그리디 알고리즘은 매 순간 최적이라고 생각되는 결정을 내리면서 문제를 해결한다. 이 방식은 각 단계에서의 최적의 결정이 전체적인 최적의 결과로 이어진다는 보장이 없다.
- 다이나믹 프로그래밍은 문제를 더 작은 하위 문제로 나누고, 각 하위 문제의 결과를 저장하여 이를 재사용함으로써 전체 문제의 최적 해를 찾는다. 이 방식은 문제의 구조가 '최적 부분 구조'와 '중복되는 부분 문제'라는 두 가지 특징을 가질 때 효과적이다.
2. 메모리 사용
- 그리디 알고리즘은 추가적인 저장 공간을 많이 필요로 하지 않는다. 현재 선택에만 집중하기 때문이다.
- 다이나믹 프로그래밍은 이전에 계산한 값을 저장하기 위해 종종 많은 메모리를 사용한다. 이 저장된 값들은 문제의 다른 부분을 해결하는 데 재사용된다.
3. 문제 유형
- 그리디 알고리즘은 문제가 '탐욕적 선택 속성'을 가지고 있을 때 적합하다. 즉, 각 단계에서의 최적의 선택이 전체 문제에 대한 최적의 해결책으로 이어진다는 속성이 있을 때 적합하다.
- 다이나믹 프로그래밍은 주어진 문제가 최적 부분 구조를 가지며, 같은 하위 문제들이 반복적으로 발생하는 경우에 적합하다. 즉, 전체 문제의 해결이 그 문제의 부분 문제들의 해결에 의존하고, 이 부분 문제들이 반복적으로 나타나는 구조를 가지고 있을 때 유리하다.
4. 성능
- 그리디 알고리즘은 일반적으로 빠르고 효율적이지만, 항상 최적의 결과를 보장하지 않는다.
- 다이나믹 프로그래밍은 문제를 체계적으로 접근하여 최적의 해를 보장하지만, 때로는 계산 시간과 메모리 사용이 많을 수 있다.
결론적으로, 그리디 알고리즘은 각 단계에서의 최선의 선택이 전체 문제 해결에 최선이라는 보장이 필요한 문제에 적합하고, 다이나믹 프로그래밍은 문제의 최적 부분 구조와 중복되는 하위 문제들을 효율적으로 해결할 수 있을 때 적합하다.
출처
이것이 취업을 위한 코딩 테스트다 with 파이썬
