그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘

 

 

그리디 알고리즘은 최적의 해를 구하기 위해 각 단계에서 가장 좋다고 생각되는 선택을 하는 알고리즘입니다. 이 방법은 문제를 해결하는 과정에서 부분적으로 최적의 선택을 반복하여 전체적으로 최적의 해답에 도달하려고 합니다.

---

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

그리디 알고리즘은 다음 두 가지 속성을 만족하는 경우에만 올바른 결과를 도출할 수 있습니다:

1.1 그리디 선택 속성 (Greedy Choice Property)

• 정의: 각 단계에서의 선택이 전체 문제에 대한 최적의 해를 보장해야 합니다.
• 설명: 현재 단계에서 최선이라고 판단되는 선택을 했을 때, 이 선택이 이후의 결정에 영향을 미치지 않고 최적의 결과를 이끌어낼 수 있어야 합니다.
• 예시: 거스름돈 문제에서 가장 큰 단위의 동전을 먼저 선택하는 방식은 최적의 해를 보장합니다.

1.2 최적 부분 구조 (Optimal Substructure)

• 정의: 문제의 최적 해결 방법이 그 하위 문제들의 최적 해결 방법으로 구성되어야 합니다.
• 설명: 문제를 부분 문제로 나눴을 때, 부분 문제의 해를 결합하여 전체 문제의 최적의 해를 구할 수 있어야 합니다.
• 예시: 최단 경로 문제에서 특정 지점까지의 최단 경로는 그 지점 이전의 최단 경로로 구성됩니다.

---

 

2. 그리디 알고리즘의 동작 원리

1. 문제를 분해: 문제를 여러 단계로 나눕니다.
2. 최적 선택: 각 단계에서 가장 최적인 선택을 합니다.
3. 반복: 선택을 반복하여 전체 문제를 해결합니다.
4. 해결 완료: 모든 선택이 끝난 후 결과를 반환합니다.

---

반응형

3. 그리디 알고리즘의 구현 방법

C 언어 예시 코드: 거스름돈 문제

#include <stdio.h>

void greedyChange(int coins[], int n, int amount) {
    int count = 0;
    printf("거스름돈 구성: \n");

    for (int i = 0; i < n; i++) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
            printf("%d원 \n", coins[i]);
        }
    }
    printf("총 동전 개수: %d\n", count);
}

int main() {
    int coins[] = {500, 100, 50, 10};
    int amount = 1260;
    int n = sizeof(coins) / sizeof(coins[0]);

    greedyChange(coins, n, amount);
    return 0;
}

Java 예시 코드: 활동 선택 문제

import java.util.*;

public class GreedyActivitySelection {
    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};

        List<Integer> selected = selectActivities(start, finish);

        System.out.println("선택된 활동: " + selected);
    }

    public static List<Integer> selectActivities(int[] start, int[] finish) {
        List<Integer> result = new ArrayList<>();
        int n = start.length;

        int lastFinish = 0;
        for (int i = 0; i < n; i++) {
            if (start[i] >= lastFinish) {
                result.add(i);
                lastFinish = finish[i];
            }
        }

        return result;
    }
}

 

Python 예시 코드: 배낭 문제 (Fractional Knapsack)

def fractional_knapsack(items, capacity):
    items = sorted(items, key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0

    for weight, value in items:
        if capacity >= weight:
            capacity -= weight
            total_value += value
        else:
            total_value += value * (capacity / weight)
            break

    return total_value

# 예시
items = [(10, 60), (20, 100), (30, 120)]  # (무게, 가치)
capacity = 50
print("최대 가치:", fractional_knapsack(items, capacity))

---

 

4. 그리디 알고리즘을 사용하는 대표적인 문제들

1. 거스름돈 문제: 주어진 금액을 최소한의 동전으로 거슬러 주는 문제
2. 최소 신장 트리 (Kruskal's Algorithm, Prim's Algorithm)
3. 활동 선택 문제: 가능한 가장 많은 활동을 선택하는 문제
4. 배낭 문제 (Fractional Knapsack): 제한된 무게에서 최대 가치를 찾는 문제
5. 허프만 코딩 (Huffman Coding): 데이터 압축을 위한 최적의 코딩 방식

---

 

5. 그리디 알고리즘이 적용되지 않는 경우 (반례)

그리디 알고리즘이 항상 최적의 해를 보장하지는 않습니다. 다음은 반례를 통해 그리디 알고리즘의 한계를 설명합니다:

반례 1: 배낭 문제 (0/1 Knapsack)

• 문제: 아이템의 무게와 가치가 주어졌을 때, 제한된 무게 내에서 최대 가치를 찾는 문제
• 반례: 아이템 [(무게: 10, 가치: 60), (무게: 20, 가치: 100), (무게: 30, 가치: 120)]
  • 제한된 무게가 50일 때, 그리디 알고리즘은 가치/무게 비율이 가장 높은 아이템을 먼저 선택합니다.
  • 결과: 아이템 (무게: 30, 가치: 120)과 (무게: 20, 가치: 100)을 선택해 220의 가치를 얻습니다.
  • 최적 해: 아이템 (무게: 20, 가치: 100)과 (무게: 10, 가치: 60)을 선택해 240의 가치를 얻습니다.

반례 2: 그래프의 최단 경로 문제

• 문제: 가중치가 음수인 그래프에서 최단 경로를 찾는 문제
• 반례: 다익스트라 알고리즘은 그리디 접근을 사용하므로, 음수 가중치가 포함된 경우 올바른 결과를 보장하지 못합니다. 벨만-포드 알고리즘이 필요합니다.

---

 

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

장점

1. 빠른 계산 속도: 대부분의 경우 시간 복잡도가 낮아 효율적입니다.
2. 단순한 구현: 논리 구조가 간단하고 직관적입니다.

단점

1. 최적 해 보장 불가: 문제에 따라 최적 해를 보장하지 않을 수 있습니다.
2. 문제 분석 필요: 그리디 선택 속성과 최적 부분 구조를 만족하는지 확인해야 합니다.

---

그리디 알고리즘은 문제를 빠르고 간단하게 해결할 수 있는 강력한 도구입니다. 하지만 적용 가능한 문제와 그렇지 않은 문제를 명확히 구분하여 적절히 활용하는 것이 중요합니다.