1. 그리디 알고리즘(탐욕법, Greedy Algorithm) 이란?

그리디 알고리즘은 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로, 각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘입니다. 이때 항상 최적의 값을 보장하는 것이 아니라 최적의 값의 근사한 값을 목표로 합니다. 주로 문제를 분할 가능한 문제들로 분할한 뒤, 각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 사용됩니다.

예시 문제

노드에서 가장 합이 높은 방법을 선택하는 방법을 생각해봅니다. 이 경우, 그리디 알고리즘은 기준 없이 선택하는 대신, 상황에서 가장 높은 수를 선택하는 방식으로 노드를 선택합니다.

2. 그리디 알고리즘 주요 속성

그리디 알고리즘을 적용하기 위해서는 두 가지 조건이 성립해야 합니다.

1. 탐욕 선택 속성(Greedy Choice Property)

각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 말합니다. 즉, 각 단계에서 가장 이상적인 선택을 하는 것이 전체적으로 최적의 결과를 가져온다는 것입니다.

2. 최적 부분 구조(Optimal Substructure)

전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우를 말합니다. 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미합니다.

3. 그리디 알고리즘 단계

그리디 알고리즘은 매 단계마다 최적이라고 생각되는 선택을 하면서 최종적으로 전체적으로 최적인 해답을 찾아내는 과정을 의미합니다.

그리디 알고리즘의 단계
  1. 문제의 최적해 구조를 결정합니다.
  2. 문제의 구조에 맞게 선택 절차를 정의합니다.
  3. 선택 절차에 따라 선택을 수행합니다.
  4. 선택된 해가 문제의 조건을 만족하는지 검사합니다.
  5. 조건을 만족하지 않으면 해당 해를 제외합니다.
  6. 모든 선택이 완료되면 해답을 검사합니다.
  7. 조건을 만족하지 않으면 해답으로 인정되지 않습니다.

4. 그리디 알고리즘 vs 동적 계획법

그리디 알고리즘과 동적 계획법을 비교해보겠습니다.

분류 그리디 알고리즘(Greedy Algorithm) 동적 계획법(DP: Dynamic Programming)
설명 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결
성립 조건 1. 탐욕 선택 속성 2. 최적 부분 구조 1. 중복 부분 문제 2. 최적 부분 구조
중복 부분 문제 해결하지 않음 해결 가능
상황 각 단계의 상황에서 최적을 선택하여 최적의 경로를 구함. 최적이 아닌 경우도 있을 수 있음 모든 상황을 계산하여 최적의 경로를 구할 수 있음. 시간이 오래 걸림

5. 그리디 알고리즘 예시

1. 거스름돈 문제

문제: 1260원을 거슬러줘야 할 때 500원, 100원, 50원, 10원짜리 동전이 무한정 존재한다면, 가장 큰 동전부터 가능한 많이 사용하는 방식으로 거스름돈을 계산합니다.

그리디 알고리즘 적용:

  1. 선택 절차: 가장 가치가 큰 동전부터 선택합니다.
  2. 적절성 검사: 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택합니다.
  3. 해답 검사: 합이 일치하면 거스름돈 문제가 해결되었습니다.

알고리즘 단계

1단계: 문제의 최적해 구조를 결정합니다.

  • 여기서는 거스름돈 문제로, 각 단계에서 가능한 가장 큰 동전을 선택하여 남은 거스름돈을 줄여 나갑니다.

2단계: 선택 절차(Selection Procedure)

  • 가장 가치가 큰 동전부터 선택합니다. 이를 위해 동전 배열을 내림차순으로 정렬합니다.

3단계: 선택 절차에 따라 선택을 수행합니다.

  • 거스름돈을 가장 큰 동전으로 나눈 몫만큼 해당 동전을 사용하고, 나머지 금액으로 다음 동전을 선택합니다.

4단계: 선택된 해가 문제의 조건을 만족하는지 검사합니다.

  • 선택된 동전으로 거스름돈을 계산할 수 있는지 확인합니다. 이 단계에서는 각 동전의 가치가 거스름돈보다 작거나 같은지 검사합니다.

5단계: 조건을 만족하지 않으면 해당 해를 제외합니다.

  • 동전의 가치가 거스름돈보다 크다면 해당 동전은 사용하지 않고 다음으로 작은 동전을 선택합니다.

6단계: 모든 선택이 완료되면 해답을 검사합니다.

  • 모든 거스름돈이 0이 되면 문제를 해결한 것입니다.

7단계: 조건을 만족하지 않으면 해답으로 인정되지 않습니다.

  • 여기서는 주어진 동전으로 모든 거스름돈을 정확히 거슬러 줄 수 있는지 확인합니다. 이 문제에서는 모든 동전이 10의 배수이므로 항상 정확히 거슬러 줄 수 있습니다.

Java 코드:

import java.util.Arrays;
import java.util.Comparator;

public class ChangeMoney {
    public static void main(String[] args) {
        // 1. 문제의 최적해 구조를 결정합니다.
        Integer[] coins = {500, 100, 50, 10}; // 동전 종류
        int money = 1260; // 거스름돈
        int count = 0; // 동전 사용 개수

        // 2. 선택 절차 적용 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택합니다.
        Arrays.sort(coins, Comparator.reverseOrder());

        // 3. 선택 절차에 따라 선택을 수행합니다.
        for (int coin : coins) {
            count += money / coin; // 해당 동전을 사용한 개수 추가
            money %= coin; // 나머지 금액 갱신
        }

        // 6. 모든 선택이 완료되면 해답을 검사합니다.
        System.out.println("동전의 개수: " + count);
    }
}

코드 설명

1. 문제의 최적해 구조를 결정합니다.

  • Integer[] coins = {500, 100, 50, 10};: 다양한 가치의 동전 종류를 정의합니다.
  • int money = 1260;: 거스름돈의 총액을 정의합니다.
  • int count = 0;: 사용된 동전의 개수를 저장할 변수를 초기화합니다.

2. 선택 절차(Selection Procedure)

  • Arrays.sort(coins, Comparator.reverseOrder());: 동전 종류를 내림차순으로 정렬합니다. 이는 가장 큰 가치의 동전부터 사용하기 위해서입니다.

3. 선택 절차에 따라 선택을 수행합니다.

  • for (int coin : coins) {: 각 동전에 대해 반복합니다.
  • count += money / coin;: 현재 동전의 가치로 나눈 몫을 사용하여 동전 개수를 계산하고 누적합니다.
  • money %= coin;: 현재 동전으로 나눈 나머지 금액을 업데이트합니다.

4. 모든 선택이 완료되면 해답을 검사합니다.

  • System.out.println("동전의 개수: " + count);: 사용된 총 동전 개수를 출력합니다.
2. 그리디 알고리즘을 사용이 적합하지 않은 경우

그리디 알고리즘이 항상 최적해를 보장하지 않는 경우도 있어요.

최적해를 보장하지 않는 문제 예시:
최소한의 동전 개수로 거스름돈을 줘야 할 때, 동전의 종류가 1, 3, 4 센트인 경우.

import java.util.Arrays;

class Main {
    public static int minCoinsGreedyFailure(int[] coins, int amount) {
        Arrays.sort(coins);
        int count = 0;
        for (int i = coins.length - 1; i >= 0; i--) {
            count += amount / coins[i];
            amount %= coins[i];
        }
        return count;
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 4};
        int amount = 6;
        System.out.println(minCoinsGreedyFailure(coins, amount));
    }
}

위 예시에서 6센트를 만들기 위해 4센트를 먼저 선택하면 나머지 2센트를 위해 1센트 동전 두 개를 사용하게 돼요. 하지만 최적해는 3센트 동전 두 개를 사용하는 것이기에 틀린 답이에요.

해결방법

이 문제를 해결하기 위해 동적 계획법(Dynamic Programming)을 사용할 수 있습니다. 동적 계획법은 문제를 작은 부분 문제로 나누어 각각의 부분 문제를 해결한 후, 이를 조합하여 전체 문제의 최적해를 구하는 방법입니다.

동적 계획법을 사용한 코드

package greedy;

import java.util.Arrays;

class MinCoinsDP {
    public static int minCoinsDP(int[] coins, int amount) {
        int[] dp = new int[amount + 1];// 금액을 저장할 dp 배열 생성
        Arrays.fill(dp, amount + 1);// dp 배열을 amount + 1로 초기화 (최대 금액 + 1은 불가능한 큰 값)
        dp[0] = 0;// 금액 0을 만드는 데 필요한 동전 개수는 0


        for (int i = 1; i <= amount; i++) {// 금액 1부터 amount까지 반복
            for (int coin : coins) {// 각 동전에 대해 반복
                if (i - coin >= 0) {// 현재 금액 i에서 동전 coin을 사용할 수 있는지 확인
                    int previousAmount = dp[i];// 이전 금액에서의 최소 동전 개수
                    int newAmount = dp[i - coin] + 1;// 새로운 금액에서의 최소 동전 개수 (현재 동전 coin을 사용했을 때)
                    dp[i] = Math.min(previousAmount, newAmount);// 두 값 중 작은 값으로 dp[i] 업데이트
                }
            }
        }

        // 주어진 금액을 만들 수 없으면 -1 반환, 그렇지 않으면 최소 동전 개수 반환
        return dp[amount] > amount ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 4}; // 동전 종류
        int amount = 6; // 거스름돈
        System.out.println(minCoinsDP(coins, amount));// 최소 동전 개수 출력
    }
}

코드설명

질문

  • dp 배열에 금액을 저장하는 이유?!

dp 배열에 금액을 저장하는 이유는 동적 계획법(Dynamic Programming)의 핵심 개념인 메모이제이션(Memoization)과 관련이 있습니다. 이를 통해 문제를 작은 부분 문제로 나누고, 각 부분 문제를 해결한 결과를 저장하여 중복 계산을 피하고 효율적으로 문제를 해결할 수 있습니다.

상세 설명
동적 계획법은 큰 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 큰 문제를 해결하는 방법입니다. 여기서 dp 배열은 각 금액을 만들기 위한 최소 동전 개수를 저장하는 역할을 합니다.

1. 부분 문제의 해결
dp[i]는 금액 i를 만드는 데 필요한 최소 동전 개수를 나타냅니다. 예를 들어, dp[3]은 금액 3을 만드는 데 필요한 최소 동전 개수입니다.

2. 중복 계산 방지
동적 계획법의 중요한 특징은 중복 계산을 피하는 것입니다. 한번 계산된 값은 dp 배열에 저장되므로, 동일한 부분 문제가 다시 발생하면 저장된 값을 재사용할 수 있습니다. 이렇게 하면 시간 복잡도를 크게 줄일 수 있습니다.

3. 최적해 계산
각 금액 i에 대해 최소 동전 개수를 계산하면서, 그 결과를 dp[i]에 저장합니다. 이를 통해 점진적으로 최적해를 구할 수 있습니다. 작은 금액부터 시작하여 점차 큰 금액으로 확장하면서, 최종적으로 원하는 금액 amount를 만드는 데 필요한 최소 동전 개수를 구하게 됩니다.

1. dp 배열 초기화:

  • int[] dp = new int[amount + 1];:

    • amount까지의 금액을 저장할 dp 배열을 생성합니다. 배열의 크기를 amount + 1로 설정한 이유는 dp 배열이 0부터 amount까지의 금액을 모두 포함해야 하기 때문입니다. 예를 들어, amount가 6이라면, dp 배열은 인덱스 0부터 6까지 총 7개의 요소를 가집니다.

  • Arrays.fill(dp, amount + 1);:

    • dp 배열을 amount + 1로 초기화합니다. 여기서 amount + 1은 불가능한 큰 값으로 설정합니다. 이는 모든 금액을 초기값으로 설정하여 나중에 더 작은 값으로 갱신하기 위해서입니다. 만약 amount가 6이라면, 배열은 [7, 7, 7, 7, 7, 7, 7]로 초기화됩니다. 이 값을 사용하는 이유는 나중에 최소값을 찾기 위한 비교에서 유리하기 때문입니다. amount + 1로 초기화하면 동전의 개수가 실제로 구해지는 상황에서는 이 값보다 작아지기 때문에 초기값으로서 적절합니다.

  • dp[0] = 0;:

    • 금액 0을 만드는 데 필요한 동전 개수는 0입니다. 따라서 dp[0]은 0으로 설정합니다. 이는 금액이 0일 때는 동전이 필요 없음을 의미합니다. 이 기본값은 나중에 다른 금액을 계산할 때 기반이 됩니다. 예를 들어, 금액 1을 계산할 때 금액 0에 동전 1을 더하면 되므로, dp[1]은 1이 됩니다.

2. 부분 문제 해결:

  • for (int i = 1; i <= amount; i++) {:

    • 금액 1부터 amount까지 모든 금액을 반복합니다. 즉, i는 현재 계산 중인 금액을 나타냅니다. 이 루프는 각 금액에 대해 최소 동전 개수를 계산합니다. 예를 들어, i가 1일 때, 금액 1을 만들기 위해 필요한 최소 동전 개수를 계산합니다.

  • for (int coin : coins) {:

    • 각 동전에 대해 반복합니다. 즉, 주어진 동전 종류를 하나씩 검사합니다. coins 배열에는 사용 가능한 동전의 종류가 저장되어 있습니다. 예를 들어, coins 배열이 {1, 3, 4}라면, 이 루프는 동전 1, 3, 4를 각각 검사합니다.

  • if (i - coin >= 0) {:

    • 현재 금액 i에서 동전 coin을 뺄 수 있는지 확인합니다. 즉, 동전 coin을 사용할 수 있는지 확인하는 조건문입니다. 예를 들어, 현재 금액 i가 5이고 동전 coin이 3이라면, 5 - 3 = 2이므로 조건을 만족합니다. 하지만 i가 2이고 coin이 3이라면, 2 - 3 = -1이므로 조건을 만족하지 않습니다.

  • int previousAmount = dp[i];:

    • 현재 금액 i를 만드는 데 필요한 최소 동전 개수를 변수 previousAmount에 저장합니다. 이는 이전에 계산된 값입니다. 예를 들어, dp[i]가 7로 초기화되어 있으면 previousAmount도 7이 됩니다.

  • int newAmount = dp[i - coin] + 1;:

    • 현재 금액 i - coin을 만드는 데 필요한 최소 동전 개수에 동전 coin 하나를 더한 값을 변수 newAmount에 저장합니다. 이는 새로운 방법으로 금액 i를 만드는 데 필요한 동전 개수입니다. 예를 들어, 현재 금액 i가 5이고 동전 coin이 3이라면, dp[2] + 1이 됩니다. 여기서 dp[2]는 금액 2를 만드는 데 필요한 최소 동전 개수이고, 여기에 1을 더하면 동전 3 하나를 추가한 것입니다.

  • dp[i] = Math.min(previousAmount, newAmount);:

    • previousAmount와 newAmount 중 작은 값을 선택하여 dp[i]를 업데이트합니다. 이는 금액 i를 만드는 데 필요한 최소 동전 개수를 최신 상태로 유지합니다. 예를 들어, previousAmount가 7이고 newAmount가 3이라면, dp[i]는 3으로 업데이트됩니다.

3. 결과 반환:

  • return dp[amount] > amount ? -1 : dp[amount];:
    • 주어진 금액 amount를 만들 수 없으면 -1을 반환하고, 그렇지 않으면 최소 동전 개수를 반환합니다. dp[amount] > amount는 dp[amount]가 여전히 초기화된 값(즉, amount + 1)인 경우로, 이는 주어진 금액을 만들 수 없음을 의미합니다. 예를 들어, amount가 6인데 dp[6]이 7이라면, 금액 6을 만들 수 없음을 나타냅니다. 그렇지 않은 경우, dp[amount]는 주어진 금액을 만드는 데 필요한 최소 동전 개수를 나타냅니다.

이와 같이, 동적 계획법을 사용하여 주어진 금액을 만드는 데 필요한 최소 동전 개수를 계산할 수 있습니다. 이 방법은 그리디 알고리즘이 최적해를 보장하지 않는 경우에도 정확한 해를 구할 수 있는 효율적인 방법입니다. 🧑‍💻💡

3. 체육복 문제

문제: 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다.

그리디 알고리즘 적용:

  1. 선택 절차: 체육복을 잃어버린 학생과 여벌 체육복을 가져온 학생의 번호를 오름차순으로 정렬합니다.
  2. 적절성 검사: 체육복을 잃어버린 학생 중 여벌이 있는 학생에게 빌려줄 수 있는 학생 수를 계산합니다.
  3. 해답 검사: 체육복을 빌려 받은 학생 수를 계산하여 반환합니다.

Java 코드:

import java.util.*;

public class GymClothes {
    public static void main(String[] args) {
        int n = 5;
        int[] lost = {2, 4};
        int[] reserve = {1, 3, 5};

        System.out.println(solution(n, lost, reserve));
    }

    public static int solution(int n, int[] lost, int[] reserve) {
        int answer = n - lost.length;

        Arrays.sort(lost);
        Arrays.sort(reserve);

        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if (lost[i] == reserve[j]) {
                    answer++;
                    reserve[j] = -1;
                    break;
                }
            }
        }

        for (int i = 0; i < lost.length; i++) {
            for (int j = 0; j < reserve.length; j++) {
                if (reserve[j] == lost[i] - 1 || reserve[j] == lost[i] + 1) {
                    answer++;
                    reserve[j] = -1;
                    break;
                }
            }
        }

        return answer;
    }
}

결론

그리디 알고리즘은 각 단계에서 최적의 선택을 하는 근시안적인 방법론으로, 최적의 값 대신 근사한 값을 목표로 합니다. 이 알고리즘은 탐욕 선택 속성과 최적 부분 구조를 만족할 때 적용할 수 있으며, 거스름돈 문제와 체육복 문제와 같은 다양한 실제 문제에 적용될 수 있습니다. 동적 계획법과 비교했을 때, 그리디 알고리즘은 중복 부분 문제를 해결하지 않으며 각 단계에서의 최적 선택이 항상 전체 문제의 최적 해답을 보장하지 않습니다. 그러나 구현이 간단하고 빠르다는 장점이 있습니다.

저작자표시

'여러가지 > 알고리즘 & 자료구조' 카테고리의 다른 글

[백준] A->B - 16953번  (0) 2024.06.14
[백준] 동전 0 - 11047번  (0) 2024.06.14
[백준] 별자리가될수있다면 - 30821번  (0) 2024.06.13
[백준] 청정순열 - 25176  (1) 2024.06.13
[백준] 슈퍼마리오 - 2851번  (0) 2024.06.13

티스토리툴바