[C++] 그리디 관련 문제 (백준 11501번, 주식)

그리디 알고리즘 (Greedy Algorithm)

이전 글과 다른 그리디 문제 풀이 글에서도 이야기했지만, "이 문제를 그리디로 풀 수 있는가?"를 판단할 수 있는 것이 중요하고, 여기에 "그리디를 어떻게 쓸 것인가?"를 결정하는 것도 어려운 문제이다.

 

그리디 알고리즘을 적용하는 방법을 1) 기준을 정의하고, 2) 정렬을 하거나 우선 순위를 지정하고, 3) 그에 따라 선택하는 흐름이라고 정리했던 적이 있다.

 

이전에 풀었던 회의실 배정 문제 (백준 1931번)를 풀 때에는 회의가 끝나는 시간을 기준으로, 내림차순으로 정렬하고, 그에 따라 겹치지 않게 선택했다. 내림차순 정렬, 또는 단순하게 앞에서 뒤로 가면서 선택하는 방식으로 그리디 알고리즘을 적용했다면, 위에서 정리한 내용을 그대로 따라가는 문제는 많지 않을 것이다. 그래서 다양한 그리디 알고리즘 적용 문제를 풀어보아야 할 것이다.

---

이번 글에서는 백준 온라인 저지의 11501번 "주식" 문제를 풀이해본다.

Reference: https://www.acmicpc.net/problem/11501

문제 분석 및 해결 전략

이득을 극대화하는 방법은 무엇일까?
이 문제에서는 미래 가격을 아는 것이 전제되어 있으므로, 미래의 가장 높은 가격을 기준으로 현재 매수 여부를 결정해야 한다.

 

이를 위한 전략을 아래와 같이 요약해볼 수 있다.

• 현재 날에서 미래를 바라본다.
• 앞으로의 가격 중 가장 높은 가격이 나오기 전까지 주식을 계속 산다.
• 최고가가 나오면 전부 판다.
• 그리고 다시 남은 날짜에 대해 반복한다.

이 전략이 탐욕적 접근이 되는 이유는 다음과 같다.

• 미래의 최고가가 언제 나오는지 이미 알고 있다.
• 지금 당장 사는 것이 이득이 될지 손해가 될지를 미래 최고가와 비교하여 정확히 알 수 있다.
• 따라서 최적의 선택이 가능하다.

구현

이 전략을 코드로 구현하기 위해서는 조금 틀어서 생각을 해야한다.

입력으로 받는 가격들의 맨 앞에서부터 보면서 검증하는 것이 아니라 맨 뒤에서부터 탐색을 시작하는 것이다. 미래의 입력을 모두 알고 있는 문제에 대해서는 이런 방법을 고려하는 것이 좋은 것 같다.

 

그리디 알고리즘을 기반으로 구현한 코드는 아래와 같다.

#include <iostream>
#include <vector>
using namespace std;

int main() {

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;
        vector<int> prices(N);

        for (int i = 0; i < N; i++) {
            cin >> prices[i];
        }

        long long profit = 0;
        int max_price = 0;

        // 가장 미래에 있는 값부터 확인
        for (int i = N - 1; i >= 0; i--) {
            if (prices[i] > max_price) {
                max_price = prices[i];
            } else {
                profit += (max_price - prices[i]);
            }
        }

        cout << profit << '\n';
    }

    return 0;
}

맨 뒤에 있는 값부터 탐색하고, 그러면서 지금까지 탐색했던 값 중 최대의 가격과 비교한다.

예를 들어서 i번부터 가장 마지막 번까지의 주식 중 i+2번째의 가격이 현재까지의 최대 주식 가격이라고 하면 (가장 마지막 주식은 i+2보다 크거나 같음), i번째와 i+1번째 주식은 i+2번째에서 모두 판매가 되어야 한다. 이를 역순으로 탐색하면서 i+2번째에는 최대 가격을 업데이트하고, i+1 번째는 i+2 번째의 주식과의 차이만큼 이익을 발생시키고, i번째도 마찬가지로 이익을 더해줄 수 있다.

 

다시 정리하면, 1) 배열을 뒤에서부터 탐색하고, 2) 현재까지 본 가격 중 최대 가격을 저장한다. 3) 만약 현재 가격이 최대보다 낮으면, 주식을 사는 것으로 처리하고 차익을 더하고, 현재 가격이 더 크면 최대 가격을 갱신하는 것이다.

 

만약 뒤에서부터 탐색하는 것을 생각하지 못하고 앞에서부터 차례대로 풀려고 하면, 그리디 알고리즘 적용이 불가능하고 답도 틀릴 것이다.

예를 들어 입력이 1 1 3 1 5로 들어오는 경우를 생각해보면 앞에서부터 뭘 하는 것이 확실히 다른 답을 보여주는 것을 알 수 있다.

---

주어진 주식 가격 배열을 뒤에서부터 본다는 구현 방식이 굉장히 참신하게 다가온 문제이다. "미래를 알 수 있다"는 조건이 주어지면 그리디 한 접근이 매우 강력해진다는 것을 알 수 있으며, 이런 문제에서는 "뒤에서부터 확인하기"를 생각할 수 있어야 한다.

 

그리디 알고리즘은 선택이 지역적 최적이면서 전체 최적이 보장될 때만 사용 가능한데, 문제를 그리디를 사용할 수 있도록 세팅하는 건 정말 어려운 것 같다. 그런데 어려운 수학문제를 푸는 것과 비슷한 기분이 들기도 한다. 어렸을 때에는 문제 푸는 것만 할 수 있었어서 몰입했던 것 같은데, 지금은 그렇게까지는 하기 어려운 것 같다. 하긴 거의 15년의 시간이 흘렀으니..