그리디 | Greedy

---

내가 볼려고 작성한 알고리즘 공부.

💾 그리디 알고리즘 (Greedy Algorithm)

✅ 1. 개념 이해하기

그리디 알고리즘(Greedy Algorithm) 은 매 순간 가장 좋아 보이는 선택을 하는 방식으로, 국소 최적 해(Local Optimal) 를 반복해서 전역 최적 해(Global Optimal) 에 도달하고자 하는 전략이다.

📌 특징

항목	설명
결정 기준	현재 시점에서 가장 최선인 것 선택
사용 조건	탐욕적 선택이 전체 문제에서도 최적 해를 보장할 때
장점	빠르고 구현이 간단함 (O(N log N) 이하)
단점	항상 최적의 해를 보장하진 않음 (반례 주의)

그리디 알고리즘은 “최적 부분 구조”와 “탐욕적 선택 속성”이 만족되는 문제에서만 사용 가능하다.

✅ 2. 대표 예제

2.1 동전 거스름돈 (백준 11047)

동전 종류가 주어졌을 때, 가장 적은 개수의 동전으로 금액을 거슬러 주는 문제

• 조건: 동전 단위가 배수 관계일 때 (ex: 1, 5, 10, 50, 100, 500)

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
coins.sort(reverse=True)

count = 0
for coin in coins:
    count += k // coin
    k %= coin

print(count)

• 핵심: 가장 큰 동전부터 최대한 사용하면 항상 최소 개수가 된다.

2.2 회의실 배정 (백준 1931)

N개의 회의 요청이 있을 때, 겹치지 않게 가장 많은 회의를 선택하는 문제

n = int(input())
meetings = [tuple(map(int, input().split())) for _ in range(n)]
meetings.sort(key=lambda x: (x[1], x[0]))  # 끝나는 시간 기준 정렬

end_time = 0
count = 0
for start, end in meetings:
    if start >= end_time:
        count += 1
        end_time = end

print(count)

• 핵심: 일찍 끝나는 회의부터 선택하면 이후 회의를 더 많이 넣을 수 있음

2.3 최소 회의실 개수 (프로그래머스 Lv3 유사 문제)

모든 회의를 수행할 수 있도록 필요한 회의실 개수의 최솟값을 구하는 문제 (우선순위 큐 사용)

import heapq

intervals = [(1, 4), (2, 5), (7, 9)]
intervals.sort()  # 시작 시간 기준 정렬
heap = []

for start, end in intervals:
    if heap and heap[0] <= start:
        heapq.heappop(heap)
    heapq.heappush(heap, end)

print(len(heap))  # 필요한 회의실 개수

✅ 3. 그리디 알고리즘 사용 판단 기준

1. 정렬 후 선택 문제인가?
2. 탐욕적 선택이 이후 선택에 영향을 주지 않는가?
3. 탐색이 아닌 직관적 해법으로 풀 수 있는가?

일반적으로 정렬 + 반복문 조합이 많고, 코드가 간단한 편이다.

✅ 4. 그리디 연습 문제 추천

난이도	문제 링크
⭐	백준 11047 - 동전 0
⭐⭐	백준 11399 - ATM
⭐⭐⭐	백준 1931 - 회의실 배정
⭐⭐⭐⭐	프로그래머스 - 단속카메라

✅ 5. 문제 풀이

• 백준 11047 - 동전 0

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
l = [int(input()) for _ in range(n)][::-1]
cnt = 0
for v in l:
    cnt += k//v
    k = k%v
print(cnt)

• 백준 11399 - ATM

n,m = int(input()),0
l = sorted(list(map(int,input().split())))
for i in range(len(l)):
    m += l[i]*(n-i)
print(m)

• 백준 1931 - 회의실 배정

import sys
input = sys.stdin.readline
n=int(input())
g = sorted([list(map(int,input().split())) for _ in range(n)], key = lambda x: (x[1],x[0]))
cnt = 0
tmp = 0
for s,e in g:
    if tmp <= s:
        cnt+=1
        tmp = e
print(cnt)

• 프로그래머스 - 단속카메라

def solution(routes):
    r = sorted(routes, key = lambda x: (x[1],x[0]))
    cnt=1
    a=r[0][1]
    print(r)
    for s,e in r[1:]:
        if a<s:
            a=e
            cnt+=1
    return cnt