시간순으로 정렬된 어떤 회사의 주가 리스트가 있다고 가정해 봅시다. 이때 해당 주식을 원하는 만큼 여러 번 사고팔았을 때 얻을 수 있는 최대 수익을 구하는 것이 목표입니다. 단, 매도하기 전에 반드시 먼저 매수해야 한다는 조건을 기억해야 합니다.
예를 들어 입력이 prices = [10, 50, 30, 40, 60]이라면 출력은 70이 됩니다. 10에 매수해서 50에 팔고, 다시 30에 매수해서 60에 팔면 되기 때문입니다.
문제 해결 접근 방법
이 문제는 탐욕 알고리즘(Greedy Algorithm)으로 간단하게 해결할 수 있습니다. 핵심 아이디어는 인접한 두 날의 가격을 비교하여 가격이 올랐다면 그 차익을 모두 더하는 것입니다. 연속된 상승 구간을 하나의 거래로 묶어도 결국 각 상승분의 합과 같기 때문에, 모든 양의 가격 차이를 누적하면 곧 최대 수익이 됩니다.
구체적인 단계는 다음과 같습니다.
- prev_price를 무한대(∞)로 초기화합니다.
- profit을 0으로 초기화합니다.
- prices의 각 가격 p에 대해 다음을 반복합니다.
- p가 prev_price보다 크면, profit에 (p − prev_price)를 더합니다.
- 매 반복마다 prev_price를 현재 가격 p로 갱신합니다.
- 반복이 끝나면 profit을 반환합니다.
예제 코드
class Solution:
def solve(self, prices):
prev_price = float("inf")
profit = 0
for p in prices:
if p > prev_price:
profit += p - prev_price
prev_price = p
return profit
ob = Solution()
print(ob.solve([10, 50, 30, 40, 60]))입력
[10, 50, 30, 40, 60]
출력
70
동작 과정 살펴보기
- 첫째 날(10): 비교 대상이 없으므로 prev_price만 10으로 갱신됩니다.
- 둘째 날(50): 50 > 10 → 수익 40을 누적합니다.
- 셋째 날(30): 가격이 하락했으므로 수익에 반영하지 않습니다.
- 넷째 날(40): 40 > 30 → 수익 10을 추가합니다. (누적 50)
- 다섯째 날(60): 60 > 40 → 수익 20을 추가합니다. (누적 70)
이처럼 하루 전 가격보다 오른 날의 차익만 모두 더하면, 여러 번의 매매로 얻을 수 있는 최대 수익인 70을 손쉽게 구할 수 있습니다.