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

[이코테] 당장 좋은 것만 선택하는 그리디

• 그리디 Greedy

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

  • 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

  • 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘 !

    → 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 은밀히 제시

[예제 3-1] 거스름돈

그리디 알고리즘의 정당성

실전 문제

큰 수의 법칙

숫자 카드 게임

1이 될 때까지

[백준] 문제 풀이

이분 탐색 단계

11047 동전 0

N, K = map(int, input().split())
coin = [int(input()) for _ in range(N)]
n = 0

for i in range(N):
    if coin[N-i-1] <= K:
        n += K // coin[N-i-1]
        K = K % coin[N-i-1]
    if K == 0:
        break

print(n)

11399 ATM

N = int(input())
arr = sorted(list(map(int, input().split())))
m = 0

for i in range(N):
    m += arr[i] * (N-i)

print(m)

1541 잃어버린 괄호

• 시도1: eval 쓰려구 했음 → error

arr = input().split('-')
ans = sum(list(map(int, arr[0].split('+'))))
for i in arr[1:]:
    ans -= sum(list(map(int, i.split('+'))))
print(ans)

13305 주유소