[이코테] chapter03 그리디

아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다.

 

그리디(greedy) 알고리즘

: 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘

그리디는 최적의 해를 보장할 수 없을 때가 많음
but, 코딩 테스트에서의 대부분의 그리디문제는 탐욕법으로 얻은 해가 최적의 해!

 

정당성 분석 필수!

---

3-1.py 동전 문제 - ⭐1/3 (❌)

N = int(input())
cnt = 0

coinType = [500, 100, 50, 10]

for i in coinType:
    cnt += N // i
    N %= i
print(cnt)

정당성: 큰 수의 화폐가 모두 작은 수의 화폐의 배수임.

동전을 타입별로 리스트에 넣어 사용

 

 

3-2.py 큰 수의 법칙 - ⭐1/3 (⭕15m 30s)

N, M, K = map(int, input().split())
data = list(map(int, input().split()))
cnt = 0
result = 0
data.sort()

for _ in range (M) :
    if cnt == K :
        result += data[N-2]
        cnt=0
        continue
    result += data[N-1]
    cnt+=1

print(result)

가장 큰 수와 두 번째로 큰 수 알아내기

[교재 풀이] 가장 큰 수가 더해지는 횟수를 아래와 같이 구하면 반복문을 사용하지 않을 수 있음.

cnt = int(M / (K + 1)) * K + M % (K + 1)

 

 

3-3.py 숫자 카드 게임 - ⭐1/3 (⭕14m 57s)

N, M = map(int, input().split())
val = [0]*N

for i in range(N):
    data = list(map(int, input().split()))
    val[i] = min(data)

print(max(val))

min(), max() 사용

 

 

3-4.py 1이 될 때까지 - ⭐1/3 (⭕05m 30s)

N, K = map(int, input().split())
cnt = 0

while True:
    if (N % K == 0):
        N = N // K
        cnt += 1
    else:
        N -= 1
        cnt+=1
    if N == 1:
        break
print(cnt)

[교재 풀이] N이 100억 이상의 큰 수가 되는 경우를 가정했을 때도 빠르게 동작하기 위해서는 N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 작성하는 것이 좋음.

n, k = map(int, input().split())
result = 0
while True:
    target = (n//k)*k
    result += (n - target)
    n = target
    if n < k:
        break
    result += 1
    n //= k
result += (n-1)	# 1이 될 때까지 빼준 횟수를 더하는 거임
print(result)

n = 25 k = 3
target = 24
result = 1
n = 24
result = 2
n = 8

target = 6
result = 4
n = 6
result = 5
n = 2

target = 2
result = 5
n = 2

result = 5