문제 개요
배열 A가 주어졌을 때, A[i]는 i번째 날의 특정 주식 가격을 나타냅니다. 우리는 가능한 한 많은 거래(매수와 매도)를 반복하여 얻을 수 있는 최대 이익(maximum profit)을 구해야 합니다.
단, 한 가지 중요한 제약 조건이 있습니다. 동시에 여러 건의 거래에 참여할 수 없다는 점입니다. 즉, 새 주식을 구매하기 전에 반드시 기존에 보유한 주식을 먼저 팔아야 합니다.
예제
배열이 다음과 같다고 가정해 보겠습니다.
A = [7, 1, 5, 3, 6, 4]
이 경우 결과값은 7입니다. 그 이유를 살펴보면 다음과 같습니다.
- 2일째(index 1)에 가격 1에 매수합니다.
- 3일째(index 2)에 가격 5에 매도하면 이익은 5 − 1 = 4입니다.
- 4일째(index 3)에 가격 3에 다시 매수하고,
- 5일째(index 4)에 가격 6에 매도하면 이익은 6 − 3 = 3입니다.
따라서 총 이익은 4 + 3 = 7이 됩니다.
해결 방법: 그리디(Greedy) 접근법
이 문제는 그리디 알고리즘으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 인접한 두 날의 가격 차이가 양수일 때마다 그 차익을 모두 더한다는 것입니다. 오르는 구간마다 매수 후 매도하는 것과 수학적으로 동일한 결과를 냅니다.
알고리즘 단계
- answer = 0 으로 초기화합니다.
- i를 0부터 n − 1까지 순회합니다 (n은 배열 A의 원소 개수).
- 만약 A[i] − A[i − 1] > 0 이라면:
- answer := answer + (A[i] − A[i − 1])
- 순회가 끝나면 answer를 반환합니다.
구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
ans = 0
for i in range(1, len(prices)):
if prices[i] - prices[i-1] > 0:
ans += (prices[i] - prices[i-1])
return ans
ob1 = Solution()
print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))입력
[7, 2, 5, 8, 6, 3, 1, 4, 5, 4, 7]
출력
13
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 상수 공간만 사용합니다.
이처럼 인접한 날짜 간의 가격 상승분을 모두 누적하는 방식은 여러 번의 거래가 허용되는 주식 매매 문제에서 가장 효율적인 해결책입니다.