contents

🪙 코딩 테스트를 위한 그리디(Greedy) 알고리즘 가이드

1. 그리디 알고리즘이란?

그리디 알고리즘(Greedy Algorithm) 은 최적화 문제를 해결할 때 각 단계에서 그 순간 가장 좋아 보이는 선택(국소 최적, Local Optimal) 을 하는 방법입니다. 이전 결정을 되돌리지 않고(백트래킹 없음) 매 단계 선택을 확정해 나갑니다.

• 특징
  • 그리디 선택 속성(Greedy Choice Property): 각 단계에서 최선의 선택이 전체 최적해로 이어짐
  • 최적 부분 구조(Optimal Substructure): 부분 문제들의 최적해를 조합해 전체 문제의 최적해를 구성 가능
• 한계
  • 모든 문제에서 항상 최적해를 보장하지 않음
  • 0/1 배낭 문제, 외판원 순회(TSP) 등에서는 DP나 완전탐색이 필요할 수 있음

2. 그리디 알고리즘 기본 절차

1. 정렬 또는 기준 계산 (예: 종료 시간, 가치/무게 비율 등)
2. 현재 상태에서 가장 좋은 선택을 함
3. 상태 갱신 (자원 차감, 선택 기록 등)
4. 종료 조건까지 반복
5. 결정을 되돌리지 않음

3. 대표 그리디 문제 & 예제

A. 활동 선택 문제 (Activity Selection)

목표: 시작·종료 시간이 주어진 활동 중 겹치지 않게 최대 개수 선택

알고리즘:

• 종료 시간 기준 오름차순 정렬
• 첫 활동 선택 후, 다음 활동들이 이전 활동 종료 시각 이후 시작하면 선택

Java 예시:

List<Activity> activitySelection(List<Activity> activities) {
    activities.sort(Comparator.comparingInt(a -> a.end));
    List<Activity> result = new ArrayList<>();
    int lastEnd = -1;
    for (Activity act : activities) {
        if (act.start >= lastEnd) {
            result.add(act);
            lastEnd = act.end;
        }
    }
    return result;
}

이유: 종료 시간이 빠를수록 이후 활동 선택 가능성이 높아짐

B. 동전 거스름(표준 화폐 단위)

목표: 거스름돈을 주어진 화폐 단위(1,5,10,25 등)로 최소 개수의 동전으로 지급

풀이:

• 남은 금액 이하의 가장 큰 단위 동전을 반복적으로 사용
• 금액이 0원 되면 종료

Java 예시:

int minCoins(int[] coins, int amount) {
    Arrays.sort(coins);
    int count = 0;
    for (int i = coins.length - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
        }
    }
    return count;
}

주의:

• 미국/한국처럼 표준적인 화폐 체계에서는 최적
• 비표준 코인 세트에서는 최적 보장 안 됨

C. 분할 가능 배낭 (Fractional Knapsack)

목표: 일부만 담을 수 있는(fractional) 물건을 허용하여 가치 최대화

알고리즘:

• 각 아이템의 가치/무게 비율 계산
• 비율 내림차순 정렬
• 비율이 높은 것부터 담고, 용량 부족 시 일부만 담음

Java 예시:

double fractionalKnapsack(Item[] items, int W) {
    Arrays.sort(items, (a, b) -> Double.compare(b.value/b.weight, a.value/b.weight));
    double total = 0;
    for (Item item : items) {
        if (W >= item.weight) {
            total += item.value;
            W -= item.weight;
        } else {
            total += item.value * ((double) W / item.weight);
            break;
        }
    }
    return total;
}

이유:
가치 효율이 높은 물건부터 담는 것이 전체 최적해로 이어짐

D. 허프만 코딩 (Huffman Coding)

목표: 데이터 압축을 위한 최적의 이진 트리 구성

방법:

• 빈도수 기준으로 최소 힙(Min-Heap) 구성
• 가장 작은 두 빈도 노드를 병합하여 새 노드 생성
• 노드 하나 남을 때까지 반복

E. 최소 신장 트리(MST) - Kruskal / Prim

• Kruskal: 사이클을 만들지 않는 가장 짧은 간선부터 선택
• Prim: 현재 트리와 연결되는 가장 짧은 간선을 계속 추가

이유:
국소적으로 가장 짧은 간선을 고르되, 항상 최적 신장 트리로 이어짐

4. 코딩 테스트에서 자주 나오는 그리디 유형

• 활동 선택(Interval Scheduling)
• 최소 동전 개수
• 분할 가능 배낭
• 작업 스케줄링(Job Sequencing with Deadlines)
• 로프 연결 최소 비용
• 점프 게임(Jump Game)
• 주어진 숫자 배열로 가장 큰 수 만들기
• 주유소 문제(Gas Station)
• 문단 정렬(Text Justification)

5. 그리디 정당성 검증법

• 그리디 선택 속성: 매 단계의 최선 선택이 전체 최선인가?
• 최적 부분 구조: 부분 최적해를 조합해 전체 최적해 생성 가능?
• 간단한 예로 그리디 결과와 완전 탐색의 결과를 비교해보기

6. 장점과 한계

7. 실전 팁

• 목표가 최대/최소이고, 현재 최선 선택이 전체에도 좋을 것 같으면 일단 그리디 고려
• 정렬은 대부분의 그리디 시작점
• 반드시 그리디의 정당성을 설명할 수 있어야 함 (증명 or 반례 제시)
• 활동 선택, 배낭, 동전, MST, 허프만 등의 대표 패턴 숙지

📌 요약 표

예시

🟢 1. 활동 선택 문제 (Activity Selection)

문제: 각 활동의 시작·종료 시간이 주어질 때, 겹치지 않게 최대한 많은 활동을 선택하세요.

풀이 방법:

• 종료 시간 기준 오름차순 정렬
• 이전에 선택한 활동의 종료 이후에 시작하는 활동만 추가

List<Activity> activitySelection(List<Activity> acts) {
    acts.sort(Comparator.comparingInt(a -> a.end));
    List<Activity> result = new ArrayList<>();
    int lastEnd = -1;
    for (Activity act : acts) {
        if (act.start >= lastEnd) {
            result.add(act);
            lastEnd = act.end;
        }
    }
    return result;
}

설명: 항상 가장 빨리 끝나는 활동을 선택해야 이후에 최대한 많은 활동을 추가할 수 있습니다.

🟢 2. 동전 거스름 (Coin Change, 표준 화폐 단위)

문제:
거스름돈을 최소 동전 개수로 지급하세요. (예: 화폐단위 = {1, 5, 10, 25})

풀이 방법:

• 매번 남은 금액 내 가장 큰 동전을 최대한 사용

int minCoins(int[] coins, int amount) {
    Arrays.sort(coins);
    int count = 0;
    for (int i = coins.length - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count++;
        }
    }
    return count;
}

주의:

• 표준 동전만 성립 (비표준: 4,3,1 등은 정답을 보장X)

🟢 3. 분할 가능한 배낭 문제 (Fractional Knapsack)

문제:
물건별 가치와 무게가 주어질 때, 배낭 용량 W 안에서 "일부만 담을 수 있는" 조건일 때 최대 가치를 구하세요.

풀이 방법:

• 각 물건의 가치/무게 비율을 구하여 내림차순 정렬, 비율이 높은 것부터 최대한 담기

double fractionalKnapsack(Item[] items, int W) {
    Arrays.sort(items, (a, b) -> Double.compare(b.value/b.weight, a.value/b.weight));
    double total = 0;
    for (Item item : items) {
        if (W >= item.weight) {
            total += item.value;
            W -= item.weight;
        } else {
            total += item.value * ((double) W / item.weight);
            break;
        }
    }
    return total;
}

설명:
가치 효율이 높은 물건부터 최대한 담아야 전체 가치가 최대가 됩니다.

🟢 4. 작업 스케줄링 / 최대 이익 문제 (Job Sequencing with Deadlines)

문제: 작업마다 완료 마감(deadline)과 이익(profit)이 있을 때, 마감 전 작업을 최대 이익 순으로 배치하세요.

풀이:

• 이익 기준 내림차순 정렬 → 가능한 가장 빠른 마감 슬롯에 작업 배치

🟢 5. 허프만 코딩 (Huffman Coding)

문제: 문자 빈도수가 주어질 때 최적의 이진 코드(압축)를 만드세요.

풀이:

• 가장 작은 두 빈도수 노드를 반복적으로 병합(최소 힙)
• 트리 완성 후 코드 길이 최소화

🟢 6. 최소 신장 트리(MST, Kruskal/Prim)

문제: 그래프의 모든 노드를 연결하는 가중치 최소 합의 트리(사이클 없음)를 만드세요.

• Kruskal: 가장 작은 간선(사이클 X)부터 선택
• Prim: 현재 트리랑 연결된 가장 작은 간선 확장

✅ 정리 & 출제 팁

• 코딩 테스트 빈출 순으로 연습: 동전, 활동 선택, 배낭, MST, Huffman
• 반례/최적상황 반드시 체크(표준 화폐/배낭 완전분할 등)
• 정렬 & 반복문 → 선택 & 자원 차감 → 종료 조건 체크가 가장 기본 패턴

references