파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다.
#12 주식을 사고팔기 가장 좋은 시점
한 번의 거래로 낼 수 있는 최대 이익을 산출하라
입력
1
| prices = [7, 1, 5, 3, 6, 4]
|
출력
Brute Force 계산
1
2
3
4
5
6
7
| def bruteForce(prices: list) -> int:
max_price = 0
for i, price in enumerate(prices):
for j in range(i, len(prices)):
max_price = max(prices[j] - price, max_price)
return max_price
|
Brute force방식은 처음부터 사고 팔고를 반복해 마지막에 최대 이익을 산출하는 것이다.- 이 문제에서는 타임아웃으로 해결되지 않는다.
내 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def maxProfit(price: list) -> int:
'''
:param price: 주식 가격이 리스트로 주어진다
:return: 최대 이익 반환 :type: int
'''
minStock = 1000
maxStock = 0
nowDay = 0
for days, prices in enumerate(price):
if prices < minStock and nowDay < days:
minStock = prices
if prices > maxStock and nowDay < days:
maxStock = prices
return maxStock - minStock
|
- 최저점에 사서 최고점에 팔아야 하기 때문에 최대 최소값을 구해 차이로 이익을 구한다
- 값을 구할때 날짜가 지나가면 최저점과 최고점의 의미가 없기때문에
if문에 날짜 조건을 걸어준다
저점과 현재 값과의 차이 계산
1
2
3
4
5
6
7
8
9
| def maxProfit_low_now_val(prices: list) -> int:
profit = 0
min_price = sys.maxsize
for price in prices:
min_price = min(min_price, price)
profit = max(profit, price - min_price)
return profit
|
- 그래프로 그려보면 고점과 저점을 확인할 수 있다
- 각 날짜의 주식 가격을 탐색하면서 최솟값과 최댓값을 갱신한다
- 갱신하면서 최대 이익을 계산한다