그리디 알고리즘 . 1

그리디 알고리즘(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법

 

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. (like. 수학)

 

그리디 해법은 정당성 분석이 중요하다.

• 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다.

---

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

하지만 코딩 테스트에서의 대부분의 그리디 문제는 그리디로 얻은 해가 최적의 해가 되도록 세팅해 놓는다.

그리고 우린 이 문제가 그리디 문제인지 추론할 수 있어야 한다.

---

문제 : 거스름 돈

500원, 100원, 50원, 10원 동전이 무한히 있다. 손님에게 거슬러 주어야 할 돈이 N원일 때, 거슬러 주어야 할 동전의 최소 개수를 구하시오 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

 

결론 : 최적의 해를 빠르게 구하기 위해선 가장 큰 화폐 단위부터 거슬러 주면 된다.

 

Why???

 

정당성 분석 : 가지고 있는 동전 중에서 큰 화폐 단위가 항상 작은 화폐 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

(큰 단위가 작은 단위의 배수가 아니면 큰 단위부터 거슬러 주는 것이 무조건 최적의 해를 보장하지 않는다)

if : 800원을 거슬러 주어야 하는데 500원, 400원, 100이라면 어떻게 될까?  --> 가장 큰 화폐 단위부터 거슬러 주면 최적의 해 X

 

 

이처럼 그리디 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 정당성을 분석하여 검토할 수 있어야 함

N = 1260   #바뀔 수 있는 값
count = 0  #초기화

array = [500, 100, 50, 10]   #바뀌지 않는 값

for coin in array:   # i 대신 coin 으로 직관성,가독성 up
    count += N // coin   # 엄청 자주 나오는 skill 기억해두기
    N %= coin
    
print(count)

 

시간 복잡도 분석 : 화페의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K) 이다.

즉, 화폐의 종류만큼 반복을 수행하면 답을 도출할 수 있다는 뜻.

이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받는다.

 

 

 

[ 문제 : 그리디 알고리즘 문제에서 정당성 분석이 중요한 이유를 서술하시오. ]

 

 

 

(2024.12.24 복습)

코드로 구현할 때 문제의 단어 + 목표를 체크하기 :  500원, 100원, 50원, 10원, N, 동전 최소 개수(cnt)

큰 화폐 단위가 몇개 사용될까? :  / , % 연산자를 사용하면 알 수 있겠다

화폐 단위를 저장하는 공간도 필요하겠다 --> [ ] 배열에 넣어서 for문과 함께 활용하면 좋겠다