코딩 테스트 대비! 파이썬으로 "주식 사고팔기 가장 좋은 시점" 문제 풀이

파이썬으로 "주식 사고팔기 가장 좋은 시점" 문제 풀이


문제 설명

주식 가격의 변동이 배열 prices로 주어졌을 때, 최대 이익을 거둘 수 있는 최적의 단일 매매 기회를 찾아 이익금액을 출력하는 프로그램을 작성하세요.


제약 조건

- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104


예시 입출력

- prices = [7,1,5,3,6,4] -> 5 (5일 때 사고 6일 때 팔면 최대 이익 5)
- prices = [7,6,4,3,1] -> 0 (매매 기회가 없으므로 최대 이익은 0)

솔루션 코드

def max_profit(prices):
    min_price = float('inf')
    max_profit = 0
    
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
        
    return max_profit

# 테스트
print(max_profit([7,1,5,3,6,4]))  # 5
print(max_profit([7,6,4,3,1]))    # 0

코드 설명

1. min_price 변수에 무한대 값을 할당하여 초기화합니다.
2. max_profit 변수를 0으로 초기화합니다.
3. prices 배열을 순회하면서:
    - min_price를 현재까지의 최소 주가와 현재 주가 중 작은 값으로 업데이트합니다.
    - max_profit을 현재까지의 최대 이익금과 (현재 주가 - 최소 주가) 중 큰 값으로 업데이트합니다.
4. 반복이 끝나면 max_profit이 주어진 prices에서 얻을 수 있는 최대 이익금입니다.

이 풀이의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다.

이 문제는 하나의 반복문을 통해 최소 주가와 최대 이익금을 계속 업데이트 하는 그리디 알고리즘 기법을 다룹니다. 주가 배열을 한 번만 순회하면서 최적의 매매 시점을 찾을 수 있습니다. 이런 유형의 문제를 연습하면 그리디 알고리즘에 대한 사고력이 향상될 것입니다.