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

Q: 한 번의 거래로 낼 수 있는 최대 이익을 산출하라.

• ex) 입력 : [7,1,5,3,6,4] -> 출력 : 5
  (1일 때 사서 6일 때 팔면 5의 이익을 얻습니다. )

브루트 포스로 계산

• 브루트 포스란 전에도 언급했듯이 , 모든 경우의 수를 다 계산해 보는 풀이를 뜻합니다.
• 떠올리기 쉬운 풀이지만 그만큼 효율성도 떨어지는 풀이입니다.

코드예시

def maxProfit(prices):
    max_price = 0
    
    for i,price in enumerate(prices):
        for j in range(i, len(prices)):
            max_price = max(prices[j] - price , max_price)
            
    return max_price
    
maxProfit([7,1,5,3,6,4])

실행결과

5

• for문을 2번 활용한 풀이입니다.
• 첫 번째 for문에서 처음 제공된 리스트의 값에 따로 인덱스를 부여합니다.
• 두 번째 for문에서는 그 인덱스에 해당하는 값과 그것 보다 뒤에 있는 인덱스들에 해당하는 값들의 차이를 전부 비교한 후 , 가장 큰 값을 max_price에 저장하는 코드입니다.

저점과 현재 값과의 차이 계산

코드예시

import sys

def maxProfit(prices):
    profit = 0
    min_price = sys.maxsize
    
    for price in prices:
        min_price = min(min_price, price)
        profit = max(profit, price - min_price)
    
    return profit
    
maxProfit([7,1,5,3,6,4])

5

• sys.maxsize는 시스템의 가장 큰 값을 뜻하며, 최소값을 경신하며 최신화시키는 문제에 자주 사용하는 함수입니다.
• 그러므로 min_price라는 변수의 값과 prices의 리스트 값을 비교하며 더 작은 수를 min_price에 저장하는 코드입니다.
• profit은 처음에 0이 저장되며, 후에 price - min_price 와 비교되며 더 큰 값을 최신화하며 저장하는 변수입니다.
• 즉, for문이 리스트를 한바퀴 돌면서 그 인덱스까지 나왔던 최소값과 그 인덱스 까지의 가장 큰 차이를 계산하고 profit에 저장하는 함수입니다.

결과 해석

• 기본적으로 for문을 한번만 사용하는 두 번째 방법이 효율적입니다.
• 두 번째 알고리즘은 O(n)의 효율성을 가지고 있고, 첫 번째 풀이는 O(n^2)의 효율성을 가진다. 그러므로 리스트가 커질수록 둘의 효율성 차이는 더 커질 것이다.