[C++] 코딩테스트 대비 - Greedy 알고리즘

 Greedy 알고리즘 개념 

Greedy Algorithm 정의

탐욕, 욕심쟁이 알고리즘이라고도 불리며, 현재 상태에서의 최적의 해가 최종적으로도(전체적으로도) 최적의 해가 될 것이라고 가정하고 접근하는 알고리즘이다.

그리디 알고리즘은 대부분의 문제에서 해답에 대한 '근사적인' 솔루션을 도출해 낼 수 있다는 장점이 있고, 그리디로 풀 수 있는 문제는 다음과 같은 두 가지 조건을 만족시켜야 한다.

1. 탐욕적 선택 속성: 앞의 선택이 이후의 선택에 영향을 주지 않아야 한다.
2. 최적 부분 구조: 문제에 대한 최종 해결 방법은 sub problem들의 optimal solution들로 구성된다.

주의할 점

모든 문제가 그리디 알고리즘으로 풀리는 것이 아니기 때문에, 이 알고리즘으로 풀리는 문제인지 아닌지 구분하기가 매우 어렵다는 특징이 있다.

1. 문제가 sub problems로 구분이 가능한지를 파악하는 것이 중요하다.
2. 최적의 해를 구하기 위한 정렬 조건을 빠르게 파악해야 한다.
3. plot twist 가 일어난다면, '최적'을 구하기 위한 '정렬'이 항상 앞에서만 일어나지는 않는 문제도 있다.

개인적으로 참 어려워했던 문제 유형이다(어떻게 풀어야 할 지 항상 감을 잡기 어려웠다)

---

Keyword: Graph, Greedy, Search. Created by DALL-E 2023

 

 Greedy 알고리즘 문제 접근법 

부분 문제에 대한 최적의 해를 구하기 위해서 어떠한 기준에 대한 '정렬'을 사용해야하는 경우가 많다. 정렬을 통해 가장 높거나 낮은 값을 기준으로 optimal solution을 구한 뒤, 최종적으로 합치는 등의 작업을 수행한다. 정렬에는 다음과 같은 알고리즘 혹은 자료구조가 사용된다.

• <algorithm> sort();
• <queue> priority_queue<> pq;

 

딱히 정형화된 문제 풀이 코드는 없으나, 우선순위 큐 혹은 정렬을 사용하여 다음과 같이 풀어볼 수 있다.

// 백준 1715 풀이의 일부
void Solve(){
    cin >> N;
    for(int n=0; n<N; n++){
        int _in;
        cin >> _in;
        input.push(-_in);
    }

    int f, s;
    for(int i=0; i<N-1; i++){
        f = -input.top(); input.pop();
        s = -input.top(); input.pop();

        answer += f+s;
        input.push(-(f + s));
    }
    cout << answer;
}

 

---

대표적인 유형문제

1. 회의실 배정 - https://www.acmicpc.net/problem/1931
2. https://www.acmicpc.net/problem/1946
3. 어려웠던 문제. https://www.acmicpc.net/problem/13904
4. https://school.programmers.co.kr/learn/courses/30/lessons/42883
5. https://school.programmers.co.kr/learn/courses/30/lessons/42885
6. https://www.acmicpc.net/problem/1700
7. https://www.acmicpc.net/problem/2437

 

참고한 사이트

1. https://hanamon.kr/
2. https://www.zerocho.com/
3. https://www.acmicpc.net/
4. https://school.programmers.co.kr/