C++로 주식 매매 최대 이익 구하기 – 브루트 포스부터 효율적인 알고리즘까지

이 글에서는 배열 stkprice[]가 주어졌을 때, 주식을 사고팔아 얻을 수 있는 최대 이익을 C++로 계산하는 방법을 알아봅니다. 배열의 각 원소는 해당 날짜(i번째 날)의 주식 가격을 나타냅니다.

문제 설명

주어진 기간 동안 언제 주식을 사고 언제 팔아야 이익을 극대화할 수 있는지 찾아야 합니다. 이익을 내려면 주가가 낮을 때 사서 가격이 오른 시점에 팔면 되고, 이후 가격이 다시 하락했다면 같은 과정을 반복하면 됩니다.

예시로 문제 이해하기

입력

stkprice[] = {120, 310, 405, 210, 150, 550}

출력

설명

1일째에 주식을 사서 3일째에 팔면 이익은 285입니다.

이후 5일째에 다시 사서 6일째에 팔면 이익은 400입니다.

따라서 총 이익은 285 + 400 = 685가 됩니다.

해결 방법 1: 모든 경우 탐색 (브루트 포스)

가장 단순한 방법은 가능한 모든 매수-매도 조합을 하나씩 확인하는 것입니다. 현재 날짜를 기준으로 첫날에 사서 마지막 날에 파는 모든 사이클 조합을 시도하고, 그중 가장 큰 이익을 내는 조합을 선택합니다. 이 방법은 이해하기 쉽지만 중복 계산이 많아 시간 복잡도가 O(n²) 이상으로 느립니다.

구현 예제

#include <iostream>
using namespace std;

int max(int a, int b){
    if(a > b)
        return a;
    return b;
}

int MaximizeProfit(int stkPrice[], int firstDay, int lastDay){
    if (lastDay <= firstDay)
        return 0;
    int maxProfit = 0;
    for (int i = firstDay; i < lastDay; i++) {
        for (int j = i + 1; j <= lastDay; j++) {
            if (stkPrice[j] > stkPrice[i]) {
                int profit = (stkPrice[j] - stkPrice[i])
                             + MaximizeProfit(stkPrice, firstDay, i - 1)
                             + MaximizeProfit(stkPrice, j + 1, lastDay);
                maxProfit = max(maxProfit, profit);
            }
        }
    }
    return maxProfit;
}

int main(){
    int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
    int days = sizeof(stkPrice) / sizeof(stkPrice[0]);
    cout<<"최대 이익은 "<<MaximizeProfit(stkPrice, 0, days - 1);
    return 0;
}

출력

최대 이익은 685

참고로, 재귀 호출 시 배열 범위를 벗어난 인덱스(lastDay에 배열 크기를 그대로 전달)를 사용하면 정의되지 않은 동작으로 잘못된 값이 출력될 수 있으므로, 반드시 마지막 인덱스(days - 1)를 전달해야 합니다.

해결 방법 2: 국소 최솟값·최댓값 활용 (효율적 접근)

훨씬 효율적인 방법은 각 거래(매수-매도 사이클)별로 얻을 수 있는 최대 이익을 찾아 모두 합산하는 것입니다. 이를 위해 주가 그래프의 국소 최솟값(local minima)과 국소 최댓값(local maxima)을 찾습니다.

국소 최솟값: 전날과 다음 날보다 주가가 낮은 날
국소 최댓값: 전날과 다음 날보다 주가가 높은 날

인덱스 0부터 n-2 범위 안에 국소 최솟값이 존재하지 않는다면, 이익을 낼 수 있는 매수 시점이 없다는 의미입니다.

이익을 극대화하려면 국소 최솟값인 날에 주식을 매수하고, 바로 다음 국소 최댓값인 날에 매도하면 됩니다. 모든 최솟값-최댓값 쌍의 이익을 더하면 전체 최대 이익(maxProfit)을 구할 수 있습니다. 이 방법은 배열을 한 번만 순회하므로 시간 복잡도가 O(n)으로 매우 빠릅니다.

구현 예제

#include <iostream>
using namespace std;

void MaximizeProfit(int price[], int n){
    if (n == 1)
        return;
    int maxProfit = 0;
    int i = 0;
    while (i <= n - 1) {
        // 국소 최솟값 찾기
        while ((i <= n - 2) && (price[i + 1] <= price[i]))
            i++;
        int minima = i++;
        // 국소 최댓값 찾기
        while ((i < n) && (price[i] >= price[i - 1]))
            i++;
        int maxima = i - 1;
        maxProfit += (price[maxima] - price[minima]);
        // 각 매매 사이클의 이익을 확인하려면 아래 주석을 해제하세요
        //cout <<(minima + 1)<<"일째에 사서 "<<(maxima + 1)
        //<<"일째에 팔아 이익 "<<(price[maxima] - price[minima])<<"\n";
    }
    cout<<"최대 이익은 "<<maxProfit;
}

int main(){
    int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
    int days = sizeof(stkPrice) / sizeof(stkPrice[0]);
    MaximizeProfit(stkPrice, days);
    return 0;
}

출력

최대 이익은 685

두 방법 비교

브루트 포스: 모든 조합을 검사하므로 직관적이지만, 데이터가 커질수록 실행 시간이 급격히 증가합니다.
국소 최솟값·최댓값 탐색: 한 번의 순회(O(n))로 답을 구할 수 있어 실전에서 훨씬 효율적이며, 각 매매 시점(몇 일째에 사고팔았는지)도 손쉽게 추적할 수 있습니다.

따라서 실제 코딩 테스트나 실무에서는 국소 최솟값·최댓값을 활용한 선형 시간 알고리즘을 사용하는 것이 좋습니다.