7-1. 그리디 알고리즘 소개

1. 그리디 알고리즘의 소개

그리디 알고리즘(Greedy Algorithm)은 탐욕적(greedy)인 선택을 통해 최적해를 찾아가는 알고리즘 설계 기법입니다. "탐욕적"이라는 말에서 짐작할 수 있듯이, 각 단계에서 가장 좋아 보이는(locally optimal) 선택을 합니다. 이러한 선택들이 모여 최종적으로 전역 최적해(globally optimal)를 보장하는 것을 목표로 합니다. 하지만, 모든 문제에 그리디 알고리즘을 적용할 수 있는 것은 아니며, 특정 조건들을 만족해야 합니다. 마치 배고픈 사람이 눈앞에 있는 가장 먹음직스러운 음식을 선택하듯, 그리디 알고리즘은 현재 상황에서 가장 이득이 되는 선택을 반복하여 문제를 해결하려는 방식입니다.

2. 핵심 특징과 동작 방식

1) 탐욕적 선택 속성 (Greedy Choice Property)

그리디 알고리즘의 핵심은 "탐욕적 선택 속성"입니다. 이는 각 단계에서 이전의 선택에 구애받지 않고 현재 상황에서 가장 좋아 보이는 선택을 한다는 의미입니다. 이러한 선택은 이후의 선택들에 영향을 주지 않으며, 최종적으로 최적해를 구성하는 데 기여해야 합니다. 다시 말해, 어떤 선택을 하더라도 최종적인 최적해에 영향을 미치지 않아야 합니다.

2) 최적 부분 구조 (Optimal Substructure)

최적 부분 구조는 그리디 알고리즘이 적용될 수 있는 중요한 조건 중 하나입니다. 이는 문제의 최적해가 부분 문제들의 최적해로 구성됨을 의미합니다. 즉, 전체 문제의 최적해를 구하기 위해, 부분 문제들을 최적으로 해결하고 이들을 결합하여 전체 해를 구성할 수 있어야 합니다.

예를 들어, 최단 경로 문제에서 특정 노드까지의 최단 경로는 그 노드 이전 노드까지의 최단 경로를 포함해야 합니다. 만약 그렇지 않다면, 전체 경로가 최적이 될 수 없습니다.

3) 동작 과정

그리디 알고리즘의 일반적인 동작 과정은 다음과 같습니다.

1. 선택(Selection): 현재 상태에서 가장 좋아 보이는 선택을 합니다.
2. 가능성 검사(Feasibility Check): 선택이 문제의 제약 조건을 위반하지 않는지 확인합니다.
3. 해결책 구성(Solution Construction): 선택을 해답 집합에 추가합니다.
4. 종료 조건(Termination Condition): 문제가 완전히 해결되었는지 확인합니다. 만약 그렇지 않다면, 1단계로 돌아갑니다.

이러한 과정을 통해 그리디 알고리즘은 문제를 단계별로 해결해 나갑니다.

3. 적용 조건과 제약 사항

1) 그리디 알고리즘 적용 가능 여부 판단

그리디 알고리즘이 모든 문제에 적용 가능한 것은 아닙니다. 일반적으로 그리디 알고리즘을 적용하기 위해서는 다음 두 가지 조건을 만족해야 합니다.

• 탐욕적 선택 속성(Greedy Choice Property) 만족: 각 단계에서 최적의 선택을 하는 것이 전체 문제의 최적해를 보장해야 합니다.
• 최적 부분 구조(Optimal Substructure) 만족: 전체 문제의 최적해가 부분 문제들의 최적해로 구성되어야 합니다.

만약 이 조건들을 만족하지 않는다면, 그리디 알고리즘은 최적해를 보장하지 못할 수 있습니다.

2) 주의사항

• 지역 최적해 vs. 전역 최적해: 그리디 알고리즘은 각 단계에서 지역적으로 최적인 선택을 하지만, 이것이 항상 전역적으로 최적인 해를 보장하지는 않습니다.
• 예외 처리: 그리디 알고리즘이 최적해를 보장하지 않는 경우, 다른 알고리즘(예: 동적 프로그래밍, 백트래킹)을 고려해야 합니다.
• 문제의 특성 파악: 그리디 알고리즘을 적용하기 전에, 문제의 특성을 정확히 파악하고 그리디 알고리즘이 적합한지 판단해야 합니다.

4. 그리디 알고리즘의 예시

1) 거스름돈 문제

거스름돈 문제는 그리디 알고리즘의 대표적인 예시입니다. 주어진 금액을 최소한의 동전 개수로 거슬러주는 문제입니다.

예를 들어, 480원을 거슬러줘야 할 때, 그리디 알고리즘은 다음과 같이 동작합니다.

1. 500원짜리 동전: 사용할 수 없음 (480원 < 500원)
2. 100원짜리 동전: 4개 사용 (480원 - 4*100원 = 80원)
3. 50원짜리 동전: 1개 사용 (80원 - 1*50원 = 30원)
4. 10원짜리 동전: 3개 사용 (30원 - 3*10원 = 0원)

총 8개의 동전(100원 4개, 50원 1개, 10원 3개)으로 거스름돈을 거슬러줍니다. 이 문제는 탐욕적 선택 속성과 최적 부분 구조를 만족하기 때문에 그리디 알고리즘으로 최적해를 구할 수 있습니다.

2) 활동 선택 문제

활동 선택 문제는 여러 개의 활동(activity) 중에서 최대한 많은 활동을 선택하는 문제입니다. 각 활동은 시작 시간과 종료 시간을 가지며, 겹치는 활동은 선택할 수 없습니다.

예를 들어, 다음과 같은 활동들이 주어졌다고 가정해 봅시다.

이 문제를 그리디 알고리즘으로 해결하기 위해, 각 활동을 종료 시간 순으로 정렬합니다. 그런 다음, 종료 시간이 가장 빠른 활동부터 선택하고, 선택된 활동과 겹치지 않는 활동을 선택합니다.

1. 활동 1 (1-4) 선택
2. 활동 4 (5-7) 선택
3. 활동 8 (8-11) 선택

총 3개의 활동을 선택할 수 있으며, 이 역시 그리디 알고리즘으로 최적해를 구할 수 있습니다.

5. 그리디 알고리즘의 장단점

1) 장점

• 간결함과 효율성: 알고리즘 설계가 비교적 간단하며, 구현이 용이합니다. 또한, 각 단계에서 최적의 선택을 하기 때문에 시간 복잡도가 낮습니다.
• 빠른 실행 속도: 대부분의 경우, 그리디 알고리즘은 다른 알고리즘보다 빠르게 해답을 찾을 수 있습니다.
• 최적해 보장: 특정 문제(거스름돈 문제, 활동 선택 문제 등)에 대해서는 최적해를 보장합니다.

2) 단점

• 최적해 보장 어려움: 모든 문제에 적용할 수 있는 것은 아니며, 최적해를 보장하지 못하는 경우가 많습니다.
• 지역 최적해 문제: 지역 최적해에 갇힐 수 있으며, 전역 최적해를 찾지 못할 수 있습니다.
• 문제 분석의 어려움: 그리디 알고리즘을 적용하기 전에, 문제의 특성을 정확히 분석하고 그리디 알고리즘이 적합한지 판단해야 합니다.

6. 결론

그리디 알고리즘은 각 단계에서 가장 좋아 보이는 선택을 하는 단순하면서도 강력한 알고리즘 설계 기법입니다. 탐욕적 선택 속성과 최적 부분 구조를 만족하는 문제에 대해서는 효율적인 해답을 제공합니다. 하지만, 모든 문제에 적용할 수 있는 것은 아니며, 최적해를 보장하지 못하는 경우도 있습니다. 그리디 알고리즘을 효과적으로 사용하기 위해서는 문제의 특성을 정확하게 이해하고, 적용 가능성을 신중하게 판단해야 합니다.