알고리즘 - 그리디

개념은 그리디 알고리즘은 매 순간 가장 좋아 보이는 선택(최선의 선택)을 반복해 전체 문제를 해결하는 방식.

전체 최적해를 고려하지 않고 현재 상태에서의 최적 선택만을 기반으로 한다는 점에서 단순하지만, 항상 정답을 보장하지는 않는다.

적용 조건은 그리디 알고리즘이 최적해를 보장하기 위해서는 두 가지 조건을 만족해야 한다

탐욕 선택 속성 (Greedy Choice Property)

현재 단계에서의 최적 선택이 전체 최적해로 이어져야 함

과거의 선택이 이후에 영향을 미치지 않아야 함

예시는 활동 선택 문제

종료 시간이 빠른 활동을 먼저 고르면 이후 가능한 활동 수가 극대화됨

최적 부분 구조 (Optimal Substructure)

문제의 최적해가 부분 문제들의 최적해로 구성될 수 있어야 함

예시는 거스름돈 문제 (500, 100, 50, 10원)

→ 가장 큰 단위의 동전부터 선택하는 것이 항상 전체 최적해로 이어짐 (단, 동전 단위가 배수일 경우)

적용 판단 기준 (Check List)

판단 질문	설명
현재 선택이 이후에 영향을 주지 않는가?	탐욕 선택 속성 만족 여부
부분 문제의 최적해로 전체 문제를 만들 수 있는가?	최적 부분 구조 확인
선택 기준이 명확한가?	"가장 작다", "가장 빠르다" 등의 기준
정당성 분석이 가능한가?	항상 최적해를 보장하는지 논리적 설명 가능해야 함

기본 해결 절차

1. 최적해 조건 파악
2. 선택 기준 정의 (우선순위 정렬 기준 등)
3. 반복적으로 선택 수행
4. 선택 결과가 유효한지 확인 (조건 만족 여부)
5. 전체 해답 도출 후 정당성 검토

대표 문제 예시

활동 선택 문제

목표는 겹치지 않게 가장 많은 활동 선택

전략은 종료 시간이 가장 빠른 활동부터 선택

activities = [(1, 4), (3, 5), (0, 6), (5, 7)]
activities.sort(key=lambda x: x[1])  # 종료시간 기준 정렬

selected = [activities[0]]

for act in activities[1:]:
    if act[0] >= selected[-1][1]:
        selected.append(act)

print(selected)  # 최대 비겹치는 활동 목록

시간복잡도: O(n log n) (정렬) + O(n)

곱하기 혹은 더하기

목표는 숫자 문자열에서 가장 큰 수 만들기

전략은 숫자나 결과 중 하나라도 0 or 1이면 더하고, 아니면 곱하기

data = input()
result = int(data[0])

for ch in data[1:]:
    num = int(ch)
    result = result + num if num <= 1 or result <= 1 else resu
    lt * num

print(result)

1이 될 때까지 문제

목표는 N을 1로 만드는 최소 연산 횟수 (나누기 vs 빼기)

전략은 나누기가 가능하면 최대한 나누고, 아니면 빼기

n, k = map(int, input().split())
result = 0

while n >= k:
    target = (n // k) * k
    result += (n - target)
    n = target
    n //= k
    result += 1

result += (n - 1)
print(result)

거스름돈 문제

목표는 최소 개수의 동전으로 거스름돈 만들기

조건은 동전 단위가 배수 관계일 경우 그리디로 해결 가능

n = 1260
count = 0
coins = [500, 100, 50, 10]

for coin in coins:
    count += n // coin
    n %= coin

print(count)

정당성 분석 & 한계

정당성

위 문제들이 그리디로 풀리는 이유는 두 가지 조건을 만족하기 때문이다. 현재 선택이 전체 최적해로 이어지고, 과거의 선택이 이후의 선택을 방해하지 않음

한계

항상 최적해를 보장하지는 않으며, 특정 조건(배수 관계 등)이 깨질 경우, 그리디가 실패할 수 있음

예시는 거스름돈 문제에서 동전이 [1, 3, 4]일 경우, 6원을 만들 때 그리디는 실패하고 DP가 필요함

요약

항목	그리디 알고리즘
개념	매 순간 최선의 선택을 반복하여 문제 해결
장점	빠르고 직관적
단점	항상 정답을 보장하지 않음
핵심 조건	탐욕 선택 속성, 최적 부분 구조
대표 문제	활동 선택, 거스름돈, 곱 or 더하기, 1 만들기