그리디(Greedy) 알고리즘

그리디(탐욕) 알고리즘은 매 순간 최적의 선택을 함으로써 전체 최적해에 도달하려는 알고리즘입니다. 즉, 문제 해결 과정에서 지금 당장 가장 좋아 보이는 선택을 계속해서 하는 방식입니다. 이러한 선택들은 각 단계에서 부분적인 최적해를 구성하고, 최종적으로 전체 최적해를 구성하는 데 도움을 줍니다.

greedy

그리디 알고리즘의 특징

1. 국소 최적 선택(Local Optimal Choice): 그리디 알고리즘은 각 단계에서의 최적해를 구하려고 합니다. 이는 전체 문제의 최적해를 보장하기보다는 각 단계의 최적해를 보장하는 접근 방식입니다.
2. 문제 분할: 큰 문제를 여러 단계의 작은 문제로 나눕니다. 매 단계에서 현재 상황에서 최적의 선택을 하고, 그 선택을 기반으로 다음 단계로 넘어갑니다.
3. 한 번의 선택: 한 번 내린 선택은 이후의 단계에서 바꾸지 않으며, 결정된 사항은 최종 해에 포함됩니다.

그리디 알고리즘이 유효한 경우

모든 문제에 그리디 알고리즘을 적용할 수 있는 것은 아니며, 다음 두 조건을 만족할 때 유효합니다.

• 탐욕 선택 속성(Greedy Choice Property): 문제를 최적의 방법으로 풀기 위해 항상 최적의 선택을 할 수 있는 성질이 있어야 합니다.
• 최적 부분 구조(Opitmal Substructure): 부분 문제의 최적해를 결합해 전체 문제의 최적해를 구성할 수 있어야 합니다.

그리디 알고리즘의 예시

1. 동전 거스름돈 문제: 최소 동전의 개수로 거스름돈을 줄 때, 큰 금액부터 선택하는 것이 최적의 해결책이 됩니다.
2. 최대 이익을 얻는 배낭 문제(Knapsack Problem) (단, Fractional Knapsack에 한정): 각 물건의 무게 대비 가치를 기준으로 가장 가치가 높은 것부터 선택해 가방에 담는 방식입니다.
3. 활동 선택 문제(Activity Selection Problem): 여러 활동 중 서로 겹치지 않으면서 최대한 많은 활동을 선택하는 문제에서, 종료 시간이 빠른 순서대로 선택하면 최적해를 구할 수 있습니다.

간단한 예제 코드

동전 거스름돈 문제의 기본 개념

예를 들어, 거스름돈을 줄 금액이 1260원이고, 사용할 수 있는 동전 단위가 500원, 100원, 50원, 10원이라고 합시다. 이 문제의 목표는 주어진 금액을 최소한의 동전 개수로 맞추는 것입니다.

동전 단위를 큰 금액 순서대로 사용하여 1260원을 거슬러 줍니다:

1. 가장 큰 동전인 500원을 최대한 사용합니다. 1260원을 500으로 나누면 2번 사용할 수 있고, 남은 금액은 260원이 됩니다.
2. 그다음 100원을 최대한 사용합니다. 260원을 100으로 나누면 2번 사용할 수 있고, 남은 금액은 60원이 됩니다.
3. 50원을 사용합니다. 60원을 50으로 나누면 1번 사용할 수 있고, 남은 금액은 10원이 됩니다.
4. 마지막으로 10원을 사용하여 남은 10원을 1번 사용하여 맞출 수 있습니다.

결과적으로 필요한 최소 동전 개수는 6개입니다.

그리디 알고리즘이 적합한 이유

이 문제에서 그리디 방식이 적용 가능한 이유는:

1. 큰 단위의 동전이 작은 단위의 동전의 배수라는 점입니다. 100원은 10원의 배수이고, 50원 역시 10원의 배수이기 때문에 큰 동전 단위를 최대한 사용하는 것이 항상 최소 개수를 보장합니다.
2. 탐욕 선택 속성과 최적 부분 구조를 만족합니다. 가장 큰 단위의 동전을 사용하는 것이 당장 최선의 선택이므로, 부분 최적해가 전체 최적해를 구성하는데 영향을 미치지 않고 최적의 결과를 제공합니다.

그리디 방식 풀이의 과정

1. 현재 상태에서 가장 큰 단위의 동전을 가능한 최대한으로 사용합니다.
2. 남은 금액에 대해서 같은 방법을 반복하여, 점차 필요한 동전 수를 계산합니다.
3. 최종적으로 남은 금액이 0원이 되면, 사용된 동전 개수를 반환합니다.

golang

package main

import "fmt"

func coinChange(amount int, coins []int) int {
	count := 0
	for _, coin := range coins {
		if amount == 0 {
			break
		}
		count += amount / coin
		amount %= coin
	}
	return count
}

func main() {
	coins := []int{500, 100, 50, 10} // 큰 금액 순서대로 정렬된 동전 배열
	amount := 1260
	fmt.Println("Minimum coins needed:", coinChange(amount, coins)) // 결과: 6
}

 

java

public class CoinChange {
    public static int coinChange(int amount, int[] coins) {
        int count = 0;
        for (int coin : coins) {   // 큰 동전부터 하나씩 시도
            if (amount == 0) {
                break;
            }
            count += amount / coin; // 현재 동전으로 사용할 수 있는 최대 개수를 더함
            amount %= coin;         // 남은 금액을 업데이트
        }
        return count;
    }

    public static void main(String[] args) {
        int[] coins = {500, 100, 50, 10};
        int amount = 1260;
        System.out.println("Minimum coins needed: " + coinChange(amount, coins)); // 결과: 6
    }
}

• 큰 단위 동전부터 순차적으로 접근하는 for 루프는 그리디 방식을 반영합니다.
• 각 동전에 대해 최대 개수를 사용하고, 잔액을 업데이트하여 다음 작은 동전 단위로 계속해서 해결해 나갑니다.

그리디 방식의 장점과 한계

• 장점: 그리디 알고리즘은 복잡한 탐색을 줄이고, 빠르고 효율적으로 최적해에 도달할 수 있습니다. 동전 거스름돈 문제에서는 큰 동전부터 순차적으로 사용함으로써 최소 개수를 얻을 수 있습니다.
• 한계: 문제에 따라 그리디가 항상 최적해를 보장하지는 않습니다. 예를 들어, 동전 단위가 배수가 아닌 경우(예: 1원, 3원, 4원)에는 그리디 방식으로는 최적해를 구할 수 없으므로, 동적 프로그래밍(DP) 방식이 필요할 수 있습니다.

동전 거스름돈 문제는 그리디 알고리즘이 어떻게 단순하면서도 효율적으로 문제를 해결하는지 보여주는 좋은 예입니다.