문제 개요
시간 순서대로 정렬된 어떤 회사의 주가 목록과, 한 번의 매도 거래당 부과되는 거래 수수료가 주어졌다고 가정해 보겠습니다. 우리가 구해야 할 것은 해당 주식을 원하는 만큼 여러 번 사고팔았을 때 얻을 수 있는 최대 이익입니다. 단, 주식을 팔기 위해서는 반드시 먼저 매수해야 한다는 조건이 있습니다.
예를 들어 입력이 prices = [2, 10, 4, 8], fee = 3이라고 해봅시다. 이 경우 출력은 6이 됩니다. 가격이 2일 때 매수하여 10일 때 매도하면 수수료 3을 제외한 이익은 5입니다. 이후 다시 가격이 4일 때 매수하여 8일 때 매도하면 수수료 3을 제외한 이익은 1이 되고, 따라서 총 이익은 5 + 1 = 6입니다.
해결 접근 방법
이 문제는 재귀(recursion)를 활용해 해결할 수 있습니다. 각 시점에서 "주식을 보유하고 있는지 아닌지"를 나타내는 플래그(flag) 변수를 사용하는 것이 핵심입니다. 해결 과정은 다음과 같습니다.
- n := prices 배열의 크기
- recur() 함수를 정의합니다. 이 함수는 i := 0(현재 인덱스)과 flag := 0(보유 여부)을 인자로 받습니다.
- i가 n과 같으면(모든 날짜를 확인했다면) 0을 반환합니다.
- flag가 false(주식 미보유)라면, max(recur(i + 1, 1) - prices[i], recur(i + 1, 0))을 반환합니다. 즉, "오늘 매수하는 경우"와 "매수하지 않고 넘어가는 경우" 중 더 큰 값을 선택합니다.
- flag가 true(주식 보유)라면, max(recur(i + 1, 1), recur(i + 1, 0) + prices[i] - fee)를 반환합니다. 즉, "계속 보유하는 경우"와 "오늘 매도하는 경우(수수료 차감)" 중 더 큰 값을 선택합니다.
- 메인 메서드에서 recur()를 호출합니다.
파이썬 구현 예제
class Solution: def solve(self, prices, fee): n = len(prices) def recur(i=0, flag=0): if i == n: return 0 if not flag: return max(recur(i + 1, 1) - prices[i], recur(i + 1, 0)) return max(recur(i + 1, 1), recur(i + 1, 0) + prices[i] - fee) return recur() ob = Solution() prices = [2, 10, 4, 8] fee = 3 print(ob.solve(prices, fee))
입력 및 출력
입력
[2, 10, 4, 8], 3
출력
6
코드 동작 원리
recur() 함수는 두 가지 상태를 기준으로 모든 경우를 탐색합니다.
- flag = 0 (미보유 상태): 현재 가격에 주식을 사거나, 아무것도 하지 않고 다음 날로 넘어갈 수 있습니다. 매수하면 그날의 가격만큼 비용이 발생하므로 -prices[i]가 반영됩니다.
- flag = 1 (보유 상태): 주식을 계속 들고 있거나, 오늘 팔아버릴 수 있습니다. 매도하면 현재 가격을 받지만 수수료 fee를 지불해야 하므로 +prices[i] - fee가 반영됩니다.
이렇게 가능한 모든 매수·매도 조합을 탐색하면서 얻을 수 있는 최대 이익이 자연스럽게 도출됩니다.
복잡도 및 최적화 참고 사항
위 재귀 구현은 각 단계마다 두 가지 선택지를 탐색하므로 시간 복잡도는 O(2^n)입니다. 입력 크기가 커지면 실행 시간이 급격히 늘어나므로, 실전에서는 메모이제이션(memoization)을 적용하거나 동적 계획법(DP)으로 전환하는 것이 좋습니다. DP로 풀 경우 각 날짜별 '보유'와 '미보유' 상태의 최대 이익만 저장하면 되므로 O(n) 시간 안에 효율적으로 해결할 수 있습니다.