_6_ 자료구조 — 스택

MJ Studio
알고리즘은 미친짓이다
11 min readMay 2, 2022

스택 자료구조와 연산, 시간복잡도, 활용법에 대하여 알아봅시다.

스택

동적 배열을 이해했다면 스택의 작동 원리는 어렵지 않습니다.

스택이란 우리가 일상생활에서 흔히 접하는 프링글스 통을 예시로 들 수 있습니다.

프링글스 통에 맛있는 프링글스가 100개가 들어있다고 합시다.

제일 밑에서부터 1번 째 프링글스라고 생각했을 때 100번 째 프링글스를 꺼내지 않고 99 번 째 프링글스를 꺼낼 수 있나요? 꺼낼 수 있다면 저한테도 좀 보여주세요.

어쨌든 보통의 경우 꺼낼 수 없는데, 이렇게 일단 위에 것들을 꺼낸 이후에 아래 것들을 꺼낼 수 있는 구조를 후입선출(Last In First Out, LIFO)구조라고 합니다.

스택의 젤 윗 부분을 top이라고 부릅니다.

근데 이건 우리가 전에 배웠던 동적 배열이 지원해주는 연산과 100% 동일합니다.

제일 마지막에 push를 해주고 제일 마지막에 pop을 해줄 수 있다면 동적 배열을 사용하지 스택이란 자료구조를 굳이 사용할 이유가 있나요? 게다가 스택은 중간의 원소를 인덱스를 이용해 O(1)에 접근할 수 있는 기능조차 지원을 안해줍니다!

c++에선 심지어 std::vectorstd::stack이 둘 다 존재합니다.

그러면 스택은 왜쓸까요?

사실 스택은 std::vector를 쓰든 std::stack을 쓰든 별 상관이 없고 스택스럽게 push, pop을 이용해서 데이터들을 관리하며 풀 수 있는 문제들에서 스택을 이용해 문제를 푼다라고 하기 위해서 의미론적으로 사용되기도 합니다.

그러니까 파이썬같은 경우 스택이란게 따로 없어도 그냥 리스트를 이용해 스택처럼 사용할 수 있다는 것입니다.

또한 고인물들은 자기가 하고싶은대로 정적 배열을 이용해 스택처럼 사용하기도 합니다. 다음과 같은 코드를 보겠습니다.

top_index 라는 변수로 현재 스택의 top이 어디인지를 기록해주며 원소를 추가할 땐 top_index1 증가시키고 거기에 원소를 저장해줍니다.

반대로 원소를 삭제할 땐 그냥 top_index1 감소시켜주기만 하는데, 어차피 다시 원소가 추가가 될 때 원하는 원소로 정적 배열의 원소를 덮어쓰기 해줄 수 있기 때문입니다.

그리고 당연히 스택에서 top 에서의 push과 pop은 시간복잡도가 O(1) 입니다.

이처럼 스택의 구현체는 그리 중요하지 않고 사실상 스택을 이용해서 어떤 문제들을 풀 수 있느냐가 중요합니다.

활용 1. 올바른 괄호 문자열

괄호라는 개념은 PS에서 정말 지겹도록 많이 등장하는 떡밥입니다.

그 중 특히 올바른 괄호 문자열 판별은 앞으로 PS를 제대로 하실 계획이시라면 아주 친근해져야 할 것입니다.

올바른 괄호 문자열이란 () 처럼 여는 괄호와 닫는 괄호의 수가 같아야 하고 왼쪽에서 오른쪽으로 훑을 때 닫는 괄호의 개수가 열린 괄호의 개수보다 많으면 안되는 구조입니다.

예를 들어 ())( 는 (와 )의 개수가 같지만 적절히 짝지을 수 없어서 올바른 괄호 문자열이 아닙니다.

하지만 ()((()())) 는 올바른 괄호 문자열입니다.

여하튼 이 문제도 나중가면 말도안되는 자료구조나 문자열 알고리즘을 써서 풀어야 할 수도 있지만 일단 스택으로 해결할 수 있는 가장 유명한 문제 중 하나입니다.

알고리즘은 다음과 같습니다.

  1. ‘(‘ 를 만났을 때

쉽습니다. 그냥 스택에 ‘(‘ 를 쌓아줍시다.

2. ‘)’ 를 만났을 때

만약 스택에 ‘(‘ 가 있다면 ‘(‘ 를 pop해줍니다.

그렇지 않다면 자신과 짝지어질 ‘(‘ 가 앞에 더 없다는 뜻이므로 올바른 괄호 문자열이 아닙니다.

3. 마지막으로 스택이 비었는지 검사

스택이 비어있지 않다면 올바른 괄호 문자열이 아닙니다.

(((( 같은 문자열을 보세요. 마지막에 스택에 그냥 ‘(‘ 가 4개 쌓인 형태로 끝이 나게 됩니다.

하지만 올바른 괄호 문자열은 1, 2 번 알고리즘을 적용하면 항상 스택이 비어있는 상태로 끝나게 됩니다.

꼭 스택을 사용할 필요도 없습니다.

사실 저도 사용하는 방법인데 그냥 열린 괄호의 개수를 정수형 자료형에 세도(실제로 스택을 사용하지 않아도) 그냥 스택을 사용하게 되는 방법입니다.

활용 2. Monotone Stack + Bad Hair Day problem

유명한 유형 중 하나입니다. Bad Hair day라는 유형은 사람들이 일렬로 서서 한 쪽 방향으로만 보고 있을 때 모든 사람들이 다른 사람들의 뒤통수를 총 몇 사람이나 볼 수 있는 지 구하는 문제입니다. 뭐 조금의 변형이 있을 수 있습니다.

이 옥상 정원 꾸미기 문제는 정확히 그 문제와 동일합니다. 문제의 예시를 볼까요?

             = 
= =
= - =
= = = -> 관리인이 보는 방향
= - = = =
= = = = = =
10 3 7 4 12 2 -> 빌딩의 높이
[0][1][2][3][4][5] -> 빌딩의 번호

0번 관리인은 1, 2, 3번 빌딩을 볼 수 있습니다. 4번 빌딩은 0번 빌딩의 높이인 10보다 크거나 같은 12이기 때문에 4번 빌딩부터 보지 못하는 것입니다.

마찬가지로 1번 관리인은 아무런 빌딩을 볼 수 없습니다. 바로 앞에 있는 2번 빌딩이 자신의 빌딩의 높이보다 크거나 같거든요.

이 문제는 Monotone Stack 테크닉을 써서 해결할 수 있습니다.

Monotonicity란 단조성이란 의미로 자료구조의 데이터들을 특별한 규칙에 맞춰 계속 관리함을 의미합니다. 이 문제에선 다음과 같습니다.

중요한 건 스택에서 top으로 갈 수록 빌딩의 높이가 계속 감소한다는 것이 보장되게 스택을 유지하는 것입니다.

스택에 <빌딩의 높이, 인덱스> 를 pair 로 쌓아간다고 해봅시다.(pair는 실제로 c++같은 경우 std::pair 를 쓸 수 도 있고, 파이썬은 그냥 튜플이나 리스트 그 자체를 써도 됩니다.)

일단 0번 관리인부터 봅니다. 처음에 스택은 비어있는 상태일테고 딱히 할게 없으니 <10, 0> 을 스택에 넣어줍니다.

1번 관리인을 봅시다. 스택에는 <10, 0> 이 들어있고 자신의 빌딩의 높이인 3은 10보다 작으니 그냥 자신도 스택에 쌓아줍니다. 이 경우 < 3, 1> 이 쌓이겠습니다.

지금까지 스택의 모양을 보면 다음과 같습니다.

보시면 아시겠지만 계속 top으로 갈수록 첫 번째 요소인 빌딩의 높이가 감소하는 것이 지켜진다는 것이 보이실 겁니다.

이제 2번 관리인을 볼까요? 빌딩의 높이가 7이네요. 그러면 이제 7은 3 이상이므로 스택에 계속 쌓지 못합니다. 7보다 이하인 빌딩들을 모두 빼주며 스택을 관리해줘야 합니다.

이제 < 3, 1>을 빼며 중요한건 이 빌딩은 인덱스=1 빌딩이였다는 것입니다.

현재 2번 인덱스를 보고 있으니 1번 인덱스와의 차이가 1이고 이는 정답에 0을 더해주어야 함을 의미합니다.

왜냐하면 인덱스가 1차이나면 그 사이에 1번 인덱스가 볼 수 있는 빌딩이 아무것도 없다는 것을 의미하기 때문입니다.

즉, 현재 인덱스 — pop 되는 인덱스 — 1 를 정답에 더해주어야 합니다.

이렇게 뭔가 자신보다 높이가 작거나 같은 빌딩들을 계속 빼주는 것과 같이 반복된 조건을 진행 할 땐while 문을 쓰는 것이 가장 자연스럽습니다.

이렇게 쭉쭉 진행하다보면 마지막 N-1 번 째 빌딩까지 모두 보고 알고리즘이 종료됩니다.

하지만 이게 정답인가요? 아닙니다.

 = 
= =
= = =
= = = = -> 관리인이 보는 방향
= = = = =
= = = = = =
12 10 8 6 4 2 -> 빌딩의 높이
[0][1][2][3][4][5] -> 빌딩의 번호

이렇게 계속해서 감소하는 빌딩의 높이가 있을 때 위 알고리즘이 정답이 몇으로 나올까요? 0입니다.

왜냐면 정답이 더해지는 부분이 없기 때문입니다. 스택에 계속 쌓이기만 하고 알고리즘이 종료되어버립니다.

이를 위해 제일 마지막에 다음과 같이 스택에서 남아있는 것들을 가장 끝 위치(n) 에서 얼마나 차이나는지 정답에 더해주고 제거해주는 방법으로 정답을 산출해줄 수 있습니다.

while len(stack):
answer += n - stack.top().index - 1
stack.pop()

혹은 그냥 높이 무한대의 마지막 빌딩을 하나 추가해버리는 것도 가능합니다.

                   ...
= =
= = =
= = = =
= = = = = -> 관리인이 보는 방향
= = = = = =
= = = = = = =
12 10 8 6 4 2 inf -> 빌딩의 높이
[0][1][2][3][4][5] [6] -> 빌딩의 번호

이렇게 되면 더미로 추가한 제일 마지막 6번 빌딩에서 0, 1, 2, 3, 4, 5 번 빌딩이 모두 처리되어버리기 때문에 깔끔하게 코드 작성이 가능합니다.

이렇게 문제를 풀 때 코드를 일관성있게 작성하기 위해 더미 데이터를 맨 앞, 맨 뒤 혹은 어디든 추가해서 데이터를 전처리하고 시작하기도 합니다.

예를 들어, 정답과 중간 연산 값들이 0.5 단위로만 떨어지는 문제를 해결할 때 모든 값에 2를 곱하고 시작해서 정수형으로만 알고리즘이 수행될 수 있게 하는 경우도 비슷합니다.

이 경우 알고리즘의 시간복잡도는 O(N) 입니다.

혹은 pair 로 관리하지 않고 단순히 정수형들만 스택에 넣어서도 문제를 해결할 수 있습니다.

JH 님의 방법은 현재 i번째 빌딩을 스택에 push하기 전에 현재 스택에 존재하는 빌딩의 개수를 정답에 계속 더해주시는데, 이는 i 번째 빌딩을 볼 수 있는 빌딩의 개수들을 즉각적으로 정답에 더해주기 때문에 올바르게 알고리즘이 수행됩니다.

비슷한 문제입니다. 이 경우 스택을 단조감소로 유지하게 됩니다.

단조 감소(monotone decreasing)와 감소(strictly decreasing)는 다른데, 단조 감소는 중간에 같은 값이 있어도 괜찮고 감소(순 감소라고도 함)는 무조건 계속 감소만 해야 합니다.

단조 증가, 증가도 마찬가지의 의미이니 참고하세요.

연습 문제

이 문제도 Monotone Stack 알고리즘으로 해결 가능합니다!

제가 알고리즘을 처음 배울 때 죽도록 고생한 문제입니다. 스택과 더 친해질 수 있습니다.

입출력이 조금 더럽지만 괄호 문자열 문제입니다.

--

--