~54일차~
1. 탐욕 알고리즘 (Greedy Algorithm)
- 현재 상황에서 당장 가장 좋아 보이는 상황만을 선택하는 알고리즘
- 주로 최적의 해를 구하기 위한 근사적인 방법으로 사용
2. 예시
- 루트에서 출발하여 단말 노드까지 가는 경우
거쳐가는 노드의 합이 가장 큰 경우를 구하자.
보기에는 1 - 4 - 5가 가장 큰 값이지만,
탐욕법은 인접한 값 중 가장 큰 노드를 선택하기 때문에 이미지와 같이 최적의 값을 내지는 못한다.
3. 탐욕 알고리즘과 근사 해
- 단순한 탐욕 알고리즘은 최적의 해를 놓칠 수 있다.
- 하지만, 최적의 해에 가까운 답을 뱉는 것을 고려하면
-> "근사 해"를 구하는 목적으로 사용되곤 한다.
4. 코딩 테스트에서의 탐욕 알고리즘
- 일반적인 채점 시스템은 참가자의 코드 결과가 정해진 결과와 같은지를 확인
- 탐욕 알고리즘 유형을 낼 경우, 탐욕법으로 최적의 해가 보장되는 문제가 출제 됨
5. 탐욕 알고리즘의 접근 방법
- 방법 고안 : 현재 상황에서 어떤 것을 선택할지 알고리즘을 고안
- 정당성 확인 : 자신이 고안한 알고리즘이 항상 최적의 해를 보장하는지 확인 (증명 단계)
6. 거스름 돈 문제
- 전형적인 탐욕 알고리즘의 예시
카운터에 500원, 100원, 50원, 10원짜리 동전이 무수히 많이 존재하고,
손님에게 6480원을 거슬러 주어야 할 때, 동전 개수의 최솟값은?
1) 해결 방법
- 가장 큰 화폐 단위부터 거슬러주는 것
- 4단계를 거쳐 정답을 도출
① 500원으로 거슬러 줄 수 있는 만큼 거슬러 준다.
② 100원
③ 50원
④ 10원
2) 정당성 분석
- 큰 화폐 단위부터 선택하여 최적의 해를 찾을 수 있는 이유는?
=> 각 화폐 단위가 배수 관계에 속하기 때문
