[알고리즘] Greedy Algorithm, 그리디(탐욕) 알고리즘

1. 그리디(탐욕) 알고리즘의 정의

 

미래를 고려하지 않고 오직 현재 시점에서 가장 좋은 선택

예) 잔돈 반환 프로그램 - 사용할 수 있는 가장 큰 동전부터 최대 사용 가능한 양만큼 쓰고 밑으로 차근차근 내려가며 동전의 개수를 최소로 사용하게 하는 방법, 6800원이 들어왔다면 5000원 한 장을 낼 때 뒤에 어떤 돈들이 쓰일 지 고려하지 않음

 

2. 그리디 알고리즘의 특징

 

이 알고리즘은 항상 최적을 보장하지 못함, 현재의 최적 해가 전체의 최적 해를 보장하지 않음

예) 마시멜로를 참으면 10분 뒤에 두 개를 먹을 수 있지만, 그리디 알고리즘에 따르면 하나를 먹는게 최선임

 

따라서 항상 최적 해를 찾아야 하기 때문에 최적 해가 보장되는 조건에서만 그리디 알고리즘을 사용해야함

 

조건1 - 현재의 선택이 미래에 영향을 미치지 않음

예) 서울 - 대전 - 부산 경로를 선택하는데 서울 - 대전 갈 때 어떤 경로를 선택하더라도 대전 - 부산 경로에 영향을 미치지 않음

이러한 조건을 '탐욕스런 선택 조건 (Greedy Choice Property)' 라고 함

 

조건2 - 부분의 최적 해가 모이면 전체의 최적 해가 됨

예) 전 문제에서 서울 - 부산의 최적 해를 구한 값이 서울 - 대전, 대전 - 부산의 최적 해의 합과 같음

이러한 조건을 '최적 부분 구조 조건 (Optimal Substructure)' 라고 함

 

조건3 - 그리디 전략

예) 하나의 회의실을 사용하고자 하는 N개의 사용 요청을 입력받고, 각 요청은 회의 시작 시간과 종료 시간 정보를 제공하는데 겹치지 않는 회의를 최대한 많이 진행하려면 가장 중요한 부분은 회의 종료 시간이기 때문에 종료 시간이 가장 짧은 순으로 정렬하고 종료 시간 전에 시작하는 회의들은 배제하고 그 다음 짧은 회의를 배치하여 최적 해 보장

 

사용 이유 : 매우 빠르지만 최적 해를 보장하지 않기 때문에 근사치만 나와도 만족스러운 부분들에서 사용, 네비게이션도 100% 최적 해를 찾긴 힘들겠지만 근사치로 괜찮은 경로를 추천해줌