주식을 최대 두 번 사고팔 때 얻을 수 있는 최대 이익 구하기

한 명의 거래자가 아침에 주식을 매수하고 저녁에 매도하는 방식으로 거래를 진행한다고 가정해 봅시다. 하루에 허용되는 거래는 최대 두 번이며, 두 번째 거래는 반드시 첫 번째 거래가 완료된 이후에만 시작할 수 있습니다. 이처럼 주식 가격 목록이 주어졌을 때, 거래자가 얻을 수 있는 최대 이익을 구하는 것이 이 문제의 목표입니다.

입력과 출력

입력:
주식 가격 목록 {2, 30, 15, 10, 8, 25, 80}

출력:
총 이익은 100입니다. 가격 2에 매수하여 가격 30에 매도하면 이익은 28입니다.
이후 가격 8에 다시 매수하여 가격 80에 매도하면 이익은 72입니다.
따라서 총 이익은 28 + 72 = 100입니다.

알고리즘

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 시점에서 첫 번째 거래와 두 번째 거래의 이익을 분리해 계산한 뒤, 두 이익을 합산하여 최댓값을 찾는 것입니다.

입력 − 전체 가격 목록, 목록에 담긴 항목의 개수 n

출력 − 최대 이익

알고리즘은 두 단계로 진행됩니다.

1단계: 오른쪽에서 왼쪽으로 순회 — 두 번째 거래의 이익 계산

마지막 날부터 역순으로 순회하면서, 각 날 i에 대해 'i번째 날 또는 그 이후에 매도했을 때 얻을 수 있는 최대 이익'을 profit 배열에 저장합니다. 이를 위해 지금까지 확인한 최고 가격(maxPrice)을 함께 추적합니다.

2단계: 왼쪽에서 오른쪽으로 순회 — 첫 번째 거래의 이익 결합

첫 번째 날부터 차례대로 순회하면서, 각 날 i에 대해 'i번째 날 또는 그 이전에 매수·매도하는 첫 번째 거래의 이익'과 앞서 계산해 둔 두 번째 거래의 이익(profit[i])을 더한 값과 기존 누적 이익을 비교하여 최댓값을 갱신합니다.

findMaxProfit(pricelist, n)

입력 − 모든 가격의 리스트, 리스트 내 항목의 개수

출력 − 최대 이익

Begin
    크기가 n인 profit 배열을 정의하고 0으로 채움
    maxPrice := pricelist[n-1]      //마지막 항목 선택

    for i := n-2 down to 0, do
       if pricelist[i] > maxPrice, then
          maxPrice := pricelist[i]
       profit[i] := profit[i+1]과 (maxPrice – pricelist[i]) 중 큰 값
    done

    minPrice := pricelist[0]      //첫 번째 항목 선택
    for i := 1 to n-1, do
       if pricelist[i] < minPrice, then
          minPrice := pricelist[i]
       profit[i] := profit[i-1]과 (profit[i]+(pricelist[i] - minPrice)) 중 큰 값
    done

    return profit[n-1]
End

C++ 예제 코드

#include<iostream>
using namespace std;

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

int findMaxProfit(int priceList[], int n) {
    int *profit = new int[n];
    for (int i=0; i<n; i++)      //profit 배열을 0으로 초기화
        profit[i] = 0;

    int maxPrice = priceList[n-1];    //가격 리스트의 마지막 요소로 초기화

    for (int i=n-2;i>=0;i--) {
        if (priceList[i] > maxPrice)
            maxPrice = priceList[i];

        profit[i] = max(profit[i+1], maxPrice - priceList[i]);   //maxPrice에 매도할 때의 이익 계산
    }

    int minPrice = priceList[0];      //priceList의 첫 번째 요소를 최솟값으로 설정

    for (int i=1; i<n; i++) {
        if (priceList[i] < minPrice)
            minPrice = priceList[i];

        profit[i] = max(profit[i-1], profit[i] + (priceList[i]- minPrice) );
    }

    int result = profit[n-1];
    return result;
}

int main() {
    int priceList[] = {2, 30, 15, 10, 8, 25, 80};
    int n = 7;
    cout << "Maximum Profit = " << findMaxProfit(priceList, n);
}

실행 결과

Maximum Profit = 100

이 알고리즘은 가격 배열을 앞뒤로 한 번씩 순회하므로 시간 복잡도는 O(n)이며, 길이가 n인 보조 배열 하나만 사용하므로 공간 복잡도 역시 O(n)입니다. 단순히 모든 매수·매도 조합을 탐색하는 브루트 포스 방식(O(n²))보다 훨씬 효율적이라는 점이 이 접근법의 가장 큰 장점입니다.