쉬움
Best Time to Buy and Sell Stock
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 최대이익(prices):2 최저가 = prices[0] // 지금까지 본 가장 싼 값3 최저i = 04 최대이익 = 0 // 아직 거래 없음5 반복 i = 1 … n-1:6 오늘가 = prices[i]7 이익 = 오늘가 - 최저가 // 오늘 판다면?8 만약 이익 > 최대이익:9 최대이익 = 이익 // 최고 기록 갱신10 만약 오늘가 < 최저가:11 최저가 = 오늘가; 최저i = i // 더 싸게 살 기회12 반환 최대이익
변수
- i
- 0
- 오늘가
- 7
- 최저가
- 7
- 이익
- 0
- 최대이익
- 0
1 / 10첫날 가격 7 을(를) 최저가로 두고 시작합니다.
지금까지의 최저가를 기억하며, 오늘 팔았을 때의 이익을 최대로 갱신한다(1회 거래).
왜 헷갈리는가
모든 매수-매도 쌍을 O(n²)로 볼 것 같지만, '오늘의 최선 매수'는 항상 '오늘 이전의 최저가' 하나뿐이라 한 번에 풀린다. 여러 번 거래하는 변형(II)과 자주 혼동된다.
핵심 아이디어
왼쪽부터 지나가며 지금까지의 최저가를 계속 갱신한다. 각 날에는 '오늘 팔면 이익 = 오늘가 − 지금까지 최저가'만 보면 되고, 그 최댓값이 답이다.
복잡도
시간 O(n)·공간 O(1). 과거 전체를 다시 보지 않고 '최저가' 하나만 들고 간다.
실무에서 어디에 쓰나
'저점 대비 최대 상승'은 금융 밖에서도 흔하다.
- 트레이딩: 단일 진입-청산의 최적 시점·최대 이익 산정
- 리스크: 최저점 대비 최대 낙폭/회복(drawdown/run-up) 측정
- 용량: 사용률 저점 대비 최대 피크 계산
- SLA: 최저 가용성 시점 대비 회복 폭 추적
흔한 실수
음수 이익을 허용하면 안 된다(거래 안 함 = 이익 0). 하한을 0으로 둔다. '1회'와 '여러 번' 거래를 구분.
기억할 것
- 오늘의 최선 매수 = 이전까지의 최저가.
- 과거 전체 대신 최저가 하나만 기억.
- 이익 하한은 0(거래 안 함).
- 저점 대비 최대 상승의 표준.