코딩테스트에서 자주 등장하는 데이터 구조 중 하나인 스택과 큐에 대해 알아보겠습니다. 두 데이터 구조 모두 요소를 저장하고 처리하는 방법에서 차이가 있으며, 특정 문제에 맞춰 선택적으로 사용할 수 있습니다. 본 강좌에서는 스택과 큐의 기본 개념, 이들을 활용한 알고리즘 문제 그리고 해당 문제의 코드를 C++로 구현하는 방법을 함께 살펴보겠습니다.
스택(Stack)
스택은 데이터를 저장하는 구조로 후입선출(Last In First Out, LIFO)를 원칙으로 합니다. 즉, 가장 나중에 들어온 데이터가 가장 먼저 나옵니다. 스택은 다음과 같은 두 가지 주요 연산을 지원합니다:
- push: 스택의 top에 데이터를 추가합니다.
- pop: 스택의 top에서 데이터를 제거하고 해당 데이터를 반환합니다.
스택의 활용 예시
스택은 괄호 검사, 세트의 역순 출력, 뒤로가기 기능을 구현하는데 유용하게 사용됩니다.
큐(Queue)
큐는 데이터를 저장하는 구조로 선입선출(First In First Out, FIFO)를 원칙으로 합니다. 즉, 가장 먼저 들어온 데이터가 가장 먼저 나갑니다. 큐도 주요 연산은 유사하게 다음과 같습니다:
- enqueue: 큐의 rear에 데이터를 추가합니다.
- dequeue: 큐의 front에서 데이터를 제거하고 해당 데이터를 반환합니다.
큐의 활용 예시
큐는 프린터 작업 관리, 프로세스 스케줄링, BFS(너비 우선 탐색) 알고리즘 구현 등에 사용됩니다.
문제: 올바른 괄호 문자열 확인하기
이번 문제는 스택을 활용하여 주어진 문자열 속의 괄호가 올바른지 검사하는 것입니다. 올바른 괄호 문자열의 정의는 다음과 같습니다:
- 모든 열린 괄호는 반드시 닫히는 괄호와 쌍을 이루어야 합니다.
- 열린 괄호가 닫히는 괄호보다 먼저 나오지 않아야 합니다.
문제 설명
문자열이 주어질 때, 이 문자열이 올바른 괄호 문자열인지 확인해야 합니다. 다음과 같은 경우에 “올바르다”고 말할 수 있습니다:
- “()”
- “(())”
- “()()”
- “(()(()))”
반대로 다음과 같은 경우는 “올바르지 않다”고 말할 수 있습니다:
- “)(“
- “(()”
- “())”
- “(()))”
풀이 과정
이 문제를 해결하기 위해 스택을 사용할 것입니다. 스택의 기본 원리를 통해 열린 괄호는 스택에 추가하고, 닫힌 괄호가 나오면 스택에서 열린 괄호를 pop하는 방식으로 진행합니다.
- 빈 스택을 생성합니다.
- 입력 문자열을 한 글자씩 읽습니다.
- 읽은 글자가 ‘(‘이면 스택에 push합니다.
- 읽은 글자가 ‘)’이면 스택이 비어있지 않은지 확인한 후, 스택에서 pop을 수행합니다. 스택이 비어있다면 잘못된 문자열입니다.
- 문자열을 모두 다 읽었을 때 스택이 비어 있다면 올바른 문자열입니다. 비어 있지 않다면 잘못된 문자열입니다.
C++ 코드 구현
위의 알고리즘을 구현한 C++ 코드는 다음과 같습니다:
#include
#include
#include
bool isValidParentheses(const std::string& str) {
std::stack s;
for (char c : str) {
if (c == '(') {
s.push(c);
} else if (c == ')') {
// 스택이 비어 있으면 잘못된 괄호
if (s.empty()) {
return false;
}
s.pop(); // 올바른 경우, 열린 괄호 제거
}
}
// 최종적으로 스택이 비어 있어야 올바르다
return s.empty();
}
int main() {
std::string input;
std::cout << "괄호 문자열을 입력하세요: ";
std::cin >> input;
if (isValidParentheses(input)) {
std::cout << "올바른 괄호 문자열입니다." << std::endl;
} else {
std::cout << "올바르지 않은 괄호 문자열입니다." << std::endl;
}
return 0;
}
결과 테스트
위의 코드를 사용하여 다양한 입력 문자열을 테스트할 수 있습니다. 예를 들어:
- 입력:
()– 출력: “올바른 괄호 문자열입니다.” - 입력:
(())– 출력: “올바른 괄호 문자열입니다.” - 입력:
())– 출력: “올바르지 않은 괄호 문자열입니다.” - 입력:
(()))– 출력: “올바르지 않은 괄호 문자열입니다.”
정리 및 팁
스택과 큐는 다양한 알고리즘 문제에서 중요한 역할을 수행합니다. 스택은 주로 LIFO 구조가 필요한 문제에, 큐는 FIFO 구조가 필요한 문제에 사용됩니다. 본 강좌에서 논의한 문제 해결 과정을 통해 스택을 보다 효과적으로 활용하는 방법을 익혔기를 바랍니다.