오늘은 99클럽 3기 코테 스터디 마지막날입니다. 마지막 문제는 Dynamic programming문제로 마무리가 되네요. 그럼 한 번 살펴볼까요?

---

1. 오늘의 학습 키워드

• Dynamic Programming

---

2. 문제: 121. Best Time to Buy and Sell Stock

• 단계: Easy
• 주제: Array, Dynamic Programming
• 출처: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

---

3. 나의 풀이

문제 이해와 접근 방법

이 문제는 주어진 주식 가격 배열에서 한 번의 거래로 최대 이익을 얻기 위한 방법을 찾는 것입니다. 거래는 하루에 주식을 사고, 이후의 다른 날에 주식을 파는 것으로 구성됩니다. 따라서 목표는 가능한 최소의 가격에 주식을 사고, 이후의 가능한 최대의 가격에 주식을 파는 것입니다.

이 문제는 처음에 배열을 반복하면서 가장 낮은 가격을 기록하고, 그 낮은 가격 이후에 오는 가격 중에서 가장 높은 이익을 계산하는 방식으로 접근할 수 있습니다. 이 방법은 결국 배열을 한 번만 훑으며 답을 찾을 수 있기 때문에 시간 복잡도가 O(n)으로 매우 효율적입니다.

Dynamic Programming으로의 접근

Dynamic Programming (DP)을 사용한 접근은, 문제를 작은 하위 문제들로 나누어 해결하고, 그 결과를 저장해두어 중복 계산을 피하는 방식입니다. 이 문제에서는 주어진 배열의 각 인덱스에서 최대 이익을 갱신해가면서 진행하는 방식이 DP적 접근이라 할 수 있습니다.

DP에서는 다음 두 가지 상태를 추적해야 합니다:

1. 지금까지의 최소 가격 (min_price).
2. 현재 가격에서 최소 가격을 뺀 최대 이익 (max_profit).

이러한 접근이 DP로 분류되는 이유는, 각 단계에서 현재 상태를 이전 상태의 최적 해를 기반으로 갱신하며 진행하기 때문입니다.

코드 설명

아래는 Python을 사용하여 문제를 해결한 코드입니다:

python코드 복사
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """

        max_profit = 0
        min_price = 10 ** 4

        for price in prices:
            min_price = min(min_price, price)  # 현재 가격과 비교하여 최소 가격 갱신
            profit = price - min_price  # 현재 가격에서 최소 가격을 뺀 이익 계산

            max_profit = max(profit, max_profit)  # 최대 이익 갱신

        return max_profit

이 코드에서 max_profit은 최대 이익을 저장하고, min_price는 지금까지의 최소 주가를 저장하는 데 사용됩니다. 배열을 순회하면서 각 주가와 현재 최소 주가를 비교하여 min_price를 갱신하고, 이익을 계산한 뒤 max_profit을 갱신하는 방식으로 최대 이익을 계산합니다.

시간 복잡도와 공간 복잡도

• 시간 복잡도: O(n) 배열을 한 번만 순회하면서 최대 이익을 계산하기 때문에 시간 복잡도는 O(n)입니다.
  
• 공간 복잡도: O(1) 추가적인 배열이나 리스트를 사용하지 않고, 고정된 변수만 사용하므로 공간 복잡도는 O(1)입니다.
  

결과

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/submissions/1375101059

---

마무리

이 문제는 Dynamic Programming의 기초 개념을 활용하여 효율적으로 풀 수 있는 좋은 예제입니다. 문제를 작게 나누어 각 단계에서의 최적해를 찾는 방식이 DP의 핵심이며, 이 문제에서는 배열의 최소값과 최대 이익을 동적으로 갱신하는 방식으로 접근할 수 있었습니다. 최적의 솔루션을 찾기 위해 DP적 사고를 연습할 수 있는 좋은 기회였습니다.

99클럽 스터디의 여정을 마무리하며 돌아보니, 그동안 정말 많은 것을 배울 수 있었습니다. 처음에는 막연하게만 느껴졌던 문제들이 이제는 다양한 접근 방법을 통해 조금씩 풀리는 경험을 할 수 있었습니다. 아쉽게도? 교류를 많이 못했지만, 스터디 취지는 어느 정도의 강제성이 부여되어 매일 1문제를 풀 수 있다는 점에서 얻어가는 것이 있는것 같습니다. 99클럽 스터디 덕분에 Velog를 시작하게 되었고, 단순히 문제를 푸는것에 그치지 않고, 문제를 정리하고 다른 풀이도 고민해보게 되는 계기가 되었습니다.

앞으로도 이번 스터디에서 배운 것들을 바탕으로 더 많은 도전을 이어가고, 배움을 멈추지 않겠습니다. 99클럽 스터디는 끝났지만, 이 경험은 앞으로도 저의 코테 여정에 큰 밑거름이 될 것입니다. 함께 했던 모든 분들께 감사드리며, 앞으로도 각자의 목표를 향해 계속 나아가시길 응원합니다!

➕ 코테 스터디가 끝나도, 여전히 1일 1문제 이상은 풉니다!! (아직 코린이,,,) + TIL