스택 활용 가능성 대표 알고리즘 요약

 

스택(Stack)은 데이터 구조에서 후입선출(LIFO) 원칙을 따르는 중요한 개념입니다. 본 글에서는 스택을 활용하여 해결할 수 있는 대표적인 알고리즘과 문제 해결 방법을 소개합니다.

스택이 중요한 이유와 활용 가능성

스택(Stack)은 후입선출(LIFO, Last In First Out) 원칙을 따르는 기본적인 자료구조 중 하나입니다. 이 데이터 구조는 다양한 알고리즘 문제 해결에 필수적으로 활용되며, 재귀 호출, 괄호 검사, 문자열 처리, 그래프 탐색 등 여러 분야에서 사용됩니다. 특히, 스택은 **웹 브라우저의 뒤로 가기/앞으로 가기**, **텍스트 편집기의 Undo/Redo 기능**, **호출 스택(Call Stack) 관리** 등에 널리 쓰이고 있습니다. 이 글에서는 스택을 활용한 대표적인 알고리즘과 이를 해결하는 방법을 자세히 살펴보겠습니다.

 

스택을 활용한 대표적인 알고리즘

1. 괄호 검사(Valid Parentheses)

괄호의 짝이 맞는지를 검사하는 문제는 스택을 활용하면 쉽게 해결할 수 있습니다. 문제 예시: **"({[()]})"**는 올바른 괄호 쌍이지만, **"({[}])"**는 올바르지 않습니다.

알고리즘

• 열린 괄호((, {, [)가 나오면 스택에 push
• 닫힌 괄호(), }, ])가 나오면 스택에서 pop 하여 짝이 맞는지 확인
• 검사가 끝난 후 스택이 비어 있으면 유효한 괄호 문자열

Python 코드 예제

def isValid(s):
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

2. 중위 표기법(Infix) → 후위 표기법(Postfix) 변환

수학 표현식을 연산자 우선순위를 고려하여 후위 표기법으로 변환하는 데 스택이 사용됩니다.

알고리즘

• 피연산자는 출력
• 연산자는 스택에 push (우선순위를 고려하여 pop)
• 왼쪽 괄호는 스택에 push, 오른쪽 괄호를 만나면 왼쪽 괄호를 만날 때까지 pop

Python 코드 예제

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    output = []
    stack = []
    
    for char in expression:
        if char.isalnum():  # 피연산자
            output.append(char)
        elif char in precedence:
            while stack and precedence.get(stack[-1], 0) >= precedence[char]:
                output.append(stack.pop())
            stack.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()
    
    while stack:
        output.append(stack.pop())
    
    return ''.join(output)

3. 깊이 우선 탐색(DFS, Depth First Search)

그래프 탐색 알고리즘 중 하나인 깊이 우선 탐색(DFS)은 재귀적으로 구현할 수도 있지만, 스택을 활용한 반복문으로도 구현할 수 있습니다.

알고리즘

• 시작 노드를 스택에 push
• 스택에서 pop하여 방문
• 방문하지 않은 인접 노드를 스택에 push

Python 코드 예제

def dfs(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=" ")
            visited.add(node)
            stack.extend(graph[node])  # 인접 노드 추가

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs(graph, 'A')

4. 웹 브라우저의 뒤로 가기/앞으로 가기 구현

웹 브라우저에서 방문한 페이지의 기록을 관리하는 데 스택이 활용됩니다.

알고리즘

• 사용자가 새로운 페이지를 방문하면 현재 페이지를 뒤로 가기(Back) 스택에 push
• 뒤로 가기 버튼을 누르면 뒤로 가기 스택에서 pop 하고, 앞으로 가기(Forward) 스택에 push
• 앞으로 가기 버튼을 누르면 앞으로 가기 스택에서 pop하여 현재 페이지로 이동

Python 코드 예제

class BrowserHistory:
    def __init__(self, homepage):
        self.back_stack = []
        self.forward_stack = []
        self.current_page = homepage

    def visit(self, url):
        self.back_stack.append(self.current_page)
        self.current_page = url
        self.forward_stack.clear()

    def back(self):
        if self.back_stack:
            self.forward_stack.append(self.current_page)
            self.current_page = self.back_stack.pop()
        return self.current_page

    def forward(self):
        if self.forward_stack:
            self.back_stack.append(self.current_page)
            self.current_page = self.forward_stack.pop()
        return self.current_page

 

스택을 활용한 알고리즘 요약

스택은 다양한 문제 해결에 필수적으로 활용되는 자료구조입니다. 특히 다음과 같은 알고리즘에서 유용하게 사용됩니다.

• 괄호 검사: 문자열의 올바른 괄호 짝을 검사
• 중위 → 후위 표기법 변환: 연산자 우선순위를 고려하여 변환
• 깊이 우선 탐색(DFS): 그래프 탐색을 위한 효율적인 방법
• 웹 브라우저 뒤로 가기/앞으로 가기: 방문 기록을 관리하는 시스템

스택을 활용한 다양한 문제를 연습하면 알고리즘 문제 해결 능력을 더욱 향상할 수 있습니다. 실제 코딩 테스트에서도 자주 등장하는 개념이므로 적극적으로 활용해 보세요!