그리디 알고리즘은 언제 올바른 해를 보장하나요?

그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하고, 그 선택을 되돌리지 않는 방식입니다. 항상 빠르고 단순하지만, 올바른 해를 보장하려면 지역 최적 선택이 전체 최적해로 이어진다는 근거가 있어야 합니다.

핵심 개념

• Greedy-choice property는 현재의 최선 선택을 포함하는 최적해가 존재한다는 성질입니다.
• Optimal substructure는 선택 후 남은 문제도 같은 방식으로 최적으로 풀 수 있다는 성질입니다.
• 증명은 보통 교환 논증(exchange argument), 귀납, cut property 등으로 합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

활동 선택 문제
- 끝나는 시간이 빠른 활동을 먼저 선택하면 최대 개수의 겹치지 않는 활동을 고를 수 있음
- 이유: 어떤 최적해의 첫 활동을 가장 빨리 끝나는 활동으로 바꿔도 이후 선택 가능성이 줄지 않음

function selectActivities(activities) {
  activities.sort((a, b) => a.end - b.end);
  const result = [];
  let lastEnd = -Infinity;
  for (const a of activities) {
    if (a.start >= lastEnd) {
      result.push(a);
      lastEnd = a.end;
    }
  }
  return result;
}

실무에서 주의할 점

• 지금 가장 큰 값/작은 값을 고르는 직감만으로는 충분하지 않습니다. 반례가 많습니다.
• 0/1 배낭 문제는 가치/무게 비율로 고르는 그리디가 항상 최적이 아닙니다.
• 정렬 기준 하나가 정답을 좌우하므로 기준 선택을 증명해야 합니다.

실무 적용 가이드

• 문제를 작은 선택으로 나누고, 한 번 선택하면 되돌리지 않아도 되는지 확인합니다.
• 반례를 직접 만들어 보고, 통과하면 교환 논증으로 설명해 봅니다.
• 최적 보장이 어려우면 DP나 탐색으로 전환합니다.

함께 연결해서 보면 좋은 키워드

Greedy, Exchange Argument, Optimality, Algorithm

정리

그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하고, 그 선택을 되돌리지 않는 방식입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.