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

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

✅ 학습 목표

이번 단원에서는 더 복잡한 그리디 문제를 해결하면서 사고력을 확장하고, 그리디 알고리즘이 항상 최적해를 보장하는 것은 아니라는 점을 이해합니다.

1. 복잡한 그리디 문제를 해결하면서 문제 해결 능력 향상
2. 그리디 알고리즘이 적용되지 않는 경우를 판단하는 능력 기르기
3. 효율적인 문제 해결 전략을 연습하고 다양한 응용 문제 학습

---

✅ 심화 문제 예제

1️⃣ 숫자 카드 게임

여러 개의 숫자 카드가 있으며, 한 줄씩 선택하여 가장 높은 숫자를 찾아야 합니다.
단, 각 행에서 가장 작은 숫자 중에서 가장 큰 값을 선택해야 합니다.

문제 해결 방법 (그리디 알고리즘)

1. 각 행(row)에서 가장 작은 숫자를 선택.
2. 그 중에서 가장 큰 숫자를 선택.

📌 핵심 원리

• 매 순간 각 행의 최솟값을 선택하여 비교하기 때문에 그리디 알고리즘을 활용하여 해결 가능.

예제

입력:
3 3 3
2 2 2
4 1 4

출력:
2

각 행의 최소값: 3, 2, 1 → 그 중에서 가장 큰 값 2 선택.

---

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
각 사람이 돈을 인출하는 데 걸리는 시간 입력: 3 1 4 3 2
최소 대기 시간 합: 32

---

✅ 핵심 원리

1. 숫자 카드 게임
   • 각 행의 최소값을 선택하고, 그중에서 최대값을 찾음.
   • 그리디 알고리즘 적용 가능.
2. ATM 인출 시간 최소화
   • 가장 짧은 인출 시간부터 정렬하여 대기 시간 최소화.
   • 그리디 알고리즘 적용 가능.

---

✅ 정리

1. 그리디 알고리즘이 적용될 수 있는지 항상 판단해야 한다.
2. 숫자 카드 문제는 각 행의 최소값 중 최댓값 선택.
3. ATM 문제는 오름차순 정렬 후 누적 합 계산으로 최적해를 찾음.