문제 개요
배열이 하나 주어지며, i번째 원소는 i번째 날의 특정 주식 가격을 나타냅니다. 우리는 이 배열에서 얻을 수 있는 최대 이익을 계산하는 알고리즘을 설계해야 합니다. 거래 횟수에는 제한이 없어서 주식을 여러 번 사고팔 수 있지만, 다음 두 가지 규칙을 반드시 지켜야 합니다.
- 동시에 여러 거래를 진행할 수 없습니다. 즉, 새로 매수하기 전에 보유 중인 주식을 반드시 먼저 매도해야 합니다.
- 주식을 매도한 직후 다음 날에는 매수할 수 없습니다. 즉, 하루의 쿨다운(휴식) 기간이 필요합니다.
예를 들어 입력이 [1,2,3,0,2]라면 출력은 3이며, 거래 순서는 [매수, 매도, 쿨다운, 매수, 매도]가 됩니다.
접근 방법: 동적 계획법(DP)
이 문제는 동적 계획법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 날짜마다 두 가지 상태를 추적하는 것입니다.
- endWithBuy: 해당 날에 매수 상태로 끝났을 때의 최대 이익
- endWithSell: 해당 날에 매도 상태로 끝났을 때의 최대 이익
쿨다운 규칙을 적용하기 위해 전날의 값(prevBuy, prevSell)을 함께 저장합니다. 알고리즘의 진행 단계는 다음과 같습니다.
- endWithSell := 0, endWithBuy := 음의 무한대, prevBuy := 0, prevSell := 0으로 초기화합니다.
- 배열의 크기만큼 반복합니다.
- prevBuy := endWithBuy
- endWithBuy := max(endWithBuy, prevSell - Arr[i])
- prevSell := endWithSell
- endWithSell := max(endWithSell, prevBuy + Arr[i])
- endWithSell을 반환합니다.
여기서 endWithBuy를 갱신할 때 prevSell(전날 매도 값)을 사용하는 이유는, 매도 후 하루를 쉬어야 한다는 쿨다운 규칙 때문입니다. 이 점화식 덕분에 모든 제약 조건이 자연스럽게 처리됩니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& p) {
int endWithSell = 0;
int endWithBuy = INT_MIN;
int prevBuy = 0, prevSell = 0;
for(int i = 0; i < p.size(); i++){
prevBuy = endWithBuy;
endWithBuy = max(endWithBuy, prevSell - p[i]);
prevSell = endWithSell;
endWithSell = max(endWithSell, prevBuy + p[i]);
}
return endWithSell;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,0,2};
cout << (ob.maxProfit(v));
}
입력
[1,2,3,0,2]
출력
3
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 상태 변수 몇 개만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 입력 크기가 커져도 매우 효율적으로 동작합니다.