[SCCC] 그리디

그리디

• 현재 상태에서 가장 좋은 선택을 하는 방법
  • 현재 상태에서 가장 좋은 선택이 전체 범위에서도 가장 좋은 선택이라는 것은 보장 못함
  • 만약 이 전략이 전체 범위에서도 최적이라면, 그리디 기법으로 문제를 해결할 수 있음

• 동적 계획법 vs 그리디 기법
  • 동적 계획법: D[i]를 계산할 때 1 ≤ j < i인 모든 D[j]를 확인
  • 그리디 기법: D[i]를 계산할 때 적당한 D[j] 하나만 확인

문제 유형

1. 동전 문제
   n개의 원소가 주어지고, 특정 조건을 만족하도록 원소 몇 개를 선택해서 원소의 가중치 합을 최대/최소화하는 문제

   예: BOJ - 동전0

2. 배낭 채우기 문제
   Fractional Knapsack Problem
   무게 대비 가격이 높은 물건부터 가져가는 전략

   예: BOJ - 평범한 문제