[4.17] 문제 18. 최대 수익 알고리즘

어려움

나중에 복습해야겠다

 

문제 18. 최대 수익 알고리즘

 

입력 : 리스트

출력 : max - min

 

알고리즘 1

 

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 = [1, 2, 3]
print(max_profit(stock))

 

알고리즘 2

파는 날을 중심으로 생각함. 

오..

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 prices[i] < min_price:
      min_price = prices[i]
    if profit > max_profit:
      max_profit = profit
  return max_profit

prices = [10, 20, 100, 200, 1000, 2000]
print(max_profit(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 = [1, 2, 3, 4, 100, 5, 7, 90]
print(max_profit(stock))

 

두 알고리즘 계산 속도 비교

 

import time
import random

#알고리즘 1 : O(n^2)
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


#알고리즘 2 : 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):
  a = []
  for i in range(0, n):
    a.append(random.randint(5000, 20000))
  start = time.time()
  mps = max_profit_slow(a)
  end = time.time()
  time_slow = end - start

  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:
    m = time_slow / time_fast
  print("%d %.5f %.5f %.2f" %(n, time_slow, time_fast, m))

test(100)
test(1000)