[알고리즘] 그리디(Greedy)란? (백준 11047, 13305)

📌 핵심 요약

• 그리디 알고리즘 — 매 순간 지금 당장 가장 좋아 보이는 선택을 반복해 최적해를 구하는 방법
• 성립 조건 — 탐욕적 선택 속성 + 최적 부분 구조가 모두 만족해야 적용 가능
• 주의점 — 그리디가 항상 정답은 아님. "왜 이 선택이 최적인가"를 반드시 증명해야 함

 

목차

1 그리디 알고리즘이란?

핵심 성립 조건

그리디 vs DP

2 BOJ 11047 — 동전 0

풀이 아이디어

Java 코드

3 BOJ 13305 — 주유소

풀이 아이디어

Java 코드

1 그리디 알고리즘이란?

그리디(Greedy) 알고리즘은 "지금 이 순간 가장 좋아 보이는 선택"을 반복하여 최적해를 구하는 방식이다. 미래를 고려하지 않고 현재 상태에서 가장 이득이 되는 선택만을 계속하다 보면 전체 최적해에 도달할 수 있는 문제에 적용한다.

ℹ️

한 줄 정의

각 단계에서 최선인 선택을 반복했을 때 전역적으로도 최선인 결과가 나오는 알고리즘

핵심 성립 조건

그리디를 적용하려면 반드시 아래 두 조건이 모두 성립해야 한다.

조건	설명	확인법
탐욕적 선택 속성	지금 최선의 선택이 나중에도 최선임이 보장됨	교환 논증
최적 부분 구조	전체 최적해가 부분 최적해들로 구성됨	귀납적 증명

💡

교환 논증(Exchange Argument)이란?

최적해에서 그리디가 선택한 것과 다른 선택이 있다면, 그것을 그리디의 선택으로 교환해도 결과가 나빠지지 않음을 보이는 증명 방법이다. "바꿔도 손해가 없다 → 그리디 선택이 항상 안전하다"는 논리 구조다.

그리디 vs DP

구분	그리디	DP (동적 프로그래밍)
선택 방식	현재 최선만 선택	모든 경우를 고려
속도	빠름	상대적으로 느림
적용 범위	조건 만족 시만	더 넓음
구현 난이도	단순	복잡
대표 예시	동전 거스름돈, 회의실 배정	배낭 문제, 최장 공통 부분 수열

⚠️

그리디가 통하지 않는 경우

동전이 1, 3, 4원이고 목표가 6원일 때 — 그리디는 4+1+1=3개를 선택하지만 최적은 3+3=2개다. 동전 단위가 배수 관계가 아닐 때는 그리디가 틀릴 수 있으며, 이때는 DP를 써야 한다.

2 BOJ 11047 — 동전 0

BOJ #11047

동전 0

N ≤ 10 · K ≤ 100,000,000 · 시간제한 1초

난이도: Silver IV

N종류의 동전으로 합이 K가 되도록 만들 때 필요한 동전 개수의 최솟값을 구하라. 각 동전의 가치는 오름차순이며, i ≥ 2인 경우 Ai는 Ai-1의 배수다.

풀이 아이디어

핵심 조건은 "각 동전은 바로 아래 동전의 배수"라는 점이다. 이 조건 덕분에 큰 동전을 쪼개면 정확히 작은 동전들로 대체되므로, 가장 큰 동전부터 최대한 많이 사용하는 전략이 항상 최적이다.

💡

그리디 정당성

큰 동전 1개 = 작은 동전 여러 개이므로, 큰 동전을 먼저 쓸수록 총 개수가 줄어든다. 배수 조건이 없는 동전 문제라면 그리디가 틀릴 수 있으니 주의!

예제 추적 — K = 4200 / 동전: 1 5 10 50 100 500 1000 5000 10000 50000

단계	동전	사용 개수	남은 K
1	1000원	4개	200
2	100원	2개	0
합계		6개 ✅	-

풀이 과정

1. 동전 배열을 입력받는다 (이미 오름차순으로 주어짐)
2. 가장 큰 동전(인덱스 n-1)부터 역순으로 순회한다
3. 현재 동전으로 K를 나눈 몫만큼 count에 더하고, K를 그만큼 차감한다
4. K가 0이 되면 종료, count를 출력한다

Java 코드

 

Java — BOJ 11047 동전 0

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N과 K를 첫 줄에서 같이 읽음
        String[] firstLine = br.readLine().trim().split(" ");
        int n = Integer.parseInt(firstLine[0]);
        int k = Integer.parseInt(firstLine[1]);

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine().trim());
        }

        int count = 0;
        // 큰 동전부터 탐욕적으로 사용
        for (int i = arr.length - 1; i >= 0; i--) {
            int mod = k / arr[i];   // 이 동전을 몇 개 쓸 수 있나
            count += mod;
            k -= arr[i] * mod;       // 남은 금액 갱신
            if (k == 0) break;
        }

        System.out.print(count);
    }
}

3 BOJ 13305 — 주유소

BOJ #13305

주유소

N ≤ 100,000 · 거리·가격 ≤ 1,000,000,000 · 시간제한 2초

난이도: Silver III

일직선으로 N개의 도시가 있고 각 도시에 주유소가 있다. 제일 왼쪽 도시에서 오른쪽 끝 도시까지 이동할 때 드는 최소 주유 비용을 구하라. 기름통 크기는 무제한이며 1km당 1리터를 소모한다.

풀이 아이디어

각 구간을 지나갈 때 "지금까지 만난 주유소 중 가장 싼 가격"으로 기름을 채우는 것이 항상 최적이다. 더 싼 주유소를 만나는 순간 그 가격이 새로운 기준이 되고, 이후 구간은 모두 이 가격으로 계산한다.

💡

핵심 그리디 관찰

각 구간마다 지금까지 본 최솟값(minPrice) × 거리를 더해나가면 된다. minPrice보다 싼 주유소가 나오면 그 순간부터 minPrice를 갱신한다.

예제 추적 — 가격: 5 2 4 1 / 거리: 2 3 1

구간	현재 가격	minPrice	구간 비용	누적
0 → 1 (2km)	5	5	5×2 = 10	10
1 → 2 (3km)	2	2	2×3 = 6	16
2 → 3 (1km)	4	2	2×1 = 2	18 ✅

⚠️

자료형 주의 — int가 아닌 long!

거리 최대 10억 × 가격 최대 10억 = 최대 10¹⁸ → int 범위(약 21억)를 훨씬 초과한다. dist, price, result 모두 반드시 long으로 선언해야 한다.

풀이 과정

1. 거리 배열(N-1개)과 가격 배열(N개)을 각각 한 줄씩 입력받는다
2. minPrice를 첫 번째 도시 가격으로 초기화한다
3. i = 0부터 N-2까지 순회하며 minPrice를 갱신하고, minPrice × dist[i]를 result에 누적한다
4. result를 출력한다 (자료형은 반드시 long)

Java 코드

 

Java — BOJ 13305 주유소

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());

        // 거리 입력 (N-1개, 한 줄)
        StringTokenizer st = new StringTokenizer(br.readLine());
        long[] dis = new long[n - 1];
        for (int i = 0; i < n - 1; i++) {
            dis[i] = Long.parseLong(st.nextToken());
        }

        // 가격 입력 (N개, 한 줄)
        st = new StringTokenizer(br.readLine());
        long[] oil = new long[n];
        for (int i = 0; i < n; i++) {
            oil[i] = Long.parseLong(st.nextToken());
        }

        // 그리디: 지금까지 본 최솟값으로 각 구간 채우기
        long result   = 0;
        long minPrice = oil[0];

        for (int i = 0; i < n - 1; i++) {
            minPrice = Math.min(minPrice, oil[i]);  // 최솟값 갱신
            result  += minPrice * dis[i];             // 이 구간 비용 누적
        }

        System.out.print(result);
    }
}

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.