[Algorithm] Greedy

📣
본 포스트는 ‘이것이 취업을 위한 코딩 테스트다 with 파이썬’을 공부하고 작성하였습니다 :)
click > (이코테 2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬

Greedy

이론

당장 좋은 것만 선택하는 그리디

Greedy 알고리즘은 ‘탐욕적’ 이라고 불리며 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’을 의미한다.

다른 알고리즘과 비교했을 때 ‘사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형’으로 문제 출제의 폭이 매우 넓고 창의력을 요구하기 때문에 다익스트라 알고리즘 처럼 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기는 어렵다.

[예제 3-1] 거스름돈

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인
coin_types = [500, 100, 50, 10]

for coin in coin_types:
	count += c // coin
	n %= coin

print(count)

실전문제

[실전문제 1] 큰 수의 법칙

단순하게 반복문을 사용해서 푸는 방법. (M의 크기가 100억 이상이면 시간초과! )

# solution_1
N, M, K = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
answer = 0
for i in range(M):
	if i % (K + 1) == K:
		answer += arr[-2]
	else:
		answer += arr[-1]
print(answer)

반복되는 수열을 이용하여 푸는 방법

# solution_2
N, M, K = map(int, input().split())
arr = list(map(int, input().split()))

arr.sort()
answer = 0
cnt = M // (K + 1)
answer = arr[-1] * (M - cnt) + arr[-2] * cnt
print(answer)

[실전문제 2] 숫자 카드 게임

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 출력

N, M = map(int, input().split())

arr = []
for i in range(N):
	arr.append(min(list(map(int, input().split()))))
print(max(arr))

[실전문제 3] 1이 될 때까지

최대한 많이 나누기 + N이 K의 배수가 되도록 효율적으로 한번에 빼는 방식

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

answer = 0
while N > 1:
	if N % K == 0:
		answer += 1
		N /= K
	else:
		answer += int(N % K)
		N -= (N % K)
		if N == 0:
			answer -= 1
print(answer)