[자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm)

---

1. 개요

그리디 알고리즘(Greedy Algorithm)이란 현재 단계에서 가장 최적의 선택을 반복하여 문제를 해결하는 알고리즘입니다. 탐욕법이라고도 불리는 이 방식은 매 순간 최선의 선택이 결국 전체 문제의 최적해로 이어진다고 가정합니다.

이 접근법이 성공적으로 작동하려면 문제에 대한 몇 가지 조건이 만족되어야 합니다. 그렇지 않으면 전역 최적해(Global Optimal Solution)를 보장하지 못할 수 있습니다.

---

2. 그리디 알고리즘의 조건

1. Greedy 선택 속성 (Greedy Choice Property)
   • 각 단계에서의 선택이 이후 단계에 영향을 주지 않고, 그 순간 최적의 선택을 하면 전체 최적해에 도달할 수 있는 속성을 의미합니다.
2. 최적 부분 구조 (Optimal Substructure)
   • 문제를 작은 부분 문제로 나누었을 때, 각 부분 문제의 최적해들이 모여 전체 문제의 최적해를 구성할 수 있는 구조입니다.

---

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

장점

• 단순성: 각 단계에서 바로 최적의 선택을 하기 때문에 설계와 구현이 비교적 단순합니다.
• 속도: 불필요한 탐색을 줄여 빠른 실행 시간을 보장합니다.

단점

• 최적해 보장 불가: 모든 문제에서 항상 최적해를 보장하지는 않습니다.
• 문제 분석 필요: 그리디 알고리즘이 적용 가능한 문제인지 미리 판단해야 합니다.

---

4. 동작 원리

1. 문제 정의: 전체 문제를 부분 문제들로 나눕니다.
2. 탐욕적 선택: 현재 상황에서 최선의 선택을 합니다.
3. 상태 갱신: 선택에 따라 문제의 상태를 업데이트합니다.
4. 반복: 문제를 완전히 해결할 때까지 위 과정을 반복합니다.

---

5. 예제 문제

---

예시 1: 동전 거스름돈 문제

문제 설명

500원, 100원, 50원, 10원의 동전이 있을 때, 특정 금액을 거슬러 주기 위해 필요한 동전의 개수를 최소화하세요.
(단, 동전 종류가 항상 큰 단위의 배수로 주어짐)

---

해결 방법

• 동전을 내림차순으로 정렬한 후, 남은 금액을 가장 큰 동전으로 최대한 많이 나누는 방식으로 풀이합니다.

#include <stdio.h>

int greedy_change(int coins[], int size, int amount) {
    int count = 0;

    for (int i = 0; i < size; i++) {
        if (amount == 0) break;  // 남은 금액이 없으면 종료
        count += amount / coins[i];
        amount %= coins[i];
    }

    return count;
}

int main() {
    int coins[] = {500, 100, 50, 10};
    int amount;

    printf("거슬러 줄 금액을 입력하세요: ");
    scanf("%d", &amount);

    int result = greedy_change(coins, 4, amount);
    printf("최소 동전 개수: %d\n", result);

    return 0;
}

---

입출력 예시

입력 출력

1260	최소 동전 개수: 6

과정 설명:

• 500원 동전 2개 → 남은 금액 260원
• 100원 동전 2개 → 남은 금액 60원
• 50원 동전 1개 → 남은 금액 10원
• 10원 동전 1개 → 남은 금액 0원

---

예시 2: 활동 선택 문제 (Activity Selection Problem)

문제 설명

여러 개의 활동이 주어졌을 때, 활동이 서로 겹치지 않으면서 최대한 많은 활동을 선택하세요.
각 활동은 시작 시간과 종료 시간으로 표현됩니다.

---

해결 방법

• 활동을 종료 시간 기준으로 정렬한 후, 가장 먼저 끝나는 활동부터 선택합니다.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
} Activity;

int compare(const void *a, const void *b) {
    return ((Activity *)a)->end - ((Activity *)b)->end;
}

int activity_selection(Activity activities[], int size) {
    qsort(activities, size, sizeof(Activity), compare);

    int count = 1;  // 첫 번째 활동 선택
    int last_end = activities[0].end;

    for (int i = 1; i < size; i++) {
        if (activities[i].start >= last_end) {
            count++;
            last_end = activities[i].end;
        }
    }

    return count;
}

int main() {
    Activity activities[] = {{1, 3}, {2, 5}, {4, 6}, {6, 7}, {5, 9}, {8, 9}};
    int size = sizeof(activities) / sizeof(activities[0]);

    int result = activity_selection(activities, size);
    printf("선택 가능한 최대 활동 개수: %d\n", result);

    return 0;
}

---

입출력 예시

활동 목록 선택 가능 활동 수

(1, 3), (2, 5), (4, 6), (6, 7), (5, 9), (8, 9)

4

과정 설명:

• 종료 시간이 빠른 순서로 정렬: (1, 3), (4, 6), (6, 7), (8, 9)
• 선택된 활동: (1, 3), (4, 6), (6, 7), (8, 9)

---

6. 한계와 고려 사항

• 문제 특성: 그리디 알고리즘이 적용 가능한 문제인지 확인해야 합니다.
• 최적해 불가 상황: 일부 문제에서는 그리디 방식이 최적해를 보장하지 못합니다. 예를 들어, 배낭 문제(Knapsack Problem)의 경우 동적 프로그래밍이 더 적합합니다.

---

7. 적용 가능한 문제 유형

• 최소 신장 트리(MST): 크루스칼, 프림 알고리즘
• 최단 경로: 다익스트라 알고리즘
• Huffman 코드 생성
• 거스름돈 문제 등

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.