주식을 사고팔기 가장 좋은 시점 문제

 

prices 에는 주식의 매일 종가 가격이 있다고 해보자. 가장 이윤을 많이 남기는 발톱 끝에서 사서 정수리에서 파는 경우에 수익이 얼마나 되는지를 찾는 문제이다. 예제 1번이 그 예를 나타낸다. 1일 때 사서 6일 때 파니까 5라는 가장 큰 이윤이 남았다. 예제 2번에는 수익이 전혀 나지 않는 하락장이다.

 

직관적으로 그리디한 브루트 포스 방식으로 생각해보자. [7,1,5,3,6,4] 가 있을 때, 어떤게 오른쪽으로 가면서 가장 이윤을 볼까를 생각해보면, 가능한한 최저점을 찾고 오른쪽으로 가면서 가능한한 최고점을 찾는 방식으로 의식이 흐름이 진행된다.

 

그리디 하게 생각해보면 계산복잡도 $O(n^{2})$ 으로 풀어볼 수 있다. 두 쌍의 차이가 가장 큰 값을 출력하면 된다. 바로 아래와 같이 for 문을 중첩하여 모든 경우의 수를 계산하여 풀 수 있다. 하지만 이렇게 풀면 타임아웃에 걸려버린다.

    def maxProfit(self, prices: List[int]) -> int:
        n=1
        best = 0
        for i in range(len(prices)-1):
            for j in range(n, len(prices)):
                profit = prices[j] - prices[i]
                if profit > best:

                    best = profit
            n += 1
        return best

그렇기 때문에 한번 죽 prices 를 훑고 지나가면서 best 한 경우를 업데이트 하는 방식으로 진행을 해주어야 한다.

1. 가장 저점인 경우 low 를 업데이트 시켜나간다.

2. 저점인 low 와 현재 가격을 비교했을 때 값을 profit이라 한다면 이 profit이 best 한 경우보다 크면 best를 현재의 profit 값으로 업데이트 한다.

3. 2번이 아닌 경우 중에서 만약 저점과 현재의 차이인 profit이 음수가 나오면 더 낮은 저점이 될 수 있으니 profit을 low 포지션으로 변경한다.

 

 

    def maxProfit(self, prices: List[int]) -> int:
        
        low = prices[0]
        best = 0
        for i in prices[1:]:
            profit = i - low
            if profit > best:
                best = profit
            elif profit < 0:
                low = i
        return best

아래와 같은 알고리즘으로 풀면 for 문을 한번만 돌면서 if 문을 가지고 업데이트를 하면서 $O^{n}$ 만에 해결할 수 있다.