알고리즘) 그리디(탐욕) 알고리즘

루트 노드부터 시작하여 매 순간의 가장 큰 값을 선택하는 알고리즘

-> 일반적 상황에서는 최적의 해를 보장할 수 없을 때가 많다

하지만 코테에서는 탐욕법을 사용하여 얻은 해가 최적의 해가 되는 상황에서 그리디를 추론할 수 있으면 됨

 

1. 거스름돈 문제

500원 100원 50원 10원짜리 동전이 무한히 존재한다고 가정하고

거슬러 주어야할 돈이 N원일 때, 거슬러줘야하는 돈이 항상 10의 배수일 때

동전의 최소 개수를 구하시오

 

=> 그리디 알고리즘으로 가장 큰 화폐단위 부터 돈을 거슬러주면 된다

=> 큰 단위가 작은 단위의 배수이기 때문

=> 큰 단위가 작은 단위의 배수가 아니라면 그리디 알고리즘으로 풀 수 없다

=> 거스름돈의 시간 복잡도는 O(K)(동전의 종류 개수에 영향을 받는다)

 

2. 1이 될 때 까지

N,K는 양의 정수이고 각각 2 이상일 때, N을 K로 나누거나 1을 뺄 수 있다

N이 1이 될 때 까지 진행하는데 가장 적은 실행으로 1을 만든다

=> 최대한 많이 나누는 것이 가장 적은 실행 결과를 준다

=> 나누어지지 않으면 -1을 한다