[Python] 알고리즘의 종류, 종류별 예제 _ 그리디 (1/7)

개념

현재 상황에서 지금 당장 좋은 것만 고르는 방법

예제1 (p.92)

큰 수의 법칙

#1 m이 10000이하인 경우
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
start = time.time()
data.sort()
max1 = data[len(data) - 1]
max2 = data[len(data) - 2]
for i in range(0, m):
    if (i != 0)&(i % k == 0):
        result += max2
    else:
        result += max1
print(result)

#2 m이 10000이하여도 가능한 방법
n, m, k = map(int, input().split())
data = list(map(int, input().split()))
start = time.time()
data.sort()
max1 = data[len(data) - 1]
max2 = data[len(data) - 2]

group = max1 * k + max2
result = group * (m // k) + max1 * (m % k - (k - 1))
print(result)

예제2 (p.96)

숫자 카드 게임

#작성
import time
n, m = map(int, input().split())
arr = []
for i in range(0, n):
    arr.append(list(map(int, input().split())))
start = time.time()
min_list = []
for i in range(0, n):
    min_list.append(min(arr[i]))
max_value = max(min_list)
idx = min_list.index(max_value)
print(min(arr[idx]))
print(f"time : {time.time()-start}s")

#min비교
import time
n, m = map(int, input().split())
result = 0

for i in range(0, n):
    data = list(map(int, input().split()))
    result = max(result, min(data))
print(f"time : {time.time()-start}s")

예제3 (p.99)

1이 될때까지

import time
n, k = map(int, input().split())
start = time.time()
cnt = 0
while(n != 1):
    if n % k == 0:
        n = n / k
    else:
        n -= 1
    cnt += 1
print(cnt)
print(f"time : {time.time()-start}s")