그리디 알고리즘

Greedy Algorithm

Greedy?

사전적 의미로는 탐욕스러운, 욕심 많은이라는 의미를 담고 있음

Greedy Algorithm

• 그리디 알고리즘은 Greedy의 사전적 의미인 "탐욕스러운"이라는 의미를 따와 탐욕법이라고도 불림
• 현재 상황에서 지금 당장 좋은 것만 고르는 선택을 반복적으로 활용하여 문제를 해결하는 방법

Greedy Algorithm의 필수 요소

• 탐욕적 선택 속성(Greedy Choice Property)
• 👉단순히 가장 좋아 보이는 방법을 선택했을 때 최적의 해를 보장할 수 있는지 검토함으로써, 탐욕적 선택이 항상 안전함을 보여야 함
• 최적 부분 구조(Optimal Substructure Property)
• 👉 현재 상황에서 가장 최적의 해를 구한 이후, 나머지에서 또 최적 해를 구하는 방법을 반복할때 최적의 해를 구하는 방법을 정형화 해야 함
• 원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해임을 증명할 수 있어야 함

위의 Greedy Algorithm 설명이 이해가 되지 않는다면 밑의 예시를 보며 이해해보자.

Greedy Algorithm 예시

✔ 거스름돈 문제

만약 내가 한 가게에서 아르바이트를 하고 있다고 생각해보자. 카운터에는 거스름돈으로 사용할 수 있는 500원, 100원, 50원, 10원짜리 동전이 있다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구해보자. (단, 거슬러 주어야 할 돈인 N원은 항상 10의 배수이다.)

👉가장 큰 단위의 동전부터 거슬러 주기

1️⃣ N = 1470원이고, 동전의 단위가 [500, 100, 50, 10]인 경우

코드

package greedyAlgorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class MoneyTest {  // 거스름돈 최소개수 구하기

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

        int N = Integer.parseInt(br.readLine());  // 거슬러줄 돈
        int cnt = 0;  // 동전의 개수
        int[] money = {500, 100, 50, 10};

        for (int m : money) {
            cnt += N/m;
            N = N%m;
            System.out.println(m + "원의 동전 개수를 합한 결과 = " + cnt + ", 남은 금액 = " + N);
        }

        System.out.println("거스름돈의 동전 개수는 " + cnt);
    }
}

결과

500원의 동전 개수를 합한 결과 = 2, 남은 금액 = 470
100원의 동전 개수를 합한 결과 = 6, 남은 금액 = 70
50원의 동전 개수를 합한 결과 = 7, 남은 금액 = 20
10원의 동전 개수를 합한 결과 = 9, 남은 금액 = 0
거스름돈의 동전 개수는 9

가장 큰 단위의 동전부터 거스름돈을 나누고, 나눈 이후의 남은 거스름돈이 해당 단위로 더이상 나누어지지 않을 때 그 다음 작은 단위의 동전으로 나누기를 반복 (최적 부분 구조)

500원의 동전의 개수를 줄이거나, 100원의 동전의 개수를 줄이게 되면 총 거스름돈의 동전 개수는 9개에서 더 증가하게 되므로 최적해가 보장 (탐욕적 선택 속성)

2️⃣ N = 800원이고, 동전의 단위가 [500, 200, 100, 50]인 경우

package greedyAlgorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class MoneyTest {  // 거스름돈 최소개수 구하기

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

        int N = Integer.parseInt(br.readLine());  // 거슬러줄 돈
        int cnt = 0;  // 거슬러 줄 동전의 개수
        int[] money = {500, 400, 100, 50};

        for (int m : money) {
            cnt += N/m;
            N = N%m;
            System.out.println(m + "원의 동전 개수를 합한 결과 = " + cnt + ", 남은 금액 = " + N);
        }

        System.out.println("거스름돈의 동전 개수는 " + cnt);
    }

}

결과

500원의 동전 개수를 합한 결과 = 1, 남은 금액 = 300
400원의 동전 개수를 합한 결과 = 1, 남은 금액 = 300
100원의 동전 개수를 합한 결과 = 4, 남은 금액 = 0
50원의 동전 개수를 합한 결과 = 4, 남은 금액 = 0
거스름돈의 동전 개수는 4

이 결과가 과연 최적의 해를 보장하는가? No

400원 단위의 동전으로 800원을 거슬러준다면 단지 2개로만 거슬러 줄 수 있음(탐욕적 선택 속성 불만족)

Why? 거스름돈 문제를 그리디로 해결할 수 있는 이유

현재 우리가 실제로 사용하는 화폐의 단위는 큰 단위의 동전이 항상 작은 단위의 동전의 배수이다. 이는 곧 작은 단위의 몇 배(단, 큰 단위 이상의 값 중)를 해도 큰 단위의 배수와 다른 해가 나올 수 없다는 의미이다. 만약, 2️⃣번의 경우 처럼 400원의 배수이며 500원보다 큰 값 중 500원의 배수로 만들지 못하는 값이 있다면 거스름돈 문제에서 그리디 알고리즘은 최적의 해를 보장할 수 없게 된다.

Greedy 기반의 Algorithm

알고리즘	목적	설명	유형
Prim	최소신장트리(MST) 찾기	서브트리를 확장하면서 MST를 찾음	그래프
Kruskal		싸이클이 없는 서브 그래프를 확장하면서 MST를 찾음	그래프
Dijkstra	최단 경로 찾기	주어진 정점에서 가장 가까운 정점을 찾고, 그 다음 정점을 반복해서 찾음	그래프

해당 알고리즘들은 나중에 더 자세히 설명하도록 하겠다.

 

 

Greedy Algorithm과 관련된 유튜브 영상으로는 나동빈 - 이것이 코딩테스트다 with 파이썬을 참고하면 더 이해가 쉬우므로 영상을 한 번 보는 것을 추천