Python algorithm 개념 및 실습 - 최대 수익

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

최대 수익 : 어떤 주식에 대해 특정 기간 동안의 가격 변화가 이루어졌을 때 사고 팔아 얻을 수 있는 최대 수익을 계산하는 알고리즘

 

최대수익 (== 최대값, 최소값이 아님)

# 입력 : 주식 가격 변화 리스트

# 출력 : 한 주를 사고 팔아 얻을 수 있는 최대 수익

# 하나하나 비교

def max_profit(stock):

    size = len(stock)

    max_profit = 0

    # 현재 기준 날짜로 전날짜는 판매 못함. 다음날만 판매 가능

    for i in range(size - 1):

        for j in range(i + 1, size):

            profit = stock[j] - stock[i]

            if profit > max_profit:

                max_profit = profit

    return max_profit

# 파는 날을 기준으로 최소값 찾기 앞쪽에 날짜에서 비교

def max_profit2(stock):

    size = len(stock)

    max_profit = 0

    # 첫째 날의 주가를 최솟값으로 시작

    min_price = stock[0]

    for i in range(1, size):

        profit = stock[i] - min_price

        if profit > max_profit:

            max_profit = profit

        if stock[i] < min_price:

            min_price = stock[i]

    return max_profit

if __name__ == "__main__":

    # 날짜별 매매가 나열

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

    print("최대수익", max_profit(stock))

시간 측정 : 데이터 양에 따라 시간차이 비교

# 시간측정

import random

import time

 

def max_profit(stock):

    size = len(stock)

    max_profit = 0

 

    for i in range(size - 1):

        for j in range(i + 1, size):

            profit = stock[j] - stock[i]

            if profit > max_profit:

                max_profit = profit

    return max_profit

 

def max_profit2(stock):

    size = len(stock)

    max_profit = 0

    min_price = stock[0]

    for i in range(1, size):

        profit = stock[i] - min_price

        if profit > max_profit:

            max_profit = profit

        if stock[i] < min_price:

            min_price = stock[i]

    return max_profit

# 시간 측정

def test(n):

    # 주가에 해당하는 숫자 랜덤 생성

    stock = []

    for i in range(0, n):

        stock.append(random.randint(5000, 20000))

    # O(n*n) 알고리즘

    start = time.time()

    mps = max_profit(stock)

    end = time.time()

    time_slow = end - start

    # O() 알고리즘

    start = time.time()

    mpf = max_profit2(stock)

    end = time.time()

    time_fast = end - start

    # 입력크기, 각각 알고리즘이 계산한 최대 수익

    print("크기", "최대수익", "최대수익")

    print(n, mps, mpf)

    diff = 0

    if time_fast > 0:

        diff = time_slow / time_fast

    # 시간 얼마나 걸리는지

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

    print()

if __name__ == "__main__":

    test(100)

    test(10000)