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

"단조 스택은 쓸모가 없어지는 순간 그걸 버려. 다시는 볼 일이 없으니까. 그 냉정한 망각이 O(n²)짜리 '앞을 내다보기'를 O(n) 한 번으로 바꿔."

이게 푸는 문제

이런 문제를 생각해 봐. 배열의 각 원소마다 오른쪽에서 처음 만나는 더 큰 원소("next greater element")를 찾는 거야. 떠오르는 방법은 원소마다 오른쪽으로 더 큰 게 나올 때까지 훑는 건데, 그러면 O(n²)라 데이터가 많으면 못 써. 단조 스택은 이걸 통째로 O(n)에 풀어. 이 퀘스트에서 손꼽히게 통쾌한 기법이야.

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

단조 스택은 원소를 정렬된 상태로 유지해. 예를 들면 바닥에서 위로 갈수록 작아지게. 유지하는 방법은 새 값을 push하기 전에 순서를 어기는 원소를 전부 pop하는 것이야. next greater가 여기서 나와. 왼쪽에서 오른쪽으로 걸어가면서, 새 값을 넣기 전에 스택에 있는 그보다 작은 원소를 전부 pop해. 왜냐면 그렇게 pop되는 원소들에게는 바로 이 새 값이 next greater element거든. 한 동작으로 답을 주고 내보낸 거야. 스택에 남아 있는 건 아직 자기 답을 기다리는 것들이고.

안쪽에 pop 반복문이 있는데 왜 O(n²)가 아니라 O(n)일까. 복잡도 트랙에서 쓴 분할 상환 논증 그대로야. 원소 하나가 정확히 한 번 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