CS(Computer Science) 학위가 없다면 뭔가 놓치고 있는 것 같은 느낌이 들 수도 있습니다...
또는 CS가 너무 추상적이어서 유용하다고 느낄 수도 있습니다...
아니면 Ruby가 이미 당신을 위해 모든 노력을 기울이고 있다는 것을...
어쨌든…
해시, 스택 및 대기열과 같은 데이터 구조의 기본 사항을 이해하면 도움이 됩니다.
이 게시물에서 :
Ruby에서 스택을 사용하는 방법을 알게 될 것입니다.
바로 실천에 옮길 수 있는 실용적인 컴퓨터 과학 개념!
Ruby의 스택 이해
Ruby에서 스택이란 무엇입니까?
스택은 "할 일" 목록으로 사용할 수 있는 데이터 구조입니다. 스택에서 요소를 계속 가져와 스택이 비어 있을 때까지 처리합니다.
다음은 시각적 표현입니다.
5를 빈 스택에 넣습니다. :
5
3을 스택에 푸시 :
3
5
스택에 9 푸시 :
9
3
5
더미에서 항목 1개 가져오기 :
3
5
여기서 주목해야 할 가장 큰 점은 새 항목이 스택 맨 위에 추가된다는 것입니다. . LIFO(후입선출) 방식입니다. 즉, 스택에서 항목을 가져오면(팝) 스택에 푸시된 마지막 항목이 됩니다.
이것이 어떻게 작동하는지 시각화하는 또 다른 방법은 접시 더미에 대해 생각하는 것입니다. 한 접시를 다른 접시 위에 올려 놓으면 윗 접시를 먼저 꺼내지 않고는 아랫 접시를 꺼낼 수 없습니다.
그것이 스택으로 하는 모든 것, 물건을 맨 위로 밀어 올리거나 튀어나온 것입니다. 색인 생성이 없습니다. .
이것을 어떻게 사용할 수 있는지에 대한 몇 가지 코드 예제를 살펴보겠습니다.
스택을 사용하여 배열을 병합하는 방법
스택의 고전적인 예는 스택을 사용하여 배열을 평면화하는 것입니다. 즉, 다차원 배열을 1차원 배열로 변환합니다.
예시 :
arr = [1,2,3,[4,5],6] arr.flatten
Ruby에는 이를 수행하는 flat 메서드가 있습니다. 하지만 이 방법이 없다면? 그리고 이 방법은 어떻게 작동합니까?
이것이 스택이 필요한 곳입니다!
Ruby는 푸시 앤 팝 방식을 구현합니다. , 그래서 우리는 배열을 스택처럼 다룰 수 있습니다.
<블록 인용>
참고:둘 다 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]
pop을 사용하기 때문에 이제 each 올바른 순서로 평평한 배열을 얻고 있습니다... 하지만 그 반대입니다.
이것은 스택의 흥미로운 속성을 보여줍니다. :
어떤 목록을 입력하든 동일한 순서로 돌아오지만 역순입니다.
<블록 인용>
팁:Array#flatten 이 메서드는 제거하려는 중첩 레이어 수(기본적으로 모든 레이어)를 정의할 수 있는 인수를 사용합니다.
대괄호 문제 풀기
여기에 또 다른 예가 있으며 이를 수행하는 동등한 Ruby 메서드가 없습니다!
컴퓨터 과학의 또 다른 고전적인 문제이기도 합니다...
이름:
균형 잡힌 괄호 일치
아이디어는 문자열이 주어지고 괄호가 유효한지 확인해야 한다는 것입니다.
예를 들어 수학 평가 프로그램을 작성한다고 가정해 보겠습니다. 입력을 처리하기 전에 입력이 유효한지 확인하고 싶습니다.
예 (유효한 입력):
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(방향)
이것을 적용하는 방법을 확실히 이해하기 위해 한 가지 더 예를 드십시오.
이 경우 우리는 일련의 방향을 제시하고 여행자의 시간을 절약하기 위해 이를 최적화해야 한다고 말합니다.
다음은 예시 세트입니다:
["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
결론
새로운 것을 배우고 스택을 사용하여 프로그래밍 문제를 해결하는 방법을 찾기 시작하셨기를 바랍니다.
이 게시물을 공유하는 것을 잊지 마세요. 더 많은 사람들이 이 글을 읽을 수 있도록!