[응용 문제] 최대 수익 알고리즘

문제

어떤 주식의 특정 기간 동안의 가격 변화가 주어졌을 때, 그 주식 한 주를 한 번 사고팔아 얻을 수 있는 최대 수익을 계산하라.

 

가격의 최대값과 최솟값을 구한 뒤 계산하는 것으로는 이 문제를 해결할 수 없다. 파는 행위가 사는 행위 후에 발생해야 하기 때문이다.

 

내 풀이

리스트의 첫번째 값을 빼서 구매금액으로 하고, 리스트의 나머지 값 중 최댓값을 판매금액이라고 한다.

판매금액과 구매금액의 차가 현재 최대 수익보다 크면 최대 수익 금액을 갱신한다.

이 반복은 리스트에 자료가 한 개 남으면 종료한다.

def max_benefit(list):
    benefit = 0;

    while len(list) > 1:
        buy = list.pop(0)
        sell = max(list)
        if sell - buy > benefit:
            benefit = sell - buy

    return benefit

문제점은, 원본 자료가 소실된다는 것. 그리고 썩 효율적인 풀이법은 아니라는 것이다.

 

효율적인 풀이

파는 날을 중심으로 생각하여, 현재 금액에서 최소 금액의 차를 수익으로 계산한다. 수익이 최대 수익보다 크면 최대 수익 금액을 갱신하고, 현재 금액이 최소 금액보다 적으면 최소 금액을 갱신한다.

이 행위는 인덱스 1부터, n-1까지 반복한다.

def max_benefit(prices):
    n = len(prices)

    max_profit = 0
    min_price = prices[0]

    for i in range(1, n):
        profit = prices[i] - min_price

        if profit > max_profit:
            max_profit = profit
        if prices[i] < min_price:
            min_price = prices[i]

    return max_profit

이 풀이의 계산복잡도는 \(\mbox{O}(n)\)