Greedy Algorithm 탐욕법 정리

Dynamic Programming처럼 현 단계에서 이전 단계를 이끌어내는 기법에 비하여

Greedy Algorithm은 현 단계에서 가장 최적인 다음 단계를 만들어내는 기법이다.

Greedy Algorithm의 가장 기본적인 원리는 최댓값 max[n] 혹은 최솟값 min[n] 에서 배열의 다음 값인 arr[n+1]의 값을 더하거나 빼서 max[n+1] 혹은 min[n+1]을 만들어내는 방식이다.

---

예를 들어서 a라는 지점에서 d라는 지점까지 가는 방법이

1. a->b->d
2. a->c->d

2가지인 경우라고 생각을 해보자.

a->b까지 걸리는 시간이 1시간, b->d까지 걸리는 시간이 1시간이고
a->c까지 걸리는 시간이 1시간 40분, c->d 까지 걸리는 시간이 40분 일 경우

우리는 당연하게도 a->b->d 라는 길을 선택하게 된다.

이러한 방식을 사용하는 것처럼 동적 계획법과는 다르게 다음 지점에 도착할 수 있는 최솟값 혹은 최댓값을 찾는 방식이 바로 Greedy 알고리즘이다.

---

가장 기초적인 문제는 누구나 알고 있는 11047번 동전 문제가 있다.

동전 문제는 최대한 적은 동전의 개수로 거스름돈을 만들어내는 탐욕법의 가장 기초적인 문제이다.

henrynoh.tistory.com/10?category=952034

11047번 동전0 BOJ 백준 C언어

동전 문제만큼 쉬운 문제는 사실 탐욕법 문제에서는 등장하지 않는다.

따라서 실질적으로 greedy 알고리즘을 공부하기 위해서는 1단계 수준부터 공부하기를 권장한다.

---

1단계에서 소개할 문제는 1931번 회의실 배정 문제가 있다.

greedy 알고리즘을 해결하는 방식으로 대표되는 유형이다.

일단 기본적으로 주어진 입력값을 오름차순으로 정렬한 다음 문제를 해결하는 방식이다.

최솟값부터 더해진다면 현재 값은 그 어떤 경우에서도 최솟값이기 때문이다.

henrynoh.tistory.com/11?category=952034

1931번 회의실 배정 BOJ 백준 C언어

비슷한 문제로는 11399번 ATM문제 / 프로그래머스 level3 단속카메라 (문제링크)정도가 있다.

---

2단계에 들어서면 1541 잃어버린 괄호 문제 정도가 있다.

잃어버린 괄호 문제부터는 단순히 다음 경우를 1가지만 보는 것이 아니라 3~4가지로 나눠지는 경우의 수를 판단하여 다음의 최솟값을 구해줘야 한다. 얼핏 보면 BFS와 비슷해 보이지만 모든 탐색을 하는 것이 아니기 때문에 greedy 알고리즘으로 분류된다.

잃어버린 괄호 문제의 경우 총 3가지로 분기점이 나뉘게 된다.

henrynoh.tistory.com/20?category=952034

1541번 잃어버린 괄호 BOJ 백준 C언어

사실 프로그래머스의 난이도 책정이 왜 저렇게 된 것인가는 잘 모르겠지만

level1 체육복 (문제링크) / level2 큰 수 만들기 (문제링크) / level2 구명보트 (문제링크) 정도가 있다.

다만 위 3문제 모두 잃어버린 괄호 문제보다는 확실하게 어렵다는 것을 느낄 수 있다.
잃어버린 괄호 문제 같은 경우에는 명확하게 다음 경우의 수가 보이는데 위 세문제 같은 경우에는 그렇지가 않다.

3가지 문제에 대한 풀이를 보자면

체육복 문제는

n명만큼의 학생을 배열로 선언 후 모두 -1로 초기화해준다.

여벌의 체육복을 가진 reserve 배열의 경우 해당 인덱스를 2로 바꿔준다.

체육복을 잃어버린 lost 배열의 경우 해당 인덱스를 0으로 바꿔준다. 이때 reserve 했지만 lost 한 경우는 1로 바꿔준다.

앞에서부터 배열을 탐색하며

1. 배열의 값이 2일 경우 배열의 값이 0인 앞 학생 또는 뒤 학생에게 준다. 건네줄 경우 둘 다 1로 바꾼다.
2. 배열의 값이 1일 경우 건너뛴다.
3. 최종적으로 1 또는 2의 값을 가질 경우 answer를 더해준다.

의 과정을 거치면 된다.

큰 수 만들기 문제는

1. 길이가 s인 문자열에서 n자리 큰 수를 만들기 위해서 0부터 s-n까지 탐색하며 최대의 수가 1번째 자리에 온다.
2. 최대의 수 앞까지 모든 수를 삭제해주고 n-1자리 큰 수에 대하여 1번의 과정을 반복한다.

위의 방식을 실제 예를 통해서 보자. 1924에서 2자리 최대한 큰 수를 만들기 위해서는

1. 1, 9, 2를 탐색하며 최대한 큰 수를 찾는다. (2까지 탐색하는 이유는 만약 3번째 수가 가장 클 경우 마지막 수는 무조건 들어와야 하기 때문이다.)
2. 9가 선택되고 나면 9를 넣어주고 1과 9를 삭제해준 다음 24에 대하여 똑같은 과정을 반복한다.

구명보트 문제의 경우는 사실 조금 다르게 생각해야 한다.

해당 문제는 풀이를 생략하고 직접 풀어보길 바란다!

---

3단계 정도의 수준에서는 프로그래머스 level3 섬 연결하기 문제가 있다.

섬 연결하기 문제는 사실 dijkstra 알고리즘을 이해하고 있다면 정말 아주 손쉽게 해결할 수 있는 문제이다.

다만 dijkstra 알고리즘에 대하여 이해하지 못하고 있고 해당 알고리즘을 본 적이 없다면 정말 오랜 시간이 걸려도 풀기가 힘든 문제이다.

섬 연결하기(문제링크)

<해결 코드 첨부>

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> d;
int gsI(int n, vector<bool> v)
{
    int min = 1000000000;
    int index = 0;
    for (int i = 0; i < n; i++)
    {
        if (d[i] < min && !v[i])
        {
            min = d[i];
            index = i;
        }
    }
    return index;
}

void dijkstra(int s, int n, vector<vector<int>> graph, vector<bool> v)
{
    for (int i = 0; i < n; i++)
        d[i] = graph[s][i];
    v[s] = true;
    for (int i = 0; i < n; i++)
    {
        int c = gsI(n, v);
        v[c] = true;
        for (int j = 0; j < n; j++)
        {
            if (!v[j])
            {
                if (graph[c][j] < d[j])
                    d[j] = graph[c][j];
            }
        }
    }
}

int solution(int n, vector<vector<int>> costs) {
    int answer = 0;
    sort(costs.begin(), costs.end());
    vector<vector<int>> graph(n,vector<int>(n,1000000000));
    vector<bool> v(n, false);
    for (int i = 0; i < n; i++)
        d.push_back(1000000000);

    for (int i = 0; i < costs.size(); i++)
    {
        graph[costs[i][0]][costs[i][1]] = costs[i][2];
        graph[costs[i][1]][costs[i][0]] = costs[i][2];
    }
    int s = costs[0][0];
    dijkstra(s, n, graph, v);
    for (int i = 0; i < d.size(); i++)
    {
        if (d[i] != 1000000000)
            answer += d[i];
    }
    return answer;
}

dijkstra 알고리즘의 경우 greedy 알고리즘에서 최단 경로를 찾는 가장 대표적인 알고리즘이다. 해당 알고리즘에 대하여 이해하지 못하고 있거나 아직까지 모른다면 무조건 필수로 찾아서 공부하길 권장한다.

비슷한 알고리즘으로는 Kruskal 알고리즘이 있다.

비슷한 수준으로는 개인적으로 헷갈리고 어렵다고 생각되는 level2 조이스틱 (문제링크) 가 있다.

---

위 문제들을 풀게 된다면 greedy 알고리즘의 기초적인 공부가 끝났다고 봐도 무방하다.

결국 greedy 알고리즘을 해결하기 위해서는 정말 해당 유형의 다양한 문제를 풀어보는 것과 어떤 것이 다음 최적해일까를 찾아내는 것이 가장 중요하다.

동적 계획법과 탐욕 법은 비슷한 듯 다르면서 많이 출제되지는 않지만 해결하는 방법을 모르고 있다면 아주 오랜 시간이 걸리는 문제들이다. 따라서 개인적으로 꼭 공부하길 권장하는 바이다.