UNIT 15 (응용)

최대 수익 알고리즘

문제) 어떤 주식에 대해 특정 기간 동안의 가격 변화가 주어졌을 때, 그 주식 한주를 한 번 사고팔아 얻을 수 있는 최대 수익을 계산하는 알고리즘을 만들어라. (단, 손해일 경우 팔지 않아도 된다. 즉, 최대 수익은 항상 0이상이다.)

방법1

#주어진 주식 가격을 보고 얻을 수 있는 최대 수익을 구하는 알고리즘
#입력 : 주식 가격의 변화 값 (리스트 : prices)
#출력 : 한 주를 한 번 사고팔아 얻을 수 있는 최대 수익 값

#모든 경우를 비교하여 가장 큰 값 찾기

def max_profit(prices):
    n = len(prices)
    max_profit = 0

    for i in range(0, n - 1):
        for j in range(i + 1, n):
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit

    return max_profit


stock = [10300, 9600, 9800, 8200, 7800, 8300, 9500, 9800, 10200, 9500]
print(max_profit(stock))

#비교 횟수 : n(n+1)/2
#계산 복잡도 : O(n*n)

방법2

#주어진 주식 가격을 보고 얻을 수 있는 최대 수익을 구하는 알고리즘
#입력 : 주식 가격의 변화 값 (리스트 : prices)
#출력 : 한 주를 한 번 사고팔아 얻을 수 있는 최대 수익 값

#판 가격을 중심으로 산 가격 최소값 찾기

def max_profit(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


stock = [10300, 9600, 9800, 8200, 7800, 8300, 9500, 9800, 10200, 9500]
print(max_profit(stock))

#계산 복잡도 : O(n)

최대 수익을 구하는 두 알고리즘의 계산 속도 비교하기

#최대 수익 문제를 푸는 두 알고리즘의 계산 속도 비교하기
#최대 수익 문제를 O(n*n)과 O(n)으로 푸는 알고리즘을 각각 수행하여
#걸린 시간을 출력/비교함

import time
import random

def max_profit_slow(prices):
    n = len(prices)
    max_profit = 0

    for i in range(0, n - 1):
        for j in range(i + 1, n):
            profit = prices[j] - prices[i]
            if profit > max_profit:
                max_profit = profit
    return max_profit


def max_profit_fast(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


def test(n):  # n = 주가 개수
    a = []
    for i in range(0, n):
        a.append(random.randint(5000, 20000))  # 주가로 사용

    # 느린 O(n*n) 알고리즘 테스트
    start = time.time()
    mps = max_profit_slow(a)
    end = time.time()
    time_slow = end - start

    # 빠른 O(n) 알고리즘 테스트
    start = time.time()
    mpf = max_profit_fast(a)
    end = time.time()
    time_fast = end - start

    # 결과 출력 : 계산 결과 (mps와 mpf가 같아야 함)
    print(n, mps, mpf)

    # 결과 출력 : 계산 시간 비교
    m = 0
    if time_fast > 0:
        m = time_slow / time_fast

    print("%d %.5f %.5f %.2f" % (n, time_slow, time_fast, m))

test(100)
test(10000)
test(100000)

출처

모두의 파이썬&알고리즘 합본호 / 이승찬 / 길벗 / 2018-12-10