백준 6549번 분할정복, 스택

서론

6549번: 히스토그램에서 가장 큰 직사각형

처음으로 백준의 플레티넘 문제를 풀어서 기록으로 남기려고 작성합니다. 문제에 대한 해답도 고민해 보겠지만 지금까지 어떤 방식으로 백준을 풀었는지 남기려고 합니다.

제한 조건

백준을 풀면서 정답은 맞으나 조건을 충족시키지 못한 경우가 많아서 제한조건을 먼저 생각하고 문제를 풀었습니다. 항상 최악의 경우를 생각합니다.

• 시간제한 - 1초

시간제한은 1초입니다. 저는 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준으로 문제를 풀고 있습니다. 데이터의 개수는 10만 개입니다. O(n^2)으로 문제를 풀 게 되면 루프 안에서 O(1)로 연산을 해도 100억 번의 연산이 필요하므로 명백하게 O(n^2)보다 빠른 알고리즘으로 푸는 문제입니다. 지금 와서 이렇게 분석했지만, 처음에 풀 때는 그냥 O(n^2)으로도 풀어봤습니다. 역시 틀렸습니다.

• 메모리 제한 - 256MB

백준을 풀면서 메모리 제한은 그렇게 크게 생각하지를 않았는데 이번 문제 풀면서 너무 많이 틀려서 이 조건도 생각해 보게 되었습니다. 메모리 제한은 256MB이고 문제에서 데이터의 개수는 최댓값 10억을 가지는 10만 개의 데이터입니다. 파이썬의 경우 arbitrary precision을 가지지만 그래도 계산을 해보자면 4바이트 int형에 -20억~20억 정도의 데이터를 담을 수 있으니 데이터 한 개의 크기를 4바이트로 잡고 10만 개, 40만 바이트, 즉 총 데이터 메모리는 400KB입니다.

데이터 자체를 전부 다 저장해도 충분해 보이는데 자꾸 틀려서 생각해 보니 함수에서 인자로 데이터 배열을 받아서였습니다. 인자로 데이터를 받을 때마다 복사해서 새로운 메모리를 차지하고 분할정복의 경우 필연적으로 함수가 재귀로 여러 번 호출되기 때문에 256MB를 넘어서 틀리는 거였습니다. 따라서 분할정복을 사용하지 않거나 분할정복 사용 시 데이터는 전역변수로 두고 인덱스값으로 데이터를 참조해야 합니다.

분할 정복 O(nlogn)

데이터를 계속 절반씩 나누고 나눠진 부분에 대해서 처리하는 분할정복입니다. 나누어졌을 때 최솟값은 히스토그램 한 개만 남을 때이며 이때는 그냥 히스토그램의 넓이를 리턴합니다. 나눠진 부분처리는 절반을 기준으로 인덱스를 좌우로 한 개씩 늘려가며 최대넓이를 찾습니다.

절반씩 분할정복을 하므로 logn, 나눠진 부분을 처리하는 방법에서 최악의 경우 n의 시간복잡도를 가지기 때문에 O(nlogn)의 시간복잡도를 가지게 됩니다. 데이터를 인덱스로 참조하기 때문에 공간복잡도 문제도 없습니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def max_area(left, right):
    if left == right:
        return hist[left]

    else:
        half_idx = (left+right)//2
        new_left = half_idx
        new_right = half_idx + 1
        new_height = min(hist[new_left], hist[new_right])
        new_width = 2
        tmp = 2 * new_height

        while True:
            if (new_left == left or hist[new_left] == 0) and (new_right == right or hist[new_right] == 0):
                break

            elif new_left == left or hist[new_left] == 0:
                new_height = min(new_height, hist[new_right+1])
                new_right += 1
                new_width += 1

            elif new_right == right or hist[new_right] == 0:
                new_height = min(new_height, hist[new_left-1])
                new_left -= 1
                new_width += 1

            else:
                if hist[new_left-1] >= hist[new_right+1]:
                    new_height = min(new_height, hist[new_left-1])
                    new_left -= 1
                    new_width += 1
                else:
                    new_height = min(new_height, hist[new_right+1])
                    new_right += 1
                    new_width += 1

            tmp = max(tmp, new_width*new_height)

        return max(max_area(left, half_idx), max_area(half_idx+1, right), tmp)


while True:
    tc, *hist = list(map(int, input().split()))
    if tc == 0:
        break

    print(max_area(0, tc-1))

스택 O(n)

스택으로도 푸는 방법이 있다고 하여 혼자서 스택으로 풀어보려고 했으나 실패하고 결국 찾아보고 풀어보게 되었습니다.

데이터 전체를 따라가며 조건에 의해 스택에 넣고 조건이 맞지 않는 경우 스택 안의 데이터를 팝 시키며 최대넓이를 찾는 방법입니다.

이 경우 for문안에 while문이 나와서 정확하게 시간복잡도가 계산되진 않지만, 보통의 경우 스택으로 문제를 풀 게 되면 O(n)의 시간복잡도를 가진다고 합니다. 역시 데이터를 인덱스로 참조하기 때문에 공간복잡도 문제도 없습니다.

import sys
from collections import deque as dq
input = sys.stdin.readline

while True:
    tc, *hist = list(map(int, input().split()))
    hist.append(0)
    if tc == 0:
        break

    stack = dq()
    max_sq = 0

    for i in range(len(hist)):

        while len(stack) != 0 and hist[stack[-1]] > hist[i]:
            tmp = stack.pop()

            if len(stack) == 0:
                width = i
            else:
                width = i - stack[-1] - 1
            max_sq = max(max_sq, width*hist[tmp])
        stack.append(i)

    print(max_sq)

생각

문제의 해답을 자세하게 설명한 글은 아닙니다. 그냥 문제를 푸는데 조건에 걸려서 틀리는 경우가 너무 많아서 처음부터 주어진 조건을 가지고 분석을 한 후 문제를 푸는 것이 맞는 것 같아 생각하는 순서를 한번 적어봤습니다.