[Algorithm] Greedy(그리디) 개념 정리

 

 

수업시간에 교수님께서 그리디 알고리즘을 소개하실 때 단어 뜻 그대로 '탐욕' 알고리즘이라고 설명하셨던게 기억난다.

실제로 이 알고리즘은 가장 좋아보이는, 당장 좋은 것을 먼저 고르는 알고리즘이다.

대표적으로 동전 개수 구하기, 회의실 배정 등의 문제들이 있다.

 

 

 

무조건적으로 그리디가 최적해를 보장하지는 않기 때문에 (오히려 그리디로 최적의 해를 찾기 어렵다고 한다.) 그리디를 사용할 때는 문제 유형을 보고 판단하도록 하자. 동전문제는 그리디의 대표적인 문제인데, 이때 그리디 알고리즘으로 최적해가 보장되는 경우는 아래의 조건을 만족한 경우이다. 

 

- 동전의 액면이 모두 바로 아래 액면의 배수가 된다.

 

 

 

백준에 올라와있는 동전 문제는 주어진 동전들이 배수의 관계이므로 그리디 알고리즘을 사용하여 풀 수 있었다.

 

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

 

 

import sys

n, k = map(int, sys.stdin.readline().split())
m = []
num = 0

for i in range(n):
	m.append(int(input())  // 입력된 동전들을 배열 m에 저장
    
for i in range(n-1, -1, -1):   // 가장 숫자가 큰 동전부터 
	if k == 0:  // 남은 금액이 없을 때 (다 계산됐을때)
    	break
    if m[i] > k: // 동전이 남은 금액보다 클 때
    	continue // 다음 동전으로 건너뜀
   
   	num += k // m[i]  // 사용한 동전의 개수 num에 더해주기
    k %= m[i]    // 동전으로 나누고 남은 나머지 k에 저장
    
print(num)