서론
안녕하세요! 이번 강좌에서는 C#을 사용하여 스택과 큐를 활용한 알고리즘 문제를 풀어보겠습니다.
스택과 큐는 컴퓨터 과학에서 가장 기본적이고 중요한 데이터 구조 중 하나로, 다양한 알고리즘 문제를 해결하는 데 널리 사용됩니다.
이 강좌를 통해 스택과 큐의 기본 개념을 이해하고 실제 코딩 테스트에서 자주 출제되는 문제를 풀면서
이 두 가지 구조에 대한 깊은 이해를 심화할 수 있길 바랍니다.
스택(Stack)과 큐(Queue)의 기본 개념
스택은 후입선출(LIFO, Last In First Out) 구조를 가지며, 마지막에 들어온 데이터가 가장 먼저 나갑니다.
큐는 선입선출(FIFO, First In First Out) 구조를 가지고 있으며, 가장 먼저 들어온 데이터가 가장 먼저 나갑니다.
이 두 가지 구조는 다양한 프로그래밍 문제를 해결하는 데 있어서 중요하게 사용됩니다.
문제: 괄호 균형 검사하기
문제 설명: 주어진 문자열에서 같은 종류의 괄호가 올바르게 열리고 닫혔는지 검사하는 함수를 작성하세요.
올바른 괄호의 예는 “()[]{}”, 그리고 잘못된 괄호의 예는 “(]”, “([)]”입니다.
입력
- 문자열 s (1 <= s.length <= 100) – 소문자 및 대문자, 숫자와 괄호로 이루어져 있습니다.
출력
- 모든 괄호가 올바르게 열리고 닫히면 true를, 아니면 false를 반환합니다.
예제
입력: s = "()"
출력: true
입력: s = "([)]"
출력: false
문제 풀이 과정
이 문제를 풀기 위해 스택 자료구조를 사용할 것입니다. 스택에 열린 괄호를 푸시(push)하고 닫힌 괄호가 나올 때마다
스택의 최상위 요소와 비교하여 올바른 괄호인지 검사할 것입니다.
과정은 다음과 같습니다:
- 괄호의 쌍을 저장하는 맵을 생성합니다. 예를 들어, { ‘)’: ‘(‘, ‘]’: ‘[‘, ‘}’: ‘{‘ }과 같이 정의합니다.
- 스택을 초기화합니다.
- 문자열을 하나씩 순회합니다.
- 만약 현재 문자가 열린 괄호라면 스택에 푸시합니다.
- 닫힌 괄호라면 스택이 비어 있는지 확인하고, 비어 있지 않다면 스택의 최상위 요소와 매칭되는지 검사합니다.
- 문자열을 모두 순회한 후, 스택이 비어 있다면 true, 아니라면 false를 반환합니다.
C# 코드 구현
using System;
using System.Collections.Generic;
public class Solution
{
public bool IsValid(string s)
{
// 괄호 쌍을 저장하는 딕셔너리
Dictionary<char, char=""> parentheses = new Dictionary<char, char="">()
{
{ ')', '(' },
{ ']', '[' },
{ '}', '{' }
};
Stack stack = new Stack(); // 스택 초기화
foreach (char c in s)
{
if (parentheses.ContainsKey(c)) // 닫힌 괄호인지 확인
{
// 스택이 비어있거나 최상위 요소가 맞지 않으면 false
if (stack.Count == 0 || stack.Pop() != parentheses[c])
{
return false;
}
}
else // 열린 괄호인 경우
{
stack.Push(c); // 스택에 푸시
}
}
return stack.Count == 0; // 스택이 비어있으면 true 반환
}
}
</char,></char,>코드 설명
위의 코드는 문자열 `s`를 입력받아 괄호의 균형을 검사하는 함수 `IsValid`를 정의합니다.
먼저, 괄호 쌍을 정의하고, 스택을 초기화합니다. 그 후, 입력된 문자열을 순회하며 열린 괄호는 스택에 푸시하고,
닫힌 괄호에 대해서는 스택의 최상위 요소와 비교하여 올바른 매칭인지 확인합니다.
모든 문자를 확인한 후 스택이 비어 있다면 모든 괄호가 올바르게 열리고 닫힌 것으로 판단하여 true를 반환합니다.
추가 예제
예제 1
입력: s = "{[]}"
출력: true
설명: ‘{‘로 시작해서 ‘}’로 끝나며, 중간에 ‘[‘와 ‘]’가 올바르게 매칭되어 있습니다.
예제 2
입력: s = "({[})"
출력: false
설명: ‘(‘가 열린 후 ‘]’가 바로 나오므로 올바른 쌍이 아닙니다.
복습 문제
이번 강좌에서는 스택을 활용하여 괄호 균형 검사 문제를 풀어보았습니다.
여러분이 이제 스택과 큐에 대해 좀 더 잘 이해할 수 있게 되었겠길 바랍니다.
다음으로 시도해볼 만한 문제는 “스택을 이용해 큐 구현하기”입니다.
이는 스택의 기본 개념과 그 활용을 더욱 깊이 있게 배울 수 있는 문제입니다.
직접 구현해보고, 코드를 작성해보시길 추천드립니다!
결론
스택과 큐는 알고리즘 및 프로그래밍에서 매우 중요한 자료 구조입니다.
이 두 가지 자료 구조를 활용하여 해결할 수 있는 문제의 종류는 많습니다.
이번 강좌가 여러분이 향후 프로그래밍 문제를 푸는 데 많은 도움이 되었기를 바랍니다!
계속해서 스택과 큐의 활용을 공부해보세요.