반응형

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

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

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

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

가) 의 경우는 두사람이 차례대로 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 | 사이버몰의 이용약관 바로가기
Posted by 파아란기쁨 트랙백 0 : 댓글 9

댓글을 달아 주세요

  1. addr | edit/del | reply 드래곤포토 2021.01.11 11:39 신고

    stack 구조를 잘 설명하셨네요
    활기찬 월요일 되세요 ^^

  2. addr | edit/del | reply 가족바라기 2021.01.12 00:02 신고

    저같은 사람도 이해할수 있을것 같아요

  3. addr | edit/del | reply 핑구야날자 2021.01.12 06:49

    블럭 쌓기 게임으로 스택 구조를 좀 더 쉽게 이해할 수 있겠군요

  4. addr | edit/del | reply 空空(공공) 2021.01.12 08:30 신고

    원리를 알면 문제 풀이가 쉽습니다^^

  5. addr | edit/del | reply Deborah 2021.01.12 10:20 신고

    자세히 설명해 주시니 알것 같아요. 재미 있네요.

  6. addr | edit/del | reply 휴식같은 친구 2021.01.12 11:54 신고

    스택하면 first in first out이 생각납니다.ㅎ
    잘 보고 갑니다~ 즐거운 하루 보내세요

  7. addr | edit/del | reply *저녁노을* 2021.01.12 16:13 신고

    좋은 날 되세요.

    잘 보고가요

  8. addr | edit/del | reply 청결원 2021.01.12 18:41

    포스팅 잘 보고 갑니다
    눈내리는 저녁이네요...
    미끄럼 조심하시고건강 유의 하세요~

  9. addr | edit/del | reply 라드온 2021.01.13 07:01 신고

    21년에 정규과목에 SW코딩이 편입된 것 같은데, 원당컴이 엄청 흥하리라 생각합니다. 화이팅!