- 한 번의 거래로 낼 수 있는 최대 이익을 산출하라
1. 브루트 포스로 계산
class Solution:
def maxProfit(self, prices: List[int]) -> 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
- 하지만 이 방식은 타임 아웃으로 풀리지 않는다.
2. 저점과 현재 값과의 차이 계산
-
다음과 같은 시각화는 기술 통계학(Descriptive Statistics)이라고 일컬으며 통계학에서도 매우 중요한 연구 분야 중 하나이기도 하다.
-
인덱스 1은 저점을 가리키고 있고, 인덱스 4는 고점을 가리킨다.
-
현재 값을 가리키는 포인터가 우측으로 이동하면서 이전 상태의 저점을 기준으로 가격차이를 계산하고, 만약 클 경우 최댓값을 계속 교체해나가는 형태로 O(n) 풀이가 가능하다.
class Solution:
def maxProfit(self, prices: List[int]) -> 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
-
최댓값이 되어야 할 profit 변수와 최솟값이 되어야 할 min_price 변수의 초깃값은 이처럼 각각 시스템의 가장 작은 값, 가장 큰 값으로 정한다. 즉, 최댓값 변수는 최솟값으로 최솟값 변수는 최댓값으로 정한다.
- 그래야 어떤 값이 들어오든 바로 교체될 수 있기 때문이다.
- 만약, None으로 잡아두게 되면 비교 시 타입에러(TypeError)가 발생할 수 있기 때문에 이처럼 최솟값, 최댓값은 시스템의 최댓값, 최솟값으로 설정하는게 편하다.
-
최대 이익 profit이 나중에 최종 결과로 리턴되는데, 입력값이 []인 경우, 즉 빈 배열인 경우에는 자칫 -sys.maxsize가 리턴될 수 있기 때문에 여기서는 0으로 설정한다.
- 최댓값은 0보다는 항상 커야하기 때문이다.
-
최저점과 비교해 더 작을 경우 최솟값을 갱신하고, 현재 값과 최솟값과의 차이를 계산해 만약 더 클 경우 최댓값 profit을 계속 갱신하며넛 반복한다.
➕ 카데인 알고리즘(Kadane's Algorithm) 으로도 O(n)으로 풀이가 가능하다.
range
-
range는 range(시작숫자, 종료숫자, step)의 형태로 리스트 슬라이싱과 유사합니다.
-
range의 결과는 시작숫자부터 종료숫자 바로 앞 숫자까지 컬렉션을 만듭니다.
-
시작숫자와 step은 생략가능합니다.
-
range는 값을 확인하기 위해서 다른 순서 있는 컬렉션으로 변환해야합니다.
>>> range(5,10)
range(5, 10)
>>> list(range(5,10))
[5, 6, 7, 8, 9]
>>> tuple(range(5,10))
(5, 6, 7, 8, 9)- 파이썬에서 권장하지 않는 패턴
>>> s = [1, 3, 5]
>>> for i in range(len(s)):
... print(s[i])
...
1
3
5- 파이썬에서 권장하는 패턴
>>> for v in s:
... print(v)
...
1
3
5enumerate
-
반복문 사용 시 몇 번째 반복문인지 확인이 필요할 수 있습니다. 이때 사용합니다.
-
인덱스 번호와 컬렉션의 원소를 tuple형태로 반환합니다.
>>> t = [1, 5, 7, 33, 39, 52]
>>> for p in enumerate(t):
... print(p)
...
(0, 1)
(1, 5)
(2, 7)
(3, 33)
(4, 39)
(5, 52)
- tuple형태 반환을 이용하여 아래처럼 활용할 수 있습니다.
>>> for i, v in enumerate(t):
... print("index : {}, value: {}".format(i,v))
...
index : 0, value: 1
index : 1, value: 5
index : 2, value: 7
index : 3, value: 33
index : 4, value: 39
index : 5, value: 52