[LeetCode 122] Best Time to Buy and Sell Stock II - Greedy & DP 풀이

[LeetCode] Best Time to Buy and Sell Stock II - Greedy & DP 풀이

문제 설명

LeetCode의 "Best Time to Buy and Sell Stock II" 문제는 여러 번 매매하여 최대 이익을 얻는 문제입니다.

• prices[i]는 i번째 날의 주가를 나타냅니다.
• 여러 번 매매 가능하지만, 보유 중에는 추가 매수가 불가능합니다. (즉, 한 번 매수하면 반드시 매도 후 다시 매수 가능)
• 최대 이익을 구하는 것이 목표입니다.

---

처음 문제를 풀었을 때의 생각

처음에는 **"최적의 매수-매도 시점을 찾는 문제"**라고 생각했어요.
하지만, **"가격이 오를 때마다 매수-매도를 반복하면 최대 이익을 얻을 수 있다"**는 점을 깨달았습니다.
이 접근법은 탐욕법(Greedy Algorithm)으로 해결 가능하며, O(N) 시간 복잡도로 최적의 결과를 얻을 수 있습니다.

또한, 동적 계획법(DP)으로도 해결 가능하지만, 탐욕법이 훨씬 직관적이고 효과적인 방식이었습니다.

---

탐욕법(Greedy) 풀이

✅ 핵심 아이디어

• 가격이 오를 때마다 이익을 취하는 것이 최적의 전략입니다.
• 즉, 모든 상승 구간에서 매수-매도를 반복하면 최대 이익을 얻을 수 있음.

export function maxProfit2(prices: number[]): number {
  let sum = 0;
  for (let index = 1; index < prices.length; index++) {
    if (prices[index] > prices[index - 1]) {
      sum += prices[index] - prices[index - 1];
    }
  }
  return sum;
}

📌 실행 예제 분석

prices = [7,1,5,3,6,4]

날짜 주가 수익 계산 누적 이익

1일차	7	-	0
2일차	1	-	0
3일차	5	5-1 = 4	4
4일차	3	-	4
5일차	6	6-3 = 3	7
6일차	4	-	7

✅ 최종 이익: 7

📌 시간 및 공간 복잡도

• 시간 복잡도: O(N) → 배열을 한 번 순회
• 공간 복잡도: O(1) → 추가적인 공간 사용 없음

---

동적 계획법(DP) 풀이

✅ DP 접근법의 핵심 개념

이 문제에서 우리는 매일 두 가지 선택을 할 수 있습니다.

1. 주식을 보유한 상태 (hold)
   • hold[i] = i번째 날까지의 최대 이익 (주식을 보유한 상태)
   • hold[i] = max(hold[i-1], sell[i-1] - prices[i])
2. 주식을 보유하지 않은 상태 (sell)
   • sell[i] = i번째 날까지의 최대 이익 (주식을 보유하지 않은 상태)
   • sell[i] = max(sell[i-1], hold[i-1] + prices[i])

✅ 결국, sell[n-1] (마지막 날 주식을 보유하지 않은 상태의 최대 이익)이 정답입니다.

export function maxProfitDP(prices: number[]): number {
  if (prices.length === 0) return 0;

  let sell = 0; // 주식을 보유하지 않은 상태의 최대 이익
  let hold = -prices[0]; // 주식을 보유한 상태의 최대 이익 (초기값: 첫날 주식을 샀을 때)

  for (let i = 1; i < prices.length; i++) {
    sell = Math.max(sell, hold + prices[i]); // 현재 주식을 팔거나, 팔지 않는 경우 중 최댓값
    hold = Math.max(hold, sell - prices[i]); // 현재 주식을 사거나, 기존 주식을 유지하는 경우 중 최댓값
  }

  return sell;
}

📌 시간 및 공간 복잡도

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

---

탐욕법(Greedy) vs. 동적 계획법(DP) 비교

방법 시간 복잡도 공간 복잡도 특징

탐욕법 (Greedy)	O(N)	O(1)	가장 직관적이고 쉬운 방법
동적 계획법 (DP)	O(N)	O(1)	상태를 명확하게 나누지만, 불필요한 계산이 많음

✅ 이 문제는 탐욕법(Greedy)이 최적의 해결법이며, DP보다 직관적이고 효율적입니다.

---

Jest 테스트 코드

describe("Best Time to Buy and Sell Stock II", () => {
  it("calculates max profit for increasing prices", () => {
    expect(maxProfit2([1,2,3,4,5])).toEqual(4);
  });

  it("calculates max profit for fluctuating prices", () => {
    expect(maxProfit2([7,1,5,3,6,4])).toEqual(7);
  });

  it("returns 0 for decreasing prices", () => {
    expect(maxProfit2([7,6,5,4,3,2,1])).toEqual(0);
  });
});

✅ 다양한 입력 케이스를 검증하여 정확성 확보 ✅ 가격이 오르지 않는 경우([7,6,5,4,3,2,1])도 테스트하여 0 반환 확인

---

📌 최종 정리

• 탐욕법(Greedy)이 가장 적절한 해결법 (O(N))
• DP도 사용 가능하지만, 탐욕법이 훨씬 직관적이고 효율적
• 테스트 케이스를 추가하여 다양한 상황에서 올바른 결과 확인 가능

💡 이제 비슷한 문제를 만나면 "탐욕법"을 우선 고려해 보세요! 🚀