[Python] 이것이 코딩테스트다 3장 Greedy

거스름돈

 

 

 

🔑 Key Point 

가장 큰 화폐 단위부터 거슬러 주며 그 나머지를 이용하는 것

 

 

 

 

---

 

큰 수의 법칙 

 

 

🎨 처음 짠 코드

직관적으로 짠다면 이 문제는 for 문이 1~2개 필요하다. 

하지만 📌 반복문을 사용하지 않고, 구현이 가능한 아이디어 가 있다.

 

 

 

 

🎨 반복문을 사용하지 않는 BEST 코드

 

아이디어는 이렇다. 이 문제에서 가장 큰 수는 6이며, 그 다음 큰 값은 5이다.  이 두가지만 번갈아 쓴다면 답을 구할 수 있다. 

 

 

 

 

🔑 Key Point 

 

간과했던 부분은 📌똑같이 반복되는 구간이 발생한다는 점 이다.

 

 

 

6

6

6

5

 

6

6

6

5

...

 

 

 

M의 수에 따라 만족하는 만큼 위의 과정이 반복된다. 

나누기를 잘 이용하면 몇번 반복되는지 알 수 있기 때문에 , 반복문이 필요 없다.

 

 

 

#가장 큰 수가 더해지는 횟수 계산
count = int(m/(k+1)) * k
count += m % (k+1)


result = 0 
result += (count) * first # 가장 큰 수 더하기
result += (m-count) * second # 두 번째로 큰 수 더하기

 

 

---

 

 

숫자 카드 게임

 

 

 

 

 

🔑 Key Point 

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것.

 

 

 

---

 

 

1이 될 때까지

 

 

🎨 직관적으로 짠 코드

직관적으로 이 문제를 푼다면 아주 쉬운문제가 된다.

 

 

 

 

🎨 좀 더 효율적인 코드

 

 

 

🔑 Key Point 

몫을 이용한다면 -1 씩 빼주는걸 일일히 while문을 돌릴 필요 없이 한번해 해줄 수 있다.

 

 

 

 

 

---

그리디 알고리즘의 정당성

 

<거스름돈> 문제에서 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이기 때문에, 그리디 알고리즘으로 구한 답이 최적의 해가 보장이 된다. 

만약 아니라면 최적의 해가 아닐 수 있다. 

 

📌 따라서, 그리디 알고리즘의 아이디어를 떠올릴 때에는 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.