2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/알고리즘 수학

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

원당컴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년에 출제된 문제 유형을 살펴 보자.

2005년도 정보올림피아드 기출문제에서 발췌

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

 

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

2009년도 정보올림피아드 기출문제에서 발췌

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

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

 

 

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

 

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

 

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

불쾌한 날 - http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=3020

빌딩 - http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=607&sca=3020

탑 - http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1082&sca=3020

히스토그램 - http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=497&sca=3020

 

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

 

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

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

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

 

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

 

인천 서구 원당컴퓨터학원

사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기