단조 스택: 딱 필요한 만큼만 기억하기

"단조 스택은 쓸모없어지는 순간 다시는 필요 없을 걸 버려. 그 무자비한 잊음이 O(n²) '앞 보기' 를 한 번의 O(n) 패스로 바꿔."

이게 푸는 문제

생각해봐: 배열의 각 원소에 대해, 오른쪽으로 다음에 나오는 더 큰 원소 ("next greater element") 를 찾아. 당연한 해법은, 각 원소마다 더 큰 게 나올 때까지 오른쪽으로 훑기 — O(n²). 많은 데이터엔 너무 느려. 단조 스택이 전체를 O(n) 에 풀고, 이 퀘스트 전체에서 가장 만족스러운 트릭 중 하나야.

아이디어: 스택을 정렬 상태로 유지

단조 스택은 원소를 정렬 순으로 유지해 — 가령, 바닥에서 위로 감소 — 새 걸 push 하기 전에 순서를 어기는 원소를 다 pop 해서. "next greater" 마법: 왼쪽에서 오른쪽으로 걸어. 각 새 값을 push 하기 전에, 스택 위 그것보다 작은 원소를 다 pop 해 — 그 pop 된 원소들 각각한테, 이 새 값이 그들의 next greater element 니까. 한 동작에 답하고 버린 거야. 스택에 남은 건 아직 답을 기다리는 거.

안쪽 pop-반복문이 있는데 왜 O(n²) 아니라 O(n) 이야? Complexity 트랙의 분할 상환 논증: 각 원소가 정확히 한 번 push 되고 많아야 한 번 pop 돼. 총 push + pop ≤ 2n. 안쪽 반복문의 총 일이 전체 구간에 걸쳐 선형이야, 어느 한 단계가 여러 원소를 pop 할 수 있어도. 중첩이 아니라 총 연산을 세면 O(n) 이 드러나.

단조 스택은 각 push 전에 위반자를 pop 해서 정렬 상태로 유지해. 각 원소가 한 번 들어오고 한 번 나가서, '각 항목마다 다음 더 큰/작은 것 찾기' 문제가 O(n²) 에서 O(n) 으로 무너져. pop 된 원소는 방금 답을 찾은 거야.

문제의 가문

모양을 알아보면, 가문 전체가 열려: next greater / next smaller element, daily temperatures (더 따뜻한 날까지 며칠), stock span (이전 연속 며칠이 더 낮았나), 그리고 유명한 히스토그램 최대 직사각형. 다 신호 하나를 공유해: "각 원소마다, 어떤 방향으로 그걸 이기는 가장 가까운 원소 찾기." 그게 들리면, 단조 스택으로 가.

피파의 고백

단조 스택은 아빠가 pop 을 다시 짜맞추기 전까진 안 딸깍했어: "넌 검색하는 게 아니라 — 답하고 버리는 거야." pop 하는 각 원소가, 그 순간, 자기 next-greater 를 찾은 거야. 다시는 안 봐. 난 그걸 영리한 검색으로 생각했는데; 사실은 영리한 잊음이야 — 아직 답을 기다리는 원소만 유지하는 거. 그 재구성이 O(n) 을 마법 대신 필연으로 느끼게 했어.

Code

next greater element 를 O(n) 에·python

def next_greater(nums):
    """각 원소에 대해, 오른쪽으로 다음에 나오는 더 큰 원소.
    없으면 -1. 단조 (감소) 스택으로 총 O(n)."""
    result = [-1] * len(nums)
    stack = []                       # 인덱스 보관, 값으로 감소 유지
    for i, x in enumerate(nums):
        # x 는 스택에서 기다리는 모든 더 작은 값의 'next greater'
        while stack and nums[stack[-1]] < x:
            idx = stack.pop()        # 이 원소의 답은 x — 기록하고 버림
            result[idx] = x
        stack.append(i)              # 이제 i 가 자기 next greater 를 기다림
    return result                    # 스택에 남은 건 -1 그대로

print(next_greater([2, 1, 2, 4, 3]))   # [4, 2, 4, -1, -1]
# 2->4, 1->2, 2->4, 4->없음, 3->없음.
# 각 인덱스가 한 번 push 되고 많아야 한 번 pop: 총 O(n),
# 안쪽 while 반복문이 있어도.

Exercise

'Daily temperatures': 일별 온도 리스트가 주어지면, 각 날마다 더 따뜻한 날까지 며칠 기다려야 하는지 출력해 (영영 없으면 0). 위 단조-스택 코드를 적응시켜 (인덱스 저장, 온도 비교, pop 할 때 날짜-간격 기록). 그다음 안쪽 while-반복문에도 왜 O(n) 인지 논증해.

Hint

인덱스를 push; 오늘 온도가 스택 맨 위 인덱스의 온도를 넘으면, pop 하고 result[popped] = 오늘_인덱스 − popped_인덱스. O(n) 인 이유는 각 날이 한 번 push 되고 많아야 한 번 pop — 총 일 ≤ 2n.

이게 푸는 문제

아이디어: 스택을 정렬 상태로 유지

문제의 가문

피파의 고백

Code

External links

Exercise

Progress

댓글 0