121. 주식을 사고팔기 가장 좋은 시점

121. Best Time to Buy and Sell Stock
Easy
파이썬 알고리즘 인터뷰 195p

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.

♬idea

• 사고 파는 순서가 있기 때문에 최솟값과 최댓값의 범위 생각해주어야 함
• 차익이 최대화 되는 값을 구해야 함

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = []
        
        # 가격 차 최댓값 리스트 생성
        for i in prices:
            max = 0
            for j in prices[i:]:
                value = prices[j] - prices[i]
                if max < value:
                    max = value
            profit.append(max)
            
        return sorted(profit, reverse=True)[0]

첫번째 시도는 에러가 났다

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize
        
        # 최솟값과 최댓값을 계속 갱신
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)
            
        return profit

교재 코드를 보고 느낀점 : 컴퓨터가 나보다 계산을 훨씬 잘하는데 왜 내가 다 나눠주려고 했을까.. 내장함수 사용하자

 

브루트 포스 알고리즘

교재에서 내가 풀이한 첫번째 방식을 브루트 포스 알고리즘이라고 지칭해서 찾아보았다.

Brute:난폭한 + Force:힘 = 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져오는 방법

 

전체 탐색에는 주로 순차 탐색, 깊이 우선 탐색(DFS), 너비우선 탐색(BFS) 이 사용된다. 브루트 포스 알고리즘은 자원과 복잡도 관련 단점이 있다.