[컴퓨팅 사고력]블록쌓기 게임으로 스택 구조 이해하기

강의자료/알고리즘 수학

원당컴1 2021. 1. 11. 08:58

두 사람이 각각 하나의 블록을 쌓거나 내려 놓을 수 있는 놀이를 한다고 가정할 때 두 사람이 만들어 낼 수 있는 블록 모양을 생각해 보자.

각 블록에는 수가 쓰여져 있으며 이 수들은 절대 두번 이상 나오니 않는다.

또한 두 사람은 블록에 쓰여진 수에 따라 차례대로 쌓을 수 있으며 한번 쌓여진 블록은 다음 사람에 이해서 내려지면 다시는 사용할 수가 없다.

다음 블록의 모양을 보고 두 사람이 어떻게 블록을 쌓아 올라갔는지 생각해 보자.

가) 의 경우는 두사람이 차례대로 1,2,3,4 를 쌓아 올린 것이다.

나) 의 경우에는 첫번째 사람이 1을 올리고 두번째 사람이 2를 올린것을 첫번째 사람이 2를 내린 후 두번째 사람이 3을 올리고 첫번째 사람이 4를 올렸음을 알 수 있다.

즉 첫번째 사람은 1,4를 올리고 2를 내렸으며 두번째 사람으 2,3을 올렸음을 알 수 있다.

이와 같이 위쪽에서만 쌓고 내리기가 가능한 즉,가운데 블록을 임의로 내릴 수 없는 구조를 스택(Stack)이로가 한다. 이러한 구조는 나중에 들어간 것이 먼저 나오는 구조라고 해서 후입선출 이라고 하며 LIFO(Last In First Out) 이라고도 한다.

이러한 유형의 문제는 과거의 정보올림피아드 기출문제에서 찾아 볼 수 있는데 다음과 같은 유형의 문제로 출제 된바 있다.

- 2005년에 출제된 문제 유형을 살펴 보자.

이 문제의 정답은 1,2,3 을 넣고 두개를 빼면 3,2 가 빠져서 스택에 1이 있는 상태에서 4,5를 넣은 후 빼 내었기 때문에 나온 순서는 3,2,5,4,1 이 될것이다.

- 2009년에는 다음과 같은 형태로 출제된 적이 있다.

2005년도에 나온 유형의 문제와 동일한 것을 확인 할 수가 있다.

역시 1,2,3 을 넣고 3,2 를 뺀 다음 4,5,6을 넣으면 스택에 1,4,5,6 이 있는 상태에서 6,5 를 뺀 후 7을 넣으면 1,4,7이 남아 있다. 여기서 스택의 모든 수를 빼 낸다고 하면 마지막에는 1이 나올것이고 마지막에서 두번째는 4가 나올것이다.

이렇게 스택에 대해서 직관적으로 나온것은 2010년 이전에 두번 정도 나왔지만 그 이후에는 이렇게 직관적인 형태의 스택 문제가 출제 된 적은 없다.

하지만 알고리즘을 공부하는 학생들이라면 이러한 스택 문제에 대해서는 기본으로 알고 가야 하는 자료 구조 형이다.

이러한 자료구조를 이용한 알고리즘 문제로는

등의 문제를 직접 구현해 볼 수 있다.

이러한 문제들을 풀다 보면 스택이 아닌 이중 반복문으로 해결 하다 보면 시간 초과가 발생하는 것을 확인할 수 있다.

하지만 이중반복이 아닌 스택이라면 데이터 횟수 만큼만 반복하는 O(n) 의 시간으로 해결이 되는 것을 확인 할수가 있다.

따라서 이러한 스택 구조를 이해하고 활용한다면 생활속의 아이디어를 프로그램으로 구현할때 좀더 빠른 시간에 해결 가능한 프로그램을 만들지 않을까 생각이 든다.

오늘도 최선을 다하는 우리 학생들을 응원합니다.

인천 서구 원당컴퓨터학원

검단신도시 코딩/컴퓨터기초/컴퓨터자격증/C++/JAVA/Python/정보올림피아드 전문 학원

원당컴퓨터학원