Greedy

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 코테에서 만나게 될 그리디 유형은 ‘사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형’
  • 정렬, 최단 경로 등은 사용법 알고 있어야 해결 가능
• 많은 유형 접해보고 문제 풀면서 훈련
• 코테에서는 창의력 능력 요구 = 즉, 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지 파악할 수 있어야
• 가장 좋은 것을 선택 = 가장 큰 순서대로, 가장 작은 순서대로 등 기준 제시해줌
• 그리디 알고리즘은 주로 정렬 알고리즘과 짝을 이뤄 출제

백준 문제 풀이

1789_수들의 합

s = int(input())
sum = 0
n = 0

for i in range(1, s+1):
    sum += i
    n += 1
    if sum > s:
        n -= 1
        break

print(n)

1449_수리공 항승

n, l = map(int, input().split())
d = list(map(int, input().split()))
d.sort()

end = 0
index = 0
for i in d:
	if i > end:
    	end = i + l -1
        index += 1
print(index)

11501_주식

T = int(input())

for _ in range(T):
	N = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    result = 0
    tmp = 0
    
    for i in a:
    	if tmp > i:
        	result += (tmp - i)
        elif tmp < i:
        	tmp = i
            
	print(result)

15903_카드 합체 놀이

import headq

n, m = map(int, input().split())

cards = []
card_list = [int(x) for x in input().split()]

for card in card_list:
	headq.headpush(cards, card)
    
for _ in range(m):
	card1 = headq.heappop(cards)
    card2 = headq.heappop(cards)
    
    heapq.heappush(cards, card1 + card2)
    heapq.heappush(cards, card1 + card2)
    
print(sum(cards))

2212_센서

n = int(input())
k = int(input())

sensor = list(map(int, input().split())
sensor.sort()

arr = []

for i in range(0, n-1):
	arr.append(sensor[i + 1] - sensor[i])
    
arr.sort()

print(sum(arr[:n-k])