Tagged: Stack 알고리즘

Stack 알고리즘.

스택(Stack) 알고리즘.

흔희들 스택(Stack) 알고리즘을 가장 단순한 것으로 생각한다. 아니 다시말해서 가장 단순한 것으로 생각한 나머지 별 할일 없는 알고리즘으로까지 치부하는게 문제다. 하지만 스택 알고리즘은 가장 단순하면서 그 단순함으로 인해서 가장 강력하고 널리쓰이는 알고리즘이다.

스택(Stack) 을 말할때에 가장 먼저 떠오르는 것이 LIFO 다. Last-In First-Out. 가장 나중에 들어간 데이터가 가정 먼저 나온다는 것을 영어로 표현한 것인데, 이것을 다른 관점에서 생각해보면 역정렬 알고리즘에 일종이기도 하다.

reverse_order
Figure1. Reverse Order by Stack

스택에 넣었다 꺼내면 역정렬된 상태가 된다.

이를 잘 활용할 수 있는 것이 있는데, 진수 변환이다. 10진수를 2진수로 진수 변환할때를 보자.

Stack 알고리즘
Figure2. Stack 알고리즘

중학교때 배웠던 10진수를 2진수로 만드는 수학 방법이다. 이것을 자세히 보면 나머지로 나오는 것들을 스택에쌓아두고 역으로 뽑아내면 그것이 바로 이진수가 된다는 사실을 알 수 있다.

스택의 또 다른 용법에는 체커(Checker) 도 있다.

위는 간단한 PHP문법이다. PHP는 함수를 사용하거나 조건문과 같은 문법을 사용할때에 ‘{‘ 를 사용한다. ‘{‘ 로 열고 ‘}’로 닫는 식이다. 그래서 항상 쌍으로 존재하는데, PHP 컴파일러는 이러한 것이 오류가 없는지를 어떻게 체크를 할까?

다음과 같이 스택을 이용하면 간단히 체크할 수 있다.

Stack 의 괄호 체크.
Figure3. Stack 의 괄호 체크.

처음에 ‘{‘ 를 만나면 스택에 넣는다. 그리고 ‘}’를 만나면 스택에서 제거한다. 최종적으로 더 이상 빼내야할 ‘{‘ 이 없고 스택이 텅 비어있다면 PHP 컴파일러는 문법으로 쓰이는 ‘{‘ 가 제대로 사용되었다라고 판단한다. 그래서 위 PHP의 예제를 스택을 이용해서 체크해보면 ‘{‘ 가 스택에 하나 남게되어 PHP 문법에 오류가 있다는 것을 알 수 있다.