철학과 함께하는 투자인사이트

만약에 stack을 쓰게 된다면 O(2n)의 시간복잡도와 시간복잡도가 생기기 마련이다. 하지만 우리는 포인터 개념으로 여기에 접근하면 O(n)으로도 풀이가 가능하다 바로 이전에 저장했던 이전 node들을 저장해서 포인터의 방향을 반대로 바꾸는 것이다 코드를 한번 따라가보자 현재 노드를 뜻하는 curr가 2에 있다고 가정하자. 그렇다면 이전 노드를 뜻하는 prev는 1일 것이고, 3은 curr.next 가 될 것이다. 그렇다면 아래의 코드가 이해가 될 것이다 curr.next = prev 현재 curr 노드의 next는 prev 노드로 정한다 라는 뜻이다. 그럼 prev를 이제 현재 노드로 입력을 해두어야 다음 loop를 쓸 것이다 prev = curr 위와 같이 쓸 수 있다. 자 이제 2의 다음 node..

하루에 한번 매매를 할 수 있을 때, 어떻게 하면 저점에 사서, 고점에 팔 수 있는 알고리즘을 짜는 것이다. for loop를 두번 도는 것이 아닌, 매 loop를 돌 때마다 최고 가격과 최저가격을 기록하면 되는 것이므로, 아래와 같이 그냥 O(n)으로도 풀이가 가능하다. class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ import sys profit = 0 min_price = sys.maxsize for price in prices: if price profit : profit = ..