스택(Stack)이 무엇이고 어디에 활용되고 있는지 알아봅니다. 그리고 스택과 관련된 문제를 풀어봅니다.

스택 (Stack)

말 그대로 데이터를 쌓아올린다고 해서 스택(Stack)이라고 불리는 자료구조입니다.

처음 자료구조를 접할 때는 이런게 왜 필요한가 싶었는데 프로그래밍을 하다보면 생각보다 이런 상황이 의외로 많이 생깁니다.

스택의 구조를 보면 이해하기 쉽습니다. 구조적으로 가장 나중에 들어온 데이터가 먼저 나옵니다. 구조는 이해하겠는데 스택을 어떤식으로 활용하는 지가 더 궁금하시죠?

스택의 활용

컴퓨터 프로그램에서 함수를 부를 때도 스택을 사용합니다. 순서대로 명령어를 실행하는 컴퓨터가 함수를 만나면 함수에 대한 명령어를 실행하고 다시 원래 코드로 복귀해야 합니다. 더 확장해서 함수 안의 함수가 있는 코드를 생각하면 함수가 종료될 때 마다 가장 최근에 실행했던 코드로 돌아가야 함을 알 수 있죠. 이는 스택을 사용해야 하는 경우임을 알 수 있습니다. 이런 함수의 정보를 저장하는 메모리를 콜스택(Call Stack)이라고 표현합니다.

프로그래밍을 할 때 가끔씩 사용하던 재귀함수도 마찬가지입니다. 내부적으로 스택으로 구현되어 있습니다. 그래프에서 모든 노드를 탐색할 때 사용하는 DFS(Depth First Search, 깊이 우선 탐색)은 구현할 때 특성상 스택이 필요한데, 이미 재귀함수가 스택 그 자체이기 때문에 DFS는 재귀를 쓰면 몇줄 안되는 코드로 구현할 수 있습니다.

또 다른 예로 아래 그림과 같이 Visual Studio에서 제공하는 기능이 있습니다.

영역을 구분할 때 ‘{‘, ‘}’로 묶는 프로그래밍 언어들이 있습니다. 여는 괄호를 쓰고 닫지 않으면 체크해서 알려주는데요. 아무리 코드가 길어도 위 그림처럼 괄호의 정합성 문제가 생기면 어디가 문제인지 바로 알려줍니다. 이 기능을 구현하려면 생각보다 로직이 어렵다고 할 수 있지만, 스택을 이용하면 쉽게 구현할 수 있는 기능입니다.

이 문제를 푸는 아이디어는 닫는 괄호가 나타나면 반드시 가장 최근에 생성된 여는 괄호와 짝이라는 사실입니다.

예제: 괄호 정합성 판단

위에서 설명한 괄호 문제를 간소화한 문제가 있습니다.

문제 링크:: 괄호 문제(https://www.acmicpc.net/problem/9012)

자세한 문제 설명은 위 링크로 들어가셔서 확인하시고 직접 풀어보세요!

이 문제는 소괄호 ‘()’ 으로만 이루어졌지만 이 문제만 풀 수 있어도 ‘()’, ‘{}’, ‘[]’와 같은 다양한 괄호를 사용하더라도 바로 쉽게 푸실 수 있을 것입니다.

풀이

핵심적인 아이디어는 닫는 괄호가 나타나면 반드시 가장 최근에 생성된 여는 괄호와 짝이다 입니다.

정합성이 맞으려면 닫는 괄호가 나타났을 때 여는 괄호가 하나라도 있어야 하고, 그리고 코드가 종료됐을 때 여는 괄호가 하나라도 남아 있으면 안됩니다.

한문장이 주어졌을 때 정합성 판단하는 코드 입니다.

scanf("%s", str);

bool flag = 1;
stack<char> stk;
for (int i = 0; str[i]; i++)
{
   if (str[i] == '(') 
      stk.push(1);
   else if (stk.size() > 0) 
      stk.pop();
   else 
      flag = 0;
}
if (stk.size()) flag = 0;

printf("%s\n", flag ? "YES" : "NO");

다른 문제 추천

• 스택(https://www.acmicpc.net/problem/10828)
• 히스토그램(https://www.acmicpc.net/problem/1725)

스택은 일반적인 프로그래밍에서 구현상의 문제로 자주 사용하지만, 알고리즘 문제에도 필요한 경우가 간혹 있습니다. 위의 히스토그램 문제는 스택을 이용하면 O(N) 시간에 빠르게 구할 수도 있습니다. 물론 아이디어를 떠올리는 것이 쉽지는 않아요. 그저 여러 문제를 풀어보는 것만이 답인 듯 합니다.