[#1] 그리디 알고리즘 with python

참고 출처 :

이것이 코딩테스트다 with 파이썬

---

그리디 알고리즘 = 탐욕법

>> 가장 큰 순서대로 or 가장 작은 순서대로와 같이 기준을 제시해줌.

 

그리디 알고리즘 대표 문제 : 거스름돈

 

>>

가장 큰 화폐 단위부터 돈을 거슬러준다.

책에 나와있는 방법 (더 간단..)

>> for문과 list를 이용해서 간단하게 작성하기 연습...

coin_types 리스트에는 나눠야 하는 동전의 종류를 넣는다.

count는 동전이 개수

 

 

문제 유형을 파악하기 어려울 때 그리디 알고리즘 문제를 의심

-> 이게 아니라면 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 문제를 해결할 수 있는 지 체크 체크

---

<큰 수의 법칙 : 문제1>

좀 더 효율적인 방법

---

<숫자 카드 게임 : 문제2>

min 함수 이용

>> 굳이 2중리스트를 만들지 않아도 min함수를 이용하면 간편하게 할 수 있음.

함수 1행씩 검사할때마다 가장 작은 수를 찾아내고, 

result와 좀 전에 찾아낸 가장 작은 수 중에 큰 숫자를 result 변수에 다시 저장

 

2중 반복문 이용

---

<1이 될 때까지 : 문제4>