파이썬 주식 수익 알고리즘 #15

파이썬 주식 수익 알고리즘 #15

#지난 포스팅 보러 가기#

2020/03/24 - [DB엔지니어가 공부하는 python] - 파이썬 모델링 그래프 알고리즘 미로 찾기 #14

파이썬 모델링 그래프 알고리즘 미로 찾기 #14

 

 

안녕하세요.

 

이번 알고리즘 시간은 파이썬 알고리즘 마지막 시간입니다.

 

그동안 부족한 내용 잘 봐주셔서 감사의 말씀을 이 자리를 빌려 전해드립니다.

 

마지막인 이번 시간 다뤄볼 알고리즘은 주식 최대 수익 알고리즘입니다.

◆문제 개요

어떤 주식이 특정 기간 동안 가격 변화가 일어났을 때, 주식을 한번 사고, 팔았을 때 얻을 수 있는 최대 수익을 계산하는 알고리즘을 만들어 보겠습니다.

 

어떤 주식 종목의 가격이 아래 표와 같이 매일 변화했다고 가정해 봅니다.

날짜	주가 (\)
12/1	10,300
12/2	9,600
12/3	9,800
12/4	8,200
12/5	7,800
12/8	8,300
12/9	9,500
12/10	9,800
12/11	10,200
12/12	9,500

위 주식을 한 주 사서 팔아 얻을 수 있는 최대 수익은 얼마일까요?

단, 손해는 없다는 가정을 한다면 최대 수익은 항상 0 이상의 값을 기대할 수 있습니다.

 

◆문제 분석

주식을 거래하여 수익을 낼 수 있는 가장 좋은 방법은 가장 쌀 때 사서 가장 비쌀 때 파는 방법입니다. 그래서 얼핏 생각하기에 어떤 기간 내 최댓값의 주가에서 최솟값을 주가를 빼면 그것이 가장 큰 수익을 얻을 것이라는 착각에 빠지기 쉽습니다.

 

위 표를 대상으로 가정해 보면 주가가 가장 비쌀 때는 12/1일의 10,300원입니다. 그리고 가장 주가가 싼 날은 12월 5일의 7,800원입니다.

 

하지만 주식이란 걸 12월 5일에 사서 12월 1일에 팔 수는 없죠.

 

그렇다면 이젠 어떤 방법으로 문제를 풀어봐야 할지 조금 감이 잡히나요?

 

위 표의 정보를 토대로 stock이라는 리스트를 만들어 보겠습니다.

stock = [10300,9600,9800,8200,7800,8300,9500,9800,10200,9500]

◆문제 풀이 방법 1

일단 생각할 수 있는 모든 경우를 가정해서 풀어 보겠습니다.

첫날 사서 둘째 날, 셋째 날, 넷째 날... 파는 경우, 둘째날 사서 셋째날, 넷째날... 마지막날 파는 경우. 이런 식으로 모든 경우를 비교해서 가장 큰 수익이 나는 경우를 찾으면 최대 수익을 계산할 수 있을 겁니다.

 

이 경우에 계산 횟수는 n(n-1)/2 가 되고 계산 복잡도로 표현한다면 O(n²) 이 됩니다.

 

◆문제 풀이 방법 1 소스

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

def max_profit(prices):
    n = len(prices)
    max_profit = 0  # 최대 수익은 항상 0 이상의 값

    for i in range(0, n - 1):
        for j in range(i + 1, n):
            profit = prices[j] - prices[i]  # i날에 사서 j날에 팔았을 때 얻을 수 있는 수익
            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))

◆문제 풀이 방법 1 결과

위 소스의 결과는 2,400이 나옵니다.

12/5일 7,800원에 주식을 사서 12/11일 10,200원에 다시 팔았을 때가 되는 것 이죠.

 

◆문제 풀이 방법 2

모든 경우를 계산하고 비교하는 1번의 방식은 직관적이긴 하지만 불필요한 계산을 많이 한다는 단점이 있습니다. 조금 생각을 바꿔서 접근해 보겠습니다.

 

1번 풀이 방법이 사는 날을 기준으로 한다면 이번엔 파는 날을 기준으로 생각해 보도록 하겠습니다.

 

예를 들어서 12월 10일에 9,800원을 받고 주식을 판다고 했을 때 가장 큰 수익이 나는 주식 사는 날은 언제 일지를 생각하는 것 이죠. 이 알고리즘을 정리해 보면 아래와 같습니다.

 

1. 최대 수익을 저장하는 변수를 만든다.

2. 최저 주가를 저장하는 변수를 만들고, 첫째 날 주가를 기록한다.

3. 둘째 날부터 마지막 날까지의 주가를 반복한다.

4. 반복하는 동안 그날 주가에서 최저 주가를 뺀 값이 현재 최대 수익보다 크다면 그 값으로 업데이트한다.

5. 그날 주가가 최저 주가보다 낮으면 최저 주가를 그날의 주가로 업데이트한다.

6. 처리할 날이 남았으면 4번으로 가서 반복하고, 다 마쳤으면 최대 수익에 저장된 값을 결괏값으로 출력하고 종료한다.

◆문제 풀이 방법 2 소스

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

def max_profit(prices):
    n = len(prices)
    max_profit = 0         # 최대 수익은 항상 0 이상의 값
    min_price = prices[0]  # 첫째 날의 주가를 주가의 최솟값으로 기억

    for i in range(1, n):  # 1부터 n-1까지 반복
        profit = prices[i] - min_price  # 지금까지의 최솟값에 주식을 사서 i날에 팔 때의 수익
        if profit > max_profit:   # 이 수익이 지금까지 최대 수익보다 크면 값을 고침
            max_profit = profit
        if prices[i] < min_price: # i날 주가가 최솟값보다 작으면 값을 고침
            min_price = prices[i]

    return max_profit

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

◆문제 풀이 방법 2 결과

위 소스의 결과 역시 1과 같이 2,400이 나옵니다.

 

◆두 알고리즘 분석

문제 풀이 방법만 살펴봐도 첫 번째 알고리즘보다 두 번째 알고리즘이 더 효율적이라는 것을 알 수 있습니다.

 

각각의 계산 복잡도는 어떻게 될까요? 모든 경우의 수를 다 비교하는 문제 풀이 1번의 경우 위에서도 말했지만 O(n²)의 계산 복잡도를 가지고 있습니다.

 

하지만, 두번째 알고리즘의 경우 최대 리스트를 한 번만 탐색하면서 최대 수익을 찾는 방식인데, 이 경우 계산 복잡도는 O(n)으로 표현할 수 있습니다.

 

더 많은 주가를, 더 많이 비교하면 할수록 그 차이가 극명하게 나타나게 될 것입니다.

 

실제로 두 알고리즘의 수행 속도를 비교하는 소스를 작성해보았습니다.

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

import time     # 시간 측정을 위한 time 모듈
import random  # 테스트 주가 생성을 위한 random 모듈

# 최대 수익: 느린 O(n*n) 알고리즘
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

# 최대 수익: 빠른 O(n) 알고리즘
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):
    # 테스트 자료 만들기(5000부터 20000까지의 난수를 주가로 사용)
    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   # 두 시각을 빼면 계산에 걸린 시간
    # 결과 출력: 계산 결과
    print(n, mps, mpf)  # 입력 크기, 각각 알고리즘이 계산한 최대 수익 값(같아야 함)
    # 결과 출력: 계산 시간 비교
    m = 0  # 느린 알고리즘과 빠른 알고리즘의 수행 시간 비율을 저장할 변수
    if time_fast > 0:  # 컴퓨터 환경에 따라 빠른 알고리즘 시간이 0으로 측정될 수 있음(이럴 때는 0을 출력)
        m = time_slow / time_fast  # 느린 알고리즘 시간 / 빠른 알고리즘 시간
    # 입력 크기, 느린 알고리즘 수행 시간, 빠른 알고리즘 수행 시간, 느린 알고리즘 시간 / 빠른 알고리즘 시간
    # %d는 정수 출력, %.5f는 소수점 다섯 자리까지 출력을 의미
    print("%d %.5f %.5f %.2f" % (n, time_slow, time_fast, m))

test(100)
test(10000)
#test(100000)  # 수행 시간이 오래 걸리므로 일단 주석 처리

자료에 따르면 위 두 알고리즘의 수행 속도 비교 결과는 아래 표와 같이 나타난다고 합니다.

입력 크기(n)	최대 수익	느린 알고리즘 수행 시간 (초)	빠른 알고리즘 수행 시간 (초)	느린 알고리즘 시간 / 빠른 알고리즘 시간
100	14658	0.00061	0.00002	40.87
10000	14996	6.09124	0.00167	3653.97
100000	15000	819.66065	0.01953	41969.70

1만 개의 샘플만 돌려도 느린 알고리즘은 빠른 알고리즘에 비해 약 3653배 정도 더 오래 걸리는 것으로 나타났습니다.

빅데이터 시대에 1만 개보다 훨씬 많은 샘플들을 비교하는 로직에서 알고리즘만 잘 짜더라도 이렇게나 좋은 효율을 가지고 올 수 있습니다.

 

알고리즘의 중요성을 이젠 아시겠죠? ㅎㅎ

 

이상으로 파이썬으로 공부하는 알고리즘 시간을 마치겠습니다.

 

감사합니다.

 

# 파이썬으로 배우는 알고리즘 콘텐츠는 <모두의 파이썬 X알고리즘, 길벗>을 참고로 작성하는 포스팅입니다. 물론 협찬은 없습니다.ㅎㅎ

https://book.naver.com/bookdb/book_detail.nhn?bid=14341699

 

by.sTricky