- 그리디 알고리즘
: 현재 상황에서 지금 당장 좋은 것만 고르는 방법
-> 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
예제 3-1) 거스름돈
n원 받고 500원, 100원, 50원, 10원짜리 동전으로 거슬러줘야 할 최소 개수
@ 나의 풀이
import sys
input = sys.stdin.readline
n = int(input())
coin500 = int(n/500)
coin100 = int(n%500/100)
coin50 = int(n%100/50)
coin10 = int(n%50/10)
print(coin500 + coin100 + coin50 + coin10)-> 그냥 단순하게 500, 100, 50, 10으로 나누고 얻은 나머지를 통해서 개수를 다 더해서 구함
@ 책의 풀이
n = int(input())
count = 0
coin_list = [500, 100, 50, 10]
for coin in coin_list :
count += n // coin
n %= coin
print(count)-> 리스트에 500원, 100원, 50원, 10원 순서대로 넣고 반복문을 통해 count에는 각 금액으로 나누었을 때 개수를 더하고, n은 각 금액으로 나눈 나머지를 넣어 구함
==> 나의 문제점
: 너무 단순하게 대입하지 말고, 반복문 잘 사용하기
(백준 5585번과 유사)
실전문제 2) 큰 수의 법칙 (p.92)
@ 책의 풀이
n, m, k = map(int, input().split(" "))
a = list(map(int,input().split(" ")))
a.sort()
num1 = a[n-1]
num2 = a[n-2]
count = 0
while True :
for _ in range(k) :
if m == 0 :
break
count += num1
m-=1
if m == 0 :
break
count += num2
m-=1
print(count)a라는 리스트에 수를 받고, sort를 이용해 크기 순서대로 정렬한다. a에서 가장 큰 수와 두번째로 큰 수를 알아내고, 가장 큰 수를 k번 더하고 두번째로 큰 수를 한 번 더하는 방법으로 문제를 해결하면 된다.
==> 나의 문제점
: sort()를 아직 외우지 못했음.
- sort()
: 리스트를 제자리에서 정렬한다. sort()가 호출되면 원본 리스트가 변경된다.
ex) a.sort()- sorted()
: 리스트의 원본을 유지하고 새로이 정렬한다. sorted()는 정렬된 새로운 리스트를 반환한다.
ex) sorted(a)
(리스트의 연산정리 파이썬 책 p258 참고)
응용
n, m, k = map(int, input().split(" "))
a = list(map(int,input().split(" ")))
a.sort()
num1 = a[n-1]
num2 = a[n-2]
count = 0
count += (m//k)*k*num1
count += int(m%k)*num2
print(count)a를 정렬하는 것까지는 위와 같다. 가장 큰 수를 k번씩 더할 수 있기 때문에 m/k를 해서 k번을 몇 번 더할 수 있는 지 구하고 m%k 나머지로 두번째로 큰 수를 몇 번 더할 수 있는지 알아내고 합을 구하면 된다.
실전문제 3) 숫자 카드 게임 (p.96)
처음부터 문제를 잘 이해하지 못했다. 풀이를 봐도 사실 정확하게 이해하지 못했지만 일단 이해해보려고 노력했다. 다른 사람들의 풀이를 살펴보니 아래와 같이 풀어야 하는 것 같다.
=> 각 행의 작은 숫자들 중에서 가장 큰 숫자를 뽑아야 한다는 말이다.
n, m = map(int, input().split())
list_num = []
result = 0
for i in range(n) :
list_num = list(map(int, input().split()))
result = max(result, min(list_num))
print(result)배열을 받고, 그 안에서 가장 작은 수를 구한다. 그리고 반복문을 통해 작은 수들끼리 가장 큰 수를 찾아내서 출력하는 문제이다.
실전 문제 4) 1이 될 때까지 (p.99)
@ 나의 풀이
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
i = 0
while True :
if n % k == 0 :
n = int(n/k)
i += 1
else :
n -= 1
i += 1
if n == 1 :
break
print(i)일단 잘 돌아가긴 하는데 책에는 이 풀이가 아예 없는 걸로 봐서 효율적인 코드는 아니라고 생각했다.
@ 책의 풀이
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
result = 0
while True :
target = (n//k)*k
result += n-target
n = target
if n<k :
break
n//=k
result += 1
result += n-1
print(result)n을 k로 나눈 몫을 다시 k와 곱하면 n보다 작고 k로 나눌 수 있는 가장 큰 수가 나온다.
n-target은 k로 나눈 나머지값이므로 어쨌든 1씩 빼야하기 때문에 결과값에 저장해둔다.
그 다음에 1씩 빼고 k로 나눠질 수 있는 값이 target이기 때문에 n은 target
반복문이 계속 돌아가면서 n이 k보다 작으면 멈추고 크면 n을 k로 나눈다. 어차피 나머지가 없기 때문에 1을 결과값에 더한다.
n이 k보다 작으면 1씩 빼주는데 n이 1이 될 때까지니까 n-1을 한 값을 결과값에 더해주면 몇 번 반복했는지 알 수 있다.
