프로그래밍에서 괄호 쌍은 일반적으로 많이 사용되는 구문 중 하나입니다. 괄호 쌍을 찾는 방법에는 스택(Stack)을 활용하는 방법이 일반적으로 사용됩니다. 스택은 후입선출(LIFO, Last-In-First-Out) 구조로, 괄호를 입력받으면 스택에 쌓고, 닫는 괄호를 만날 때마다 해당 열린 괄호를 스택에서 pop합니다. 이를 통해 모든 괄호가 정상적으로 쌍을 이루는지 확인할 수 있습니다. 이러한 방법을 사용하여 괄호 쌍을 찾을 수 있습니다. 아래 글에서 자세하게 알아봅시다.
스택을 활용한 괄호 쌍 찾기
1. 스택(Stack)이란?
스택은 후입선출(Last-In-First-Out) 구조를 가지는 자료구조로, 데이터를 쌓아 올리는 것에 적합합니다. 스택은 배열(Array)이나 연결리스트(Linked List)를 이용하여 구현할 수 있습니다. 스택은 요소를 삽입하는 연산을 push라고 하며, 요소를 꺼내는 연산을 pop이라고 합니다. 스택의 가장 상단에 위치한 요소를 top이라고 하며, 스택이 비어있을 때에는 top을 가리키는 포인터가 없습니다.
2. 괄호 쌍 찾기 알고리즘
괄호 쌍을 찾기 위해서는 스택을 활용하여 입력된 문자열을 탐색해야 합니다. 알고리즘의 동작은 다음과 같습니다.
- 문자열을 순회하며, 열린 괄호를 스택에 push합니다.
- 닫는 괄호를 만날 때마다 스택에서 가장 최근에 삽입된 열린 괄호를 pop합니다.
- 만약 닫는 괄호를 만나서 pop을 할 수 없는 상태라면, 괄호 쌍이 올바르지 않은 것으로 판단합니다.
- 문자열을 모두 탐색했을 때, 스택이 비어있으면 괄호 쌍이 올바르게 이루어진 것으로 판단합니다.
- 스택이 비어있지 않다면, 괄호 쌍이 올바르지 않은 것으로 판단합니다.
3. 예시
다음은 입력된 문자열의 괄호 쌍이 올바른지 판단하는 함수입니다. 스택을 사용하여 괄호 쌍을 찾습니다.
“`python
def check_parentheses(string):
stack = []
for ch in string:
if ch == ‘(‘ or ch == ‘[‘ or ch == ‘{‘:
stack.append(ch)
elif ch == ‘)’:
if not stack or stack.pop() != ‘(‘:
return False
elif ch == ‘]’:
if not stack or stack.pop() != ‘[‘:
return False
elif ch == ‘}’:
if not stack or stack.pop() != ‘{‘:
return False
return len(stack) == 0
“`
위의 함수를 이용하여 다음과 같이 괄호 쌍을 확인할 수 있습니다.
“`python
print(check_parentheses(“(())”)) # True
print(check_parentheses(“({[()]})”)) # True
print(check_parentheses(“(()))”)) # False
print(check_parentheses(“({[()]}”)) # False
“`
위의 예시에서는 문자열 “(())”와 “({[()]})”의 괄호 쌍이 올바르게 이루어져 있으므로 True를 반환하며, 문자열 “(()))”와 “({[()]}”의 괄호 쌍은 올바르게 이루어져 있지 않으므로 False를 반환합니다.
달바 괄사
마치며
위의 알고리즘을 이용하면 입력된 문자열의 괄호 쌍이 올바른지 간단하게 확인할 수 있습니다. 스택을 사용하여 열린 괄호를 push하고, 닫는 괄호를 만날 때마다 스택에서 pop하여 괄호 쌍을 확인합니다. 만약 열린 괄호를 찾을 수 없거나, 닫는 괄호와 매치되는 열린 괄호를 찾을 수 없는 경우에는 올바른 괄호 쌍이 아니라고 판단합니다. 스택을 사용하여 괄호의 짝을 찾는 것은 굉장히 효율적인 방법이며, 프로그래밍 문제나 자료구조 관련 문제에서 종종 활용되는 기법입니다.
추가로 알면 도움되는 정보
- 다른 종류의 괄호를 사용할 경우, if문을 추가하여 처리할 수 있습니다.
- 스택을 사용하여 괄호 쌍을 찾는 문제는 대표적인 프로그래밍 문제입니다. 유형을 익히고 연습하는 것이 중요합니다.
- 스택을 사용하여 다른 문제를 해결할 수도 있습니다. 예를 들어, 수식의 후위 표기법 계산이나 깊이 우선 탐색(DFS) 등의 문제에서 스택을 활용할 수 있습니다.
- 괄호 쌍 찾기 문제와 관련하여, 중첩된 구조를 해결할 수 있는 재귀 함수를 이용한 알고리즘도 고려해볼 수 있습니다.
- 스택을 활용하는 문제를 풀 때는 문제의 요구사항에 맞는 자료구조를 선택하고, 스택을 사용할 때의 시간 복잡도에 유의해야 합니다.
놓칠 수 있는 내용 정리
스택을 활용하여 괄호 쌍을 찾는 것은 매우 간단한 알고리즘입니다. 하지만 괄호 쌍을 찾을 때, 열린 괄호와 닫는 괄호의 순서나 짝을 올바르게 맞추는 것이 중요합니다. 스택을 사용하여 괄호를 확인할 때, 닫는 괄호를 만났을 때의 조건을 정확하게 설정하는 것이 중요합니다. 스택을 활용하여 괄호 쌍을 찾는 문제는 프로그래밍 알고리즘 문제에서 자주 출제되는 유형 중 하나이므로, 익숙해지는 것이 좋습니다.
