[알고리즘] 그리디

🤗그리디?

눈앞의 이익만 우선 추구하는 알고리즘을 총칭해서 그리디 알고리즘이라고 한다.

그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우도 있다.

그리디 알고리즘은 최적화 문제를 대상으로 한다.

최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다.

그리디 알고리즘에서 최적해를 보장하는 알고리즘은 프림 알고리즘을 예로 들을 수 있다.

🐻예시

int Post(int n) {
    int d[3] = { 10, 50, 80 };
    int* dp = malloc(sizeof(int) * n + 1);
    for (int i = 1; i <= n; i++) dp[i] = INT_MAX;
    dp[0] = 0;

    for (int i = 0; i < 3; i++) {
        int coin = d[i];
        for (int j = coin; j <= n; j++) {
            dp[j] = min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[n];
}

int Post_Greedy(int n) {
    int d[3] = { 80, 50, 10 };
    int count = 0;
    int c[3] = { 0,0,0 };
    for (int i = 0; i < 3; i++) {
        while (n >= d[i]) {
            n -= d[i];
            c[i]++;
            count++;
        }
    }
    printf("80원: [%d개] | 50원: [%d개] | 10원: [%d개]\n", c[0], c[1], c[2]);
    return count;
}

이 코드는 우표의 갯수를 구하는 문제이다. 만약 내가 가진 돈을 입력했을때, 10원 50원 80원짜리 우표를 최소로 살수 있는 갯수를 구하는 문제이다.

Post함수는 다이나믹프로그래밍으로 문제를 푼 방법이고 아래 방법은 그리디 알고리즘을 이용해 문제를 푼 방법이다.

만약 내가 160원을 가지고 있다면 다이나믹 프로그래밍으로도 그리디 알고리즘으로도 80원짜리 2개로 최적해가 구해질 것이다.
하지만 만약 100원을 가지고있다면 다이나믹프로그래밍으로는 50원 2개가 구해지겠지만, 그리디 알고리즘은 80원 1개 10원 2개로 최적해가 보장이 되지않는다.