파이썬으로 주식 매매 최적 타이밍 찾기 – 최대 이익 계산 알고리즘

배열 A가 주어졌다고 가정해 봅시다. 여기서 A[i]는 i번째 날의 특정 주식 가격을 나타냅니다. 우리의 목표는 딱 한 번의 거래(주식을 사고 파는 행위)로 얻을 수 있는 최대 이익을 구하는 것입니다. 단, 동시에 여러 건의 거래를 진행할 수 없으므로 새로운 주식을 사기 전에 반드시 기존에 보유한 주식을 먼저 팔아야 합니다.

예를 들어 배열이 A = [7, 1, 5, 3, 6, 4]라고 해보겠습니다. 이 경우 결과값은 5가 됩니다. 2일째(인덱스 1)에 가격 1로 주식을 사고, 5일째에 가격 6으로 팔면 이익이 6 − 1 = 5가 되기 때문입니다.

문제 해결 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

• A와 같은 크기의 두 배열 leftMin과 rightMax를 생성하고 0으로 초기화합니다.
• leftMin[0] = A[0]으로 설정합니다.
• i가 1부터 A의 길이 − 1까지 증가하는 동안 leftMin[i] = min(leftMin[i − 1], A[i])로 갱신합니다. 즉, leftMin에는 각 시점까지의 최소 가격이 저장됩니다.
• rightMax[n − 1] = A[n − 1]로 설정합니다.
• i가 A의 길이 − 1부터 1까지 감소하는 동안 rightMax[i] = max(rightMax[i + 1], A[i])로 갱신합니다. 즉, rightMax에는 각 시점 이후의 최대 가격이 저장됩니다.
• answer := 0으로 초기화합니다.
• i가 0부터 A의 길이 − 1까지 증가하는 동안 answer = max(answer, rightMax[i + 1] − leftMin[i])로 갱신합니다.
• answer를 반환합니다.

핵심 아이디어

leftMin 배열은 "i번째 날까지 주식을 살 때 지불할 수 있는 최소 가격"을, rightMax 배열은 "i번째 날 이후 주식을 팔 때 얻을 수 있는 최대 가격"을 의미합니다. 따라서 모든 i에 대해 rightMax[i + 1] − leftMin[i]를 계산하면, 사고파는 시점의 모든 조합 중 가장 큰 이익을 효율적으로 찾을 수 있습니다.

구현 예제

class Solution(object):
    def maxProfit(self, prices):
        """
         :type prices: List[int]
         :rtype: int
        """
        if not prices:
            return 0
        leftMin, rightMax = [0 for i in range(len(prices))], [0 for i in range(len(prices))]
        leftMin[0] = prices[0]
        for i in range(1, len(prices)):
            leftMin[i] = min(leftMin[i-1], prices[i])
        rightMax[-1] = prices[-1]
        for i in range(len(prices)-2, -1, -1):
            rightMax[i] = max(rightMax[i+1], prices[i])
        ans = 0
        for i in range(len(prices)-1):
            ans = max(ans, rightMax[i+1]-leftMin[i])
        return ans

ob1 = Solution()
print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))

입력

prices = [7,2,5,8,6,3,1,4,5,4,7]

출력

6

복잡도 분석

이 알고리즘은 배열을 총 세 번 순회하며, 각각 최소 가격 누적, 최대 가격 누적, 최대 차이 계산을 수행합니다. 따라서 시간 복잡도는 O(n), 공간 복잡도 역시 보조 배열 두 개를 사용하므로 O(n)입니다. 완전 탐색 방식(O(n²))보다 훨씬 효율적으로 대량의 가격 데이터도 빠르게 처리할 수 있습니다.