파이썬 코딩테스트 강좌, 스택과 큐

1. 서론

프로그래밍을 배우는 데 있어 가장 기본적인 자료구조 중 두 가지는 스택과 큐입니다. 이 자료구조들은 각각 고유의 일관된 작동 방식을 가지고 있으며, 다양한 알고리즘 문제에서 자주 사용됩니다. 이 글에서는 스택과 큐의 개념을 설명하고, 이들을 활용하여 해결할 수 있는 알고리즘 문제를 다룰 것입니다.

2. 스택(Stack)

스택은 후입선출(LIFO, Last In First Out) 구조를 가진 자료구조입니다. 가장 최근에 삽입된 데이터가 가장 먼저 삭제되는 방식입니다. 스택의 주요 연산으로는 다음과 같은 것이 있습니다:

push(item): 스택의 맨 위에 item을 추가합니다.
pop(): 스택의 맨 위에 있는 아이템을 제거하고 반환합니다.
peek(): 스택의 맨 위에 있는 아이템을 반환하되 제거하지 않습니다.
is_empty(): 스택이 비어있으면 True, 그렇지 않으면 False를 반환합니다.

3. 큐(Queue)

큐는 선입선출(FIFO, First In First Out) 구조를 가진 자료구조입니다. 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 방식입니다. 큐의 주요 연산은 다음과 같습니다:

enqueue(item): 큐의 끝에 item을 추가합니다.
dequeue(): 큐의 맨 앞에 있는 아이템을 제거하고 반환합니다.
peek(): 큐의 맨 앞에 있는 아이템을 반환하되 제거하지 않습니다.
is_empty(): 큐가 비어있으면 True, 그렇지 않으면 False를 반환합니다.

4. 알고리즘 문제 설명

이번에 우리가 풀어볼 문제는 스택과 큐를 활용한 괄호의 유효성 검사입니다. 문제는 다음과 같습니다:

주어진 문자열이 괄호로만 이루어져 있을 때, 괄호가 올바르게 닫히는지를 확인하는 함수를 작성하시오. 올바른 괄호 표현은 모든 열린 괄호가 올바르며 각각의 닫힌 괄호가 열린 괄호와 짝이 맞아야 합니다.

입력

입력은 하나의 문자열로 주어지며, 이 문자열은 다음 괄호들로 이루어질 수 있습니다:

‘(‘
‘)’
‘{‘
‘}’
‘[‘
‘]’

출력

모든 괄호가 올바르게 닫혀 있으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

5. 문제 풀이 과정

이 문제를 해결하기 위해 스택을 사용할 것입니다. 입력된 문자열을 한 글자씩 처리하면서 열린 괄호는 스택에 추가하고, 닫힌 괄호가 등장할 때 스택에서 열린 괄호와 매칭되는지를 확인합니다. 다음은 문제를 해결하는 과정입니다:

단계 1: 스택 초기화

문자열의 각 문자를 순회하기 위해 빈 리스트를 이용한 스택을 초기화합니다.

단계 2: 괄호 매핑 설정

열린 괄호와 닫힌 괄호의 관계를 정의하기 위해 딕셔너리를 만듭니다.

단계 3: 문자열 순회

문자열을 한 글자씩 순회하면서 열린 괄호일 경우 스택에 추가합니다. 닫힌 괄호일 경우 스택의 맨 위의 요소와 매칭하여 확인합니다.

단계 4: 스택 상태 확인

문자열 순회가 끝난 후, 스택에 남아있는 내용물이 없다면 모든 괄호가 올바르게 닫힌 것입니다.

파이썬 코드 구현


def is_valid_parentheses(s: str) -> bool:
    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  # 스택이 비어있으면 True, 그렇지 않으면 False

단계별 설명

이제 각 단계에 대해 좀 더 자세히 설명하겠습니다.

스택 초기화

“stack = []“로 스택을 빈 리스트로 초기화합니다. 스택은 괄호들이 올바른 순서로 열리고 닫히는지 확인하는 데 사용됩니다.

괄호 매핑 설정

“mapping = {“)”: “(“, “}”: “{“, “]”: “[“}“와 같이 딕셔너리를 생성하여 각 닫힌 괄호에 대한 매칭 열린 괄호를 정의합니다. 이 매핑은 닫힌 괄호를 만났을 때, 스택의 맨 위의 요소와 비교하는 데 사용됩니다.

문자열 순회

문자열을 for 루프를 사용하여 한 문자씩 순회합니다. 만약 문자가 닫힌 괄호라면 스택에서 요소를 꺼내서 매핑된 열린 괄호와 비교합니다. 만약 열었다가 닫힌 괄호가 매칭되지 않는다면, 유효하지 않으므로 False를 반환합니다. 만약 문자가 열린 괄호라면, 스택에 추가합니다.

스택 상태 확인

완전 순회 후 스택이 비어있다면 모든 열린 괄호가 올바르게 닫혔다고 할 수 있습니다. 따라서 return not stack는 스택이 비어있으면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

6. 결론

이번 강좌에서는 스택과 큐의 기본 개념을 먼저 살펴보고, 스택을 활용한 괄호 유효성 검사 문제를 해결하는 과정을 다뤘습니다. 스택은 후입선출의 구조로 다양한 알고리즘 문제에 유용하게 사용되며, 이를 이해하고 활용하는 것은 코딩 테스트를 준비하는 데 매우 중요합니다.

큐 또한 중요한 자료 구조로, FIFO 방식으로 작동하여 많은 문제에 적용할 수 있습니다. 스택과 큐는 코딩 문제를 푸는 기초로, 이러한 자료 구조를 잘 이해하고 활용하는 것이 자주 요구됩니다. 이 글에서 다룬 내용을 바탕으로 더 많은 문제를 풀어보며 실력을 쌓아나가길 바랍니다.