[LeetCode] Buy and Sell Crypto

문제 : prices[i]는 i번째날의 neetcoin이다. / 하나의 날을 선택하여 NeetCoin을 구매하고, 그보다 나중의 다른 날을 선택하여 NeetCoin을 팔 수 있다. 얻을 수 있는 최대 이익을 반환한다./ 거래를 하지 않기로 선택할 수도 있으며, 이 경우 이익은 0이 된다.

나의 답안

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        lowest_price = prices[0]
        max_profit = 0 #거래를 하지 않기를 선택할수도 있으니.. 그 경우 이익은 0임.
        for price in prices:
        	# lowest_price를 찾음
            if price < lowest_price:
                lowest_price = price
            # 최대 이익을 찾음
            elif price - lowest_price > max_profit:
                max_profit = price - lowest_price
         # 최대 이익을 반환
        return max_profit 

이 문제를 볼 때 lowest_price를 for문을 통해 돌려서 가져오고, 이 lowest_price를 prices[price]에서 빼면 profit이 나오니 이것도 max_profit을 가져오면 되겠다고 생각했다. 그럼 자연스레 profit이 높은 값만 추출할 것이고, 만약 profit이 없으면 거래하지 않아 원래 정의 되었던 max_profit=0을 반환할 것이다.

이러한 형태의 알고리즘을 Greedy라고 한다고 한다.
그리디 알고리즘(Greedy Algorithm)은 각 단계에서 현재 가장 최적의 선택을 함으로써 전체 문제를 해결하는 알고리즘입니다. 즉, 문제를 해결할 때 매 순간 가장 이득이 되는 선택을 하는 방식입니다. 그리디 알고리즘은 '지금 당장 최선인 선택이 결국 전체 문제에 대한 최선의 해결책으로 이어질 것'이라는 가정 하에 동작합니다.

방식 :

• 현재 상태에서 가능한 선택지를 나열하고, 그중에서 최적의 선택을 고릅니다.
• 그 선택을 확정하고, 문제를 더 작은 부분 문제로 줄입니다.
• 남은 부분 문제에 대해 같은 방식으로 최적의 선택을 반복합니다.
• 최종적으로 문제 전체를 해결하는 최적해를 얻습니다.

NeetCode 답안

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        
        lowest = prices[0]
        for price in prices:
            if price < lowest:
                lowest = price
            res = max(res, price - lowest)
        return res

내 코드와 비슷하지만 내장 함수 max()를 사용함.

max 함수

print(max(1, 5, 3))  # 출력: 5
numbers = [10, 20, 30, 5]
print(max(numbers))  # 출력: 30
# 문자열의 경우: 알파벳 순서에서 가장 뒤에 있는 문자(즉, 가장 큰 문자)를 반환합니다.
print(max('hello'))  # 출력: 'o'