그리디 알고리즘

그리디 알고리즘

-      현재의 선택이 후에 끼칠 영향은 고려 안하고 매순간 최고의 선택만 하는 알고리즘

-      효과적, 직관적 / 최적의 답을 찾기에는 별로

-      바로 문제 유형 파악이 어려우면 그리디 알고리즘 의심

 

문제1. 큰 수의 법칙

#큰 수의 법칙  2020-12-15 17:10 시작 17:21 종료
N,M,K = list(map(int,input().split()))
list = list(map(int,input().split()))

list.sort(reverse=True)
res = 0
cnt = 0
for i in range(0,M):
    if cnt == K:
        res += list[1]
        cnt = 0
    else:
        res += list[0]
        cnt += 1

print(res)

 

 

문제2. 숫자 카드 게임

N,M = list(map(int,input().split()))
min_card=[]
for i in range(0,N):
    #list.append(list(map(int,input().split())))
    a=[int(x) for x in input().split()]
    min_card.append(min(a))

print(max(min_card))

 

 

문제3. 1이 될 때 까지

#1이 될 때까지 2020-12-15 17:52 시작 17:57 종료
N,K = list(map(int,input().split()))

cnt = 0

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

 

 

꿀팁

 

1260 == 1260 // 500 * 500 + 1260 % 500

-