algo · 17

모노토닉 스택

코딩테스트모노토닉스택

모노토닉 스택(monotonic stack)은 스택 안의 값이 항상 한 방향으로만 변하도록, 곧 단조 증가 또는 단조 감소 순서를 유지하며 쓰는 스택입니다. 새 원소가 들어올 때 순서를 깨는 원소들을 먼저 꺼낸 뒤에 넣는 것이 핵심입니다. 자료구조가 새로운 것은 아니고 일반 스택에 규칙 하나를 더한 사용법입니다.

이 규칙 덕분에 "오른쪽에서 처음 나오는 더 큰 값"처럼 이중 반복문으로 O(n²)이 걸릴 문제를 O(n)에 풉니다. 반복문 안에 while이 있어서 이중 반복처럼 보여도 각 원소가 스택에 한 번 들어가고 한 번만 나오기 때문입니다. 이 토픽에서는 다음 큰 원소, 히스토그램의 가장 큰 직사각형, 주가 스팬을 같은 스택으로 풀어 봅니다.

핵심 개념

단조 스택

바닥에서 맨 위로 갈수록 값이 한 방향으로만 변하는 스택입니다. 다음 큰 원소를 찾을 때는 값이 줄어드는 단조 감소 순서를 유지합니다.

핵심 개념

꺼내며 답 확정

새 원소가 top보다 크면 top의 다음 큰 원소가 바로 그 새 원소로 정해집니다. 답이 정해진 원소는 스택에서 꺼내고 더 이상 보지 않습니다.

핵심 개념

인덱스를 쌓는다

값 대신 인덱스를 넣으면 값은 배열에서 읽고, 거리나 너비 같은 위치 정보도 함께 얻습니다. 히스토그램과 주가 스팬이 이 정보를 씁니다.

핵심 개념

다음 큰 원소

각 원소의 오른쪽에서 처음 나오는 더 큰 값입니다. 없으면 -1로 둡니다. 모노토닉 스택의 가장 기본적인 문제입니다.

핵심 개념

상각 O(n)

while이 반복되어도 각 원소가 한 번 들어가고 최대 한 번 나오므로 전체 연산이 2n 이하입니다. 한 번의 반복이 길어도 n번 전체 비용을 n으로 나누면 원소당 상수 시간입니다(상각).

핵심 개념

경계 찾기

원소를 꺼낸 뒤 남은 top이 왼쪽에서 가장 가까운 더 큰(또는 더 작은) 원소입니다. 같은 값을 포함할지는 비교 조건에 따릅니다. 이 경계로 직사각형의 너비나 스팬 같은 범위를 계산합니다.

시간은 O(n)입니다 — 원소마다 한 번 넣고 한 번 꺼내는 것이 전부라서 전체 push와 pop은 많아야 2n번입니다. 이중 반복문의 O(n²)을 줄입니다.

공간은 O(n)입니다 — 최악에는 모든 원소가 스택에 남습니다. 예를 들어 값이 줄어드는 배열에서는 다음 큰 원소를 찾는 스택에서 아무것도 꺼내지 못합니다.

방향은 문제가 정합니다 — 다음 큰 원소는 단조 감소, 다음 작은 원소는 단조 증가 스택입니다. 순서를 깨는 방향이 정반대입니다.

같은 값은 조건으로 정합니다 — 새 값이 top보다 "크면" 꺼낼지 "크거나 같으면" 꺼낼지에 따라 같은 값이 어떻게 처리되는지가 달라집니다.

이 시각화에서 확인할 것 — "다음 큰 원소" 탭에서 큰 값이 오면 작은 값들이 꺼내지며 답이 채워지는 모습을, "히스토그램 직사각형" 탭에서 낮은 막대를 만나면 높은 막대부터 꺼내며 넓이를 계산하는 모습을, "주가 스팬" 탭에서 오늘 이하인 날들이 한꺼번에 빠지는 모습을 STEP으로 확인하세요.

모노토닉 스택의 배경

모노토닉 스택은 교재나 논문의 정식 용어라기보다 알고리즘 문제 풀이에서 흔히 쓰는 이름이고, 특정 알고리즘 하나가 아니라 "각 원소에 대해 가장 가까운 더 작은(또는 더 큰) 원소를 찾는 문제"를 푸는 스택 기법을 가리킵니다. 이 문제는 전체 가장 가까운 작은 값(all nearest smaller values) 문제로 연구되었고, 병렬 알고리즘 분야에서 베르크만(Berkman), 쉬버(Schieber), 비슈킨(Vishkin)이 1993년 이 문제를 바탕으로 한 알고리즘을 발표했습니다. 비슷한 스택 기법은 배열에서 카르테시안 트리(Cartesian tree)를 선형 시간에 만드는 데에도 쓰입니다.

숫자로 확인하기

다음 큰 원소 — 배열 [2, 7, 3, 5, 4, 6, 8]의 답은 [7, 8, 5, 6, 6, 8, -1]입니다. 7이 오면 2가 꺼내지고, 5가 오면 3이, 6이 오면 4와 5가, 8이 오면 6과 7이 꺼내집니다. 8은 끝까지 남아 답이 -1입니다.

연산 횟수 — 원소 7개에 넣기 7번, 꺼내기 6번으로 모두 13번이고 2n = 14번 이하입니다.

히스토그램 — 높이 [2, 1, 5, 6, 2, 3]에서 가장 큰 직사각형은 높이 5인 막대와 높이 6인 막대를 포함해 높이 5, 너비 2로 만든 넓이 10입니다. 높이 2의 막대를 만나는 순간 높이 6(넓이 6)과 높이 5(넓이 10)가 차례로 꺼내집니다.

주가 스팬 — 가격 [100, 80, 60, 70, 60, 75, 85]의 스팬은 [1, 1, 1, 2, 1, 4, 6]입니다. 가격 85가 오면 75와 80이 꺼내지고 남은 100과의 거리가 6입니다.

코드 확인 — 파이썬과 자바가 같은 입력에서 같은 다음 큰 원소를 냅니다. 히스토그램 코드는 10을, 주가 스팬 코드는 위의 배열을 돌려줍니다.

자주 하는 오해

while 안의 반복 때문에 O(n²)이다 — 안쪽 while이 원소를 꺼내는 횟수를 모두 더해도 각 원소가 한 번만 나오므로 전체는 O(n)입니다. 반복문의 겉모양이 아니라 총 push와 pop 횟수로 셉니다.

스택에는 값을 넣어야 한다 — 거리나 너비를 구해야 하는 문제는 값만으로는 위치를 알 수 없습니다. 인덱스를 넣고 값은 배열에서 읽는 편이 일반적입니다.

항상 단조 감소 스택이다 — 문제에 따라 방향이 달라집니다. 다음 작은 원소를 찾으면 값이 늘어나는 단조 증가 스택을 씁니다.

같은 값은 신경 쓰지 않아도 된다 — 비교를 "<"로 할지 "<="로 할지에 따라 같은 값이 서로의 답이 되는지가 달라집니다. 문제의 정의(strictly 더 큰가, 같거나 큰가)를 먼저 확인해야 합니다.

모든 구간 문제에 쓸 수 있다 — 각 원소의 가장 가까운 더 크거나 작은 원소를 찾는 구조의 문제에 알맞습니다. 구간 합이나 임의의 구간 질의에는 다른 구조가 필요합니다.

면접에서 이렇게 물어요

면접 질문

다음 큰 원소를 O(n)에 구하려면?

값이 줄어드는 순서로 인덱스를 쌓는 스택을 씁니다. 새 원소가 top보다 크면 top을 꺼내며 그 원소의 답을 새 원소로 정하고, 마지막에 새 인덱스를 넣습니다. 끝에 남은 원소는 -1입니다.

면접 질문

while이 있는데 왜 O(n)인가요?

각 원소가 스택에 한 번 들어가고 최대 한 번 나옵니다. 모든 반복에서 꺼낸 횟수를 합쳐도 n을 넘지 않으므로 전체 연산은 2n 이하입니다.

면접 질문

히스토그램의 가장 큰 직사각형은 어떻게 구하나요?

높이가 줄지 않는(같거나 늘어나는) 순서로 인덱스를 쌓고, 더 낮은 막대를 만나면 꺼내며 높이와 너비를 곱해 넓이를 계산합니다. 왼쪽 경계는 꺼낸 뒤의 top 다음 칸이고 오른쪽 경계는 현재 위치 직전입니다. 끝에 높이 0을 붙여 남은 막대를 모두 처리합니다.

면접 질문

스택에 값이 아닌 인덱스를 넣는 이유는?

값은 인덱스로 배열에서 다시 읽을 수 있습니다. 반대로 같은 값이 여러 번 나올 수 있어 값만으로는 위치를 알 수 없고, 거리와 너비를 계산하려면 위치가 필요합니다.

활용 분야

가장 큰 직사각형 — 0과 1로 된 행렬에서 1로만 이루어진 가장 큰 직사각형을 찾을 때, 행마다 쌓인 높이를 히스토그램으로 보고 같은 스택을 적용하는 풀이가 알려져 있습니다.

카르테시안 트리 — 배열 순서가 중위 순회 순서가 되고 값은 힙 순서를 이루는 이진 트리(카르테시안 트리)를 스택으로 선형 시간에 만들 수 있습니다. 구간 최솟값 질의는 이 트리의 최소 공통 조상 문제로 바뀝니다.

주가 스팬 — 시간 순서로 들어오는 가격에서 이전에 더 큰 가격이 언제였는지, 며칠 동안 오늘 이하였는지를 한 번 훑어 구하는 스팬 문제에 씁니다.

함께 보면 좋은 토픽

스택과 큐 — 후입선출 스택의 기본 연산을 봅니다.

투 포인터 — 이중 반복을 한 번의 훑기로 줄이는 또 다른 기법을 봅니다.

시간 복잡도 — 상각 분석과 O(n)의 의미를 봅니다.

세그먼트 트리 — 구간 질의를 다루는 다른 자료구조를 봅니다.

참고 자료

논문 — Berkman, O., Schieber, B., Vishkin, U., "Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values", Journal of Algorithms 14(3), 1993

논문 — Vuillemin, J., "A unifying look at data structures", Communications of the ACM 23(4), 1980 (카르테시안 트리를 소개한 논문)

논문 — Gabow, H., Bentley, J., Tarjan, R., "Scaling and related techniques for geometry problems", STOC 1984 (카르테시안 트리의 선형 시간 구성)

교재 — Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", 3rd ed., Section 10.1 Stacks and queues, Chapter 17 Amortized Analysis

공식 문서 — Java Deque

공식 문서 — Java Stack

공식 문서 — Python Using Lists as Stacks

Python — 다음 큰 원소

def next_greater(a):
    ans = [-1] * len(a)                       # 답이 없으면 -1
    st = []                                   # 아직 답을 못 찾은 원소의 인덱스
    for i, x in enumerate(a):
        while st and a[st[-1]] < x:         # 새 원소가 top보다 크면
            ans[st.pop()] = x                 # top의 답이 확정된다
        st.append(i)
    return ans

print(next_greater([2, 7, 3, 5, 4, 6, 8]))   # [7, 8, 5, 6, 6, 8, -1]

각 원소의 오른쪽에서 처음 나오는 더 큰 값을 구합니다. 원소마다 오른쪽을 끝까지 훑으면 O(n²)이지만, 스택에 아직 답을 찾지 못한 원소의 인덱스를 쌓아 두면 O(n)에 풉니다. 새 원소 x가 오면 스택 맨 위의 값이 x보다 작은 동안 계속 꺼내며 그 원소들의 답을 x로 확정하고, 마지막에 x의 인덱스를 넣습니다. 끝까지 스택에 남은 원소는 오른쪽에 더 큰 값이 없어 답이 -1입니다. 이 과정에서 스택의 값은 바닥에서 맨 위로 갈수록 줄어드는 단조 감소 순서가 유지됩니다. 새 원소가 큰 값이면 작은 값들을 모두 꺼내고 들어가기 때문입니다. 값 대신 인덱스를 쌓아야 값은 a[인덱스]로 읽고, 거리나 너비가 필요한 문제에서도 같은 스택을 쓸 수 있습니다. 시각화의 다음 큰 원소 탭이 보여 주는 과정과 같습니다.

Python — 히스토그램의 가장 큰 직사각형과 주가 스팬

def largest_rectangle(h):
    st, best = [], 0
    for i, cur in enumerate(h + [0]):          # 끝에 높이 0을 붙여 모두 꺼낸다
        while st and h[st[-1]] > cur:
            height = h[st.pop()]
            left = st[-1] + 1 if st else 0     # 왼쪽에서 처음 낮은 막대 다음
            best = max(best, height * (i - left))
        st.append(i)
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))             # 10

def stock_span(p):
    st, span = [], []
    for i, x in enumerate(p):
        while st and p[st[-1]] <= x:        # 오늘 이하인 날은 꺼낸다
            st.pop()
        span.append(i - st[-1] if st else i + 1)
        st.append(i)
    return span

print(stock_span([100, 80, 60, 70, 60, 75, 85]))   # [1, 1, 1, 2, 1, 4, 6]

같은 스택을 다른 문제에 적용한 예입니다. 히스토그램에서는 높이가 줄지 않는(같거나 늘어나는) 순서로 인덱스를 쌓고, 더 낮은 막대를 만나면 꺼내며 그 막대를 높이로 하는 직사각형의 넓이를 계산합니다. 왼쪽 경계는 꺼낸 뒤 스택에 남은 top의 다음 칸이고 오른쪽 경계는 현재 위치 직전입니다. 막대 높이 [2, 1, 5, 6, 2, 3]에서는 높이 5, 너비 2로 만든 넓이 10이 가장 큽니다. 주가 스팬은 오늘 가격 이하인 날들을 스택에서 꺼내고, 남은 top과의 거리를 스팬으로 합니다. 날마다 한 번 넣고 최대 한 번 꺼내므로 모두 O(n)입니다. 같은 값을 어떻게 다룰지(<로 비교할지 <=로 비교할지)에 따라 결과가 달라지므로 문제가 요구하는 조건을 확인해야 합니다. 시각화의 히스토그램 직사각형 탭과 주가 스팬 탭이 보여 주는 과정과 같습니다.

Java — Deque로 다음 큰 원소

static int[] nextGreater(int[] a) {
    int[] ans = new int[a.length];
    Arrays.fill(ans, -1);
    Deque<Integer> st = new ArrayDeque<>();       // 스택으로 쓰는 Deque
    for (int i = 0; i < a.length; i++) {
        while (!st.isEmpty() && a[st.peek()] < a[i]) {
            ans[st.pop()] = a[i];
        }
        st.push(i);
    }
    return ans;
}

// nextGreater(new int[]{2, 7, 3, 5, 4, 6, 8}) → [7, 8, 5, 6, 6, 8, -1]

자바에서는 오래된 Stack 클래스보다 Deque 인터페이스의 구현체인 ArrayDeque를 스택으로 쓰는 것이 권장됩니다. Stack의 Javadoc은 Deque와 그 구현체가 더 완전하고 일관된 후입선출 연산 집합을 제공하므로 Stack 대신 쓰라고 안내합니다. push와 pop은 맨 앞에서, peek는 맨 앞 값을 읽는 연산이라 모두 스택의 top과 같습니다. 결과는 파이썬과 같은 [7, 8, 5, 6, 6, 8, -1]입니다. push와 pop은 보통 O(1)이고 원소마다 한 번씩만 넣고 꺼내므로 전체 시간은 O(n)입니다.

배열의 각 원소에 대해 오른쪽에서 처음 나오는 더 큰 값(Next Greater Element)을 O(n)에 구하는 데 쓰는 자료구조는?

아직 답을 찾지 못한 원소들을 쌓아두고 새 원소가 오면 확인합니다.

아직 더 큰 값을 만나지 못한 원소들의 인덱스를 스택에 쌓아 두고, 새 원소가 스택 top보다 크면 top을 꺼내 답을 확정하는 방식으로 O(n)에 해결합니다.

Next Greater Element를 구하는 모노토닉 스택에서 스택 안의 값은 어떤 순서로 유지될까?

새 값이 크면 그보다 작은 값들의 답이 정해집니다.

스택 top보다 큰 값이 오면 그 top의 "다음 큰 원소"가 확정되므로 pop합니다. 이 과정 때문에 스택에는 바닥에서 top으로 갈수록 값이 커지지 않는(같은 값은 남을 수 있는 단조 감소) 원소들만 남습니다.

모노토닉 스택 방식이 전체 O(n)인 이유는?

이중 반복문처럼 보이지만 총 push/pop 횟수를 세어 보세요.

반복문 안에 while로 pop이 있어도, 각 원소는 한 번 push되고 한 번 pop되는 것이 전부이므로 전체 연산 횟수는 최대 2n으로 O(n)입니다.