컴퓨터 과학(CS) 전공자가 아니라면 뭔가 놓치고 있다는 느낌이 들 수 있습니다...
또는 CS가 너무 추상적이라 실용성이 없다고 생각할 수도 있고...
Ruby가 이미 어려운 작업을 모두 대신 처리해준다고 믿을 수도 있죠.
어느 쪽이든...
해시, 스택, 큐 같은 자료구조의 기본 개념을 이해하는 것은 분명 큰 도움이 됩니다.
이 글에서 다룰 내용:
Ruby에서 스택을 활용하는 방법을 알아봅니다.
지금 바로 실전에 적용할 수 있는 실용적인 컴퓨터 과학 개념입니다!
Ruby에서 스택 이해하기
Ruby에서 스택(stack)이란 무엇일까요?
스택은 "할 일 목록"처럼 사용할 수 있는 자료구조입니다. 스택에서 요소를 하나씩 꺼내 처리하고, 스택이 빌 때까지 이 과정을 반복합니다.
시각적으로 표현하면 다음과 같습니다.
빈 스택에 5를 넣기(push):
5
스택에 3을 넣기:
3
5
스택에 9를 넣기:
9
3
5
스택에서 하나 꺼내기(pop):
3
5
여기서 주목해야 할 핵심은 새로운 요소가 스택의 맨 위(top)에 추가된다는 점입니다. 즉, "후입선출(LIFO, Last-In First-Out)" 방식으로 동작합니다. 스택에서 요소를 꺼낼 때(pop)는 마지막에 넣었던 요소가 가장 먼저 나옵니다.
접시 더미를 떠올리면 이해하기 쉽습니다. 접시를 하나씩 쌓아 올리면, 맨 아래 접시를 꺼내려면 그 위에 쌓인 접시들을 먼저 치워야 하죠.
스택으로 할 수 있는 작업은 결국 이것이 전부입니다. 맨 위에 요소를 넣거나(push), 맨 위에서 꺼내는(pop) 것뿐입니다. 인덱싱은 불가능합니다.
그럼 실제 코드 예제를 통해 스택이 어떻게 활용되는지 살펴보겠습니다.
스택으로 배열 평탄화(Flatten)하기
스택의 대표적인 활용 예는 배열을 평탄화(flatten)하는 것입니다. 즉, 다차원 배열을 1차원 배열로 변환하는 것이죠.
예제:
arr = [1,2,3,[4,5],6] arr.flatten
Ruby에는 이 작업을 대신 처리해주는 flatten 메서드가 있습니다. 하지만 만약 이 메서드가 없다면 어떻게 될까요? 그리고 이 메서드는 내부적으로 어떤 원리로 동작할까요?
바로 여기서 스택이 등장합니다!
Ruby는 push와 pop 메서드를 제공하기 때문에, 배열을 스택처럼 다룰 수 있습니다.
참고:
push와<<는 사실상 같은 메서드입니다. 이 글의 코드 예제에서는<<를 사용하겠습니다.
핵심 아이디어는 모든 요소를 순회하면서 해당 요소가 배열인지 아닌지 확인하는 것입니다. 배열이라면 그 안의 요소들을 다시 스택에 push합니다.
이렇게 하면 양파 껍질을 벗기듯 배열의 중첩 층이 계속 제거되고, 결국 남는 것은 평탄화된 배열입니다.
코드:
arr = [1,2,3,[4,5],6]
flat = []
arr.each do |thing|
if thing.is_a? Array
thing.each { |i| arr << i }
else
flat << thing
end
end
p flat
# [1, 2, 3, 6, 4, 5]
눈치채셨나요? 이 코드에는 pop 호출이 없습니다.
그 이유는 each가 스택에서 요소를 꺼내 알고리즘에 전달하는 역할을 대신 수행해주기 때문입니다. 또한 이 방식으로 처리하면 요소들의 원래 순서가 유지되지 않는다는 점도 주목하세요.
until과 empty?를 사용한 다른 버전도 있습니다:
until arr.empty?
thing = arr.pop
if thing.is_a? Array
thing.each { |i| arr << i }
else
flat << thing
end
end
p flat
# [6, 5, 4, 3, 2, 1]
이번에는 each에 맡기지 않고 직접 pop을 사용했습니다. 그 결과 올바른 순서대로 평탄화된 배열을 얻지만... 거꾸로 뒤집혀서 나옵니다.
여기서 스택의 흥미로운 특성이 드러납니다:
어떤 목록을 넣든, 같은 순서대로 나오지만 반대로 뒤집혀서 나온다는 것입니다.
팁:
Array#flatten메서드는 인자를 받아 몇 겹의 중첩까지 제거할지 지정할 수 있습니다(기본값은 모든 중첩 제거).
괄호 균형 검사 문제 풀기
또 다른 예제를 소개합니다. 이번에는 Ruby에 이 작업을 대신해주는 메서드가 없습니다!
컴퓨터 과학의 고전적인 문제이기도 하죠...
문제 이름은 바로:
균형 잡힌 괄호 검사(Matching Balanced Parenthesis)입니다.
문자열이 주어졌을 때, 그 안의 괄호가 유효한지 검증해야 합니다.
예를 들어 수식 계산 프로그램을 작성한다고 가정해봅시다. 본격적인 처리에 앞서 입력값이 유효한지 확인하고 싶을 것입니다.
예제 (유효한 입력):
input = "1 + (4 + 6) * 2"
예제 (잘못된 입력):
input = "1 + (4 + 6 * 2"
스택을 사용하면 입력 문자열에서 발견한 괄호를 추적할 수 있습니다. 그리고 닫는 괄호를 발견할 때마다 스택의 맨 위 요소와 비교하여 짝이 맞는지 확인하면 됩니다.
짝이 맞지 않는다면 그 입력은 유효하지 않다는 의미입니다.
예제:
PARENS = {
"(" => ")",
"{" => "}",
"[" => "]"
}
OPENING_PARENS = PARENS.keys
CLOSING_PARENS = PARENS.values
def valid_parentheses(string)
stack = []
string.each_char do |ch|
if OPENING_PARENS.include?(ch)
stack << ch
elsif CLOSING_PARENS.include?(ch)
ch == PARENS[stack.last] ? stack.pop : (return false)
end
end
stack.empty?
end
p valid_parentheses("(){}[]") # true
p valid_parentheses("[(])") # false
또 한 가지 눈여겨볼 점은 valid_parentheses 메서드가 stack.empty?로 끝난다는 것입니다. 닫히지 않은 채 남아있는 괄호가 없는지 확인하기 위함입니다.
모든 괄호가 올바르게 닫혔다면 스택은 비어 있어야 합니다 🙂
예제 3: 방향 데이터 최적화
마지막 예제를 통해 개념을 확실히 익혀보겠습니다.
이번에는 일련의 방향(directions) 데이터가 주어지고, 여행자의 시간을 절약할 수 있도록 이를 최적화해야 합니다.
예제 데이터:
["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
북쪽으로 갔다가 남쪽으로 가면 결국 제자리로 돌아온다는 것을 알 수 있습니다(양방향 거리가 같다고 가정). 이것이 우리가 최적화해야 할 부분이며, 스택을 사용하면 간단히 해결할 수 있습니다.
예제:
input = ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]
directions = []
opposites = {
"NORTH" => "SOUTH",
"SOUTH" => "NORTH",
"EAST" => "WEST",
"WEST" => "EAST"
}
input.each do |dir|
opposites[dir] == directions.last ? directions.pop : directions << dir
end
p directions
마무리
이 글을 통해 새로운 것을 배웠기를 바랍니다. 앞으로 프로그래밍 문제를 마주할 때 스택을 활용해 해결할 방법을 적극적으로 찾아보시길 권합니다.
더 많은 사람들이 이 글을 읽을 수 있도록 글 공유도 잊지 마세요!