LeetCode 122 - 주식을 사고팔기 II (Best Time to Buy and Sell Stock II)

문제 설명

정수 배열 prices가 주어집니다. prices[i]는 i번째 날의 주식 가격을 나타냅니다. 원하는 만큼 여러 번 거래(매수와 매도)를 할 수 있지만, 동시에 여러 개의 주식을 보유할 수는 없습니다. 즉, 주식을 산 후에는 반드시 팔아야만 다음 거래를 진행할 수 있습니다.

목표는 최대 이익을 얻는 것입니다.

---

최적 풀이: 그리디(Greedy) 알고리즘

핵심 아이디어

주식 가격이 전날보다 상승했다면 그 차익을 즉시 이익으로 계산하면 됩니다.

이 전략이 유효한 이유는?

• 저점에서 사고 고점에서 파는 전략과, 가격이 상승하는 모든 구간의 차익을 전부 합산하는 전략은 최종적으로 동일한 수익을 주기 때문입니다.

---

풀이 코드 (TypeScript)

function maxProfit(prices: number[]): number {
  let profit = 0

  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1]
    }
  }

  return profit
}

---

동작 원리

1. 첫째 날부터 마지막 날까지 주식 가격 배열을 순회합니다.
2. 오늘의 가격이 어제보다 높으면 그 차액만큼 이익에 더합니다.
3. 모든 날짜를 순회한 뒤 계산된 이익을 반환합니다.

---

시간 및 공간 복잡도

복잡도	값
시간 복잡도	O(n)
공간 복잡도	O(1)

---

이 풀이가 가장 효율적인 이유는?

• 최소, 최대 가격을 따로 관리할 필요 없이 단순 비교만으로 해결 가능
• 재귀나 동적 계획법(DP), 추가 메모리 없이도 한 번의 순회로 완료
• 문제 조건에 가장 적합한 간단한 방법

---

다른 참고 가능한 풀이 방법

1. 재귀 풀이: 가능한 모든 경우를 탐색 (시간 복잡도 O(2^n), 입력이 클수록 비효율적)
2. 재귀 + 메모이제이션 (Top-Down DP): 중복 계산을 방지하여 성능 향상 (시간 복잡도 O(n²))
3. Bottom-Up DP: 메모이제이션과 동일한 원리이나 구현이 더 복잡함

하지만 이 문제에서는 그리디 알고리즘이 가장 간단하면서도 효율적입니다.