문제 설명
주식 가격이 담긴 배열이 주어졌을 때, 배열의 i번째 요소는 i일째 되는 날의 주식 가격을 의미합니다. 이때 최대 두 번의 거래만 허용되며, 얻을 수 있는 최대 이익을 구하는 알고리즘을 설계해야 합니다.
예를 들어, 주어진 가격 배열이 [3,3,5,0,1,3,1,4]라면 결과는 6이 됩니다. 그 이유는 다음과 같습니다.
- 4일째 되는 날 가격 0에 매수하고, 6일째 되는 날 가격 3에 매도 → 이익 3 − 0 = 3
- 7일째 되는 날 가격 1에 매수하고, 8일째 되는 날 가격 4에 매도 → 이익 4 − 1 = 3
두 거래의 이익을 합하면 3 + 3 = 6으로, 이것이 가능한 최대 이익입니다.
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 날짜를 기준으로 거래를 두 구간으로 나누는 것입니다.
- 첫 번째 단계 (왼쪽 → 오른쪽 순회): 각 날짜 i까지 한 번의 거래로 얻을 수 있는 최대 이익을 dp 배열에 저장합니다. 이때 지금까지의 최저 가격(xmin)을 추적하며, 현재 가격에서 최저 가격을 뺀 값과 기존 이익 중 큰 값을 선택합니다.
- 두 번째 단계 (오른쪽 → 왼쪽 순회): 각 날짜 i 이후의 최대 가격(xmax)을 미리 계산해 둡니다.
- 세 번째 단계 (거래 분할): 오른쪽에서 왼쪽으로 순회하면서, i+1일 이후에 두 번째 거래로 얻을 수 있는 최대 이익(tempp)을 갱신합니다. 그런 다음 첫 번째 거래의 이익(dp[i])과 두 번째 거래의 이익을 합산하여 전체 최댓값을 구합니다.
이 방식의 시간 복잡도는 O(n), 공간 복잡도는 O(n)으로, 배열을 여러 번 순회하지만 각 순회가 선형 시간에 처리되므로 매우 효율적입니다.
구현 예제
다음은 위 접근 방식을 파이썬으로 구현한 코드입니다.
class Solution(object):
def maxProfit(self, p):
if not p:
return 0
n = len(p)
dp = [0 for i in range(n)]
ans = 0
xmin = p[0]
for i in range(1, n):
xmin = min(xmin, p[i])
dp[i] = max(dp[i], p[i] - xmin)
ans = max(ans, dp[i])
xmax = [0 for i in range(n)]
xmax[-1] = p[-1]
tempp = 0
for i in range(n-2, -1, -1):
xmax[i] = max(xmax[i+1], p[i])
xmin = [p[-1], n]
for i in range(n-2, -1, -1):
tempp = max(tempp, xmax[i+1] - p[i+1])
ans = max(ans, dp[i] + tempp)
return ans
ob = Solution()
print(ob.maxProfit([3,3,5,0,1,3,1,4]))입력
[3,3,5,0,1,3,1,4]
출력
6
마무리
이 문제의 핵심은 각 날짜를 기준으로 앞쪽 거래와 뒤쪽 거래를 분리하여 생각하는 것입니다. 왼쪽에서 오른쪽으로 한 번, 오른쪽에서 왼쪽으로 한 번 순회하면서 두 구간의 최대 이익을 각각 계산한 뒤 결합하면, 최대 두 번의 거래로 얻을 수 있는 최대 이익을 효율적으로 찾을 수 있습니다.