그리디 알고리즘 (Greedy Algorithm) 요약

그리디 알고리즘 (Greedy Algorithm)

---

📌 1. 그리디 알고리즘 개요

✅ 학습 목표

• 알고리즘이란 무엇인가?
• 그리디 알고리즘의 개념과 특징 이해
• 그리디 알고리즘이 사용될 수 있는 조건 이해

✅ 학습 내용

• 알고리즘이란? (컴퓨터가 문제를 해결하는 절차)
• 그리디 알고리즘이란?
  • 매 단계에서 가장 최적(최선)의 선택을 하는 알고리즘
  • 전체적으로도 최적의 해를 찾을 수 있는 경우 사용
• 그리디 알고리즘이 적용 가능한 경우
  • 탐욕적 선택 속성 (Greedy Choice Property): 부분 최적해가 전체 최적해를 보장할 때
  • 최적 부분 구조 (Optimal Substructure): 부분 문제의 최적해를 조합하여 전체 문제의 최적해를 만들 수 있을 때

---

📌 2. 기본적인 그리디 알고리즘 구현

✅ 학습 목표

• 그리디 알고리즘을 C언어로 구현하는 방법 익히기
• 간단한 문제를 해결해 보면서 그리디 개념 이해

✅ 학습 내용

• 동전 거스름돈 문제
  • 최소한의 동전 개수로 거스름돈을 주는 문제

✅ 예제 문제

💡 거스름돈이 1260원이 있을 때, 500원, 100원, 50원, 10원 동전으로 최소한의 동전 개수를 구하는 프로그램을 작성하세요.

✅ C언어 코드 예제

#include <stdio.h>

int main() {
    int money = 1260;
    int coin_types[4] = {500, 100, 50, 10};
    int count = 0;

    for (int i = 0; i < 4; i++) {
        count += money / coin_types[i];
        money %= coin_types[i];
    }

    printf("최소 동전 개수: %d\n", count);
    return 0;
}

📌 핵심 원리: 가장 큰 단위의 동전부터 차례로 나누어 최대한 활용하는 방식

---

📌 3. 다양한 그리디 문제 연습

✅ 학습 목표

• 다양한 유형의 그리디 문제를 풀어보며 적용 능력 향상
• 문제 해결 과정에서 논리를 정리하는 연습

✅ 연습 문제

1. 회의실 배정 문제
   • 여러 개의 회의가 있고, 한 회의실에서 진행 가능
   • 회의 시간이 겹치지 않도록 최대한 많은 회의를 배정하기
   • 종료 시간이 가장 빠른 회의부터 선택하는 방식이 유리
2. 배낭 문제 (Fractional Knapsack)
   • 각 아이템은 무게와 가치가 있음
   • 배낭에 담을 수 있는 최대 무게 제한이 있음
   • 단, 아이템을 쪼갤 수 있음! (비율로 담을 수 있음)
   • 가치 대비 무게 비율이 높은 것부터 선택
3. 큰 수 만들기
   • 숫자 리스트에서 K개의 숫자를 제거하여 가장 큰 수 만들기

---

📌 4. 그리디 알고리즘 심화 문제

✅ 학습 목표

• 복잡한 그리디 문제를 해결하면서 사고력을 확장하기
• 그리디 알고리즘이 적용되지 않는 경우를 판단하는 능력 기르기

✅ 심화 문제 예제

1. 숫자 카드 게임
   • 여러 개의 숫자 카드 중, 각 행에서 가장 작은 숫자를 선택하고
     그 중에서 가장 큰 숫자를 찾는 문제
   • 그리디 알고리즘을 활용하여 해결
2. ATM 인출 시간 최소화 문제
   • 사람들이 은행에서 돈을 인출하는데 시간이 다름
   • 각 사람이 돈을 인출하는 데 걸리는 시간이 짧은 순으로 정렬하여
     대기 시간을 최소화하는 방식

✅ C언어 코드 예제 (ATM 인출 시간 최소화)

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

// 정렬 함수
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;
    printf("사람 수 입력: ");
    scanf("%d", &n);
    
    int times[n];
    
    printf("각 사람이 돈을 인출하는 데 걸리는 시간 입력: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &times[i]);
    }

    // 인출 시간이 짧은 사람부터 정렬
    qsort(times, n, sizeof(int), compare);
    
    int total = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        sum += times[i];  // 현재 사람이 기다려야 하는 총 시간
        total += sum;  // 누적 시간 합산
    }

    printf("최소 대기 시간 합: %d\n", total);
    return 0;
}

📌 핵심 원리:

• 인출 시간이 적은 사람부터 정렬하면 전체 대기 시간이 최소가 됨

---

📌 5. 그리디 알고리즘 vs 다른 알고리즘

✅ 학습 목표

• 그리디 알고리즘이 항상 최적해를 보장하는 것은 아니라는 점 이해
• 다이나믹 프로그래밍 (DP)과의 차이점 알기

✅ 학습 내용

• 그리디 vs 다이나믹 프로그래밍 (DP)
  • 그리디: 현재 최선의 선택 → 항상 최적해 보장 안됨
  • DP: 모든 경우를 고려하며 최적의 해를 구함 (비교적 더 정확함)
• 그리디가 적용되지 않는 경우 예제:
  • 최대 증가 부분 수열 (LIS) → DP로 풀어야 함
  • 최소 동전 개수 문제에서 특정한 경우 그리디가 오답이 될 수 있음

---

📌 6. 실전 문제 풀이 및 최종 프로젝트

✅ 학습 목표

• 온라인 저지(백준, 프로그래머스)에서 문제 풀어보기
• 실전 프로젝트: 그리디 알고리즘을 활용한 응용 문제 해결

✅ 실전 연습 사이트

• 백준 온라인 저지 (https://www.acmicpc.net/)
• 프로그래머스 (https://programmers.co.kr/)

✅ 프로젝트 아이디어

• 배달 최적화 문제 (예: 가장 빠른 경로 찾기)
• 최소 비용 네트워크 연결 문제 (예: 크루스칼 알고리즘과 비교)

---

🎯 마무리 및 정리

• 그리디 알고리즘의 핵심: 매 순간 최선의 선택을 하지만 항상 최적해를 보장하지는 않음
• C언어로 구현 연습: 기본 문제부터 심화 문제까지 직접 구현
• 그리디 적용 여부 판단: 문제를 보고 그리디로 해결할 수 있는지 판단하는 능력 기르기