[알고리즘] 코드잇 - 삼송전자 주식 분석(Python)

설명

태호는주식 분석이 취미입니다.

 

요즘 제일 핫한 종목은 삼송전자인데요. 삼송전자의 주식을 딱 한 번 사고 팔았다면 최대 얼마의수익이 가능했을지 궁금합니다. 그것을 계산해 주는 O(n)함수 max_profit()을 작성하세요.

 

max_profit()은 파라미터로 일별 주식 가격이 들어 있는 리스트 stock_prices를 받고 최대 수익을 리턴합니다. 주식은 딱 한번만 사고 한 번만 팝니다. 그리고 사는 당일에 팔 수는 없습니다.

 

하나의 예시로, 지난 6일간 삼송전자의주식 가격이 이렇다고 가정합시다.

max_profit([7, 1, 5, 3, 6, 4])

이 기간 동안 낼 수 있는 최대 수익은 얼마일까요? 둘째 날 1에 사서 다섯째 날 6에 팔면 총 5의 수익이 생깁니다.

 

또 다른 예시를 봅시다.

max_profit([7, 6, 4, 3, 1])

이 기간 동안 가능한 최대 수익은 얼마일까요? 이번에는 주식이 계속 떨어지기만 하네요. 하지만 꼭 한 번은 사고 팔아야 하기 때문에, 첫날 7에 사고 둘째 날 6에 팔아서 나오는 -1이 최대 수익입니다.

 

힌트1

우선 간단하게 Brute Force 방식부터 살펴봅시다.

 

한 번 사고 한 번 파는 모든 조합을 보고, 그 중에서 가장 큰 수익을 고르면 되겠죠.

def max_profit(stock_list):
    # 현재까지의 최대 수익
    max_profit_so_far = stock_list[1] - stock_list[0]

    # 한 번 사고 파는 모든 조합을 본다
    for i in range(len(stock_list) - 1):
        for j in range(i + 1, len(stock_list)):
            # i에서 사고 j에 파는 것이 현재까지의 최대 수익이라면 max_so_far을 바꾼다
            max_profit_so_far = max(max_profit_so_far, stock_list[j] - stock_list[i])

    return max_profit_so_far

이렇게 하면 확실히 답을 구할 수 있지만 상당히 비효율적입니다. stock_list의 길이를 n이라고하면, 시간 복잡도는 O(n^2)이죠.

 

더 효율적으로, O(n)으로 문제를 해결할 수 있는데요. 어떻게 할 수 있을지 고민해 보세요.

 

힌트2

가장 낮은 가격에 사서 가장 높은 가격에 팔면 최대 수익이 날 것같습니다.

예시를 볼게요.

max_profit([7, 6, 4, 3, 1])

리스트 전체에서 가장 낮은 가격은 1이고 가장 높은 가격은 7 입니다. 그런데 문제가 있네요. 시간 순서상 1에 사서 7 에 파는 것은 불가능 합니다.

 

결국 리스트 전체의 최솟값을 찾는 것은 큰 도움이 안됩니다. 파는 날을 기준으로, 지난 날들 중에서 최솟 값을 알아야 하는거죠.

 

힌트3

기존의 Brute Force 솔루션에서는 max_profti_so_far라는 변수로 현재까지의 최대 수익을 보관하고 있는데요. 추가로 또 다른 변수를 이용해서 어떤 값을 보관하면 좋을 것 같습니다. 그게 어떤 값일까요?

 

답안

def max_profit(stock_list):
    # 현재까지의 최대 수익
    max_profit_so_far = stock_list[1] - stock_list[0]

    # 현재까지의 최소 주식 가격
    min_so_far = min(stock_list[0], stock_list[1])

    # 주식 가격을 하나씩 확인한다
    for i in range(2, len(stock_list)):
        # 현재 파는 것이 좋은지 확인한다
        max_profit_so_far = max(max_profit_so_far, stock_list[i] - min_so_far)

        # 현재 주식 가격이 최솟값인지 확인한다
        min_so_far = min(min_so_far, stock_list[i])

    return max_profit_so_far


# 테스트 코드
print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))
print(max_profit([11, 13, 9, 13, 20, 14, 19, 12, 19, 13]))
print(max_profit([12, 4, 11, 18, 17, 19, 1, 19, 14, 13, 7, 15, 10, 1, 3, 6]))