그리디 알고리즘 with 백준 11047

11047번: 동전 0

알고리즘 분류 : 그리디 알고리즘

 

선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

 

그리디 알고리즘의 조건

 

1. 탐욕적 선택 속성 (Greedy Choice Property) : 앞의 선택이 이후에 영향을 주지 않는다.

2. 최적 부분 구조 (Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

백준 11047번의 입력 조건을 잘 보면 크기 순으로 정렬된 상태로 입력되기 때문에 정렬 알고리즘을 쓰지 않아도 된다.

 

대신 최적 해결 방법을 위해서 값이 큰 것부터 카운트 한다면 굳이 이전 카운트 값보다 작은지 비교할 필요가 없을 것이다.

 

그리고 파이썬에서 찾아본건데 i값이 큰값에서 감소하는 문법을 아래처럼 구현하는 것보다

for i in range(N-1, -1, -1):
	#blablabla

아래가 더 이해하기 쉬운거 같다. 다음부터 아래로 해보자.

for i in reversed(range(N)):
	#blablabla

 

 

아래 페이지에서 그리디 알고리즘에 대해 더 상세하게 잘 나와있어 참고하였다.

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬