78. Best Time to Buy and Sell Stock II

🎯 leetcode - 122. Best Time to Buy and Sell Stock II

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 78번 문제

💡 그리디 알고리즘(탐욕 알고리즘)

• 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

📌 날짜

2020.03.09

📌 시도 횟수

1 try

💡 Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                result += prices[i] - prices[i - 1]
        return result

💡 문제 해결 방법

- 이 문제는 "여러번의 거래"가 가능하기 때문에 그리디 알고리즘으로 풀 수 있다.
- 위의 표를 보면 알겠지만, 최저점-최고점을 잇는 1번의 거래보다 매 순간 이전보다 값이 
내렸을 때 사고, 올랐을 때 파는 것을 여러번 반복하는 것이 더 많은 이익을 낼 수 있다.

- 따라서 코드도 이와 같은 단순한 방법으로 구했다.
- 이전의 값보다 현재 값이 올랐을 때, 이전 값과 현재 값의 차이를 result에 더해주었다.

💡 새롭게 알게 된 점

- 그리디 알고리즘의 개념을 새롭게 알게 되었고 
어떤 경우에 그리디 알고리즘이 필요한 지를 새롭게 배웠다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

-