데이터 단순 처리하기 위해
들어온 순서대로 저장-출력
‘스택’은 마지막 자료가 먼저
‘큐’는 들어온 순서대로 처리


매년 세계 컴퓨터과학자 연구 평가 순위를 발표해 온 미국의 권위 있는 학술정보서비스 플랫폼 리서치닷컴(Research.com)의 2023년 순위(World Ranking of Top Computer Scientist in 2023)에 따르면 세계 상위 1000명의 컴퓨터과학자 리스트에 한국의 컴퓨터과학자는 한 명도 없었다고 합니다. 우리나라 1위는 세계 순위 1029위였는데요, 가까운 미래에 우리 학생들이 성장해 상위 랭킹에 이름을 올리길 바라며, 이번 지면에서는 컴퓨터과학자처럼 세상을 바라보는 방법에 대해 다루려고 합니다.

주제에 들어가기 전에 2017년 비버챌린지의 ‘공굴리기’라는 제목의 문제를 함께 볼까요. 공이 경사로를 따라 굴러가다 경사로 중간에 있는 구멍을 만나면 공이 들어가고, 핀을 당기면 구멍 안에 들어간 공들이 들어간 순서와 반대로 나옵니다. 경사로는 3개의 구멍 A, B, C가 있고 각각 3개, 2개, 1개의 공이 들어갈 만한 공간을 가지고 있습니다. 10개의 공이 전부 굴러간 다음 A, B, C의 순으로 핀을 당겨 구멍에 들어 있는 공들을 모두 꺼낼 때, 공들이 모두 바닥까지 굴러간 상태는 어느 것일까요.

이 문제는 컴퓨터과학에서 자주 사용되는 자료 구조의 하나인 스택(Stack)에 대해 학생들이 경험해 볼 수 있도록 하는 문제입니다. ‘쌓다’는 의미의 스택은 접시가 쌓여 있을 때 가장 위에 있는 접시, 즉 가장 나중에 쌓아 올린 접시부터 꺼내어 쓰게 되는 것처럼 스택에 저장된 데이터는 가장 나중에 들어간 것이 제일 먼저 나오는 자료 구조입니다.

가장 먼저 입력된 자료에는 가장 마지막에 접근하고, 가장 나중에 저장된 자료에는 가장 먼저 접근하도록 설계된 후입선출(Last In First Out) 형태로 추상화된 자료 구조를 스택이라고 합니다.

문제 상황에서 사용하기 위한 프로그램을 작성하기 위해서는 실세계의 다양한 자료들, 그리고 그 자료들의 관계를 표현하고 저장하는 것이 필요합니다. 자료 구조는 이러한 자료들 사이의 관계를 저장하기 위해 고안된 구조입니다. 현실 세계의 규칙을 추상화하는 자료 구조의 대표적인 예로 스택과 큐(Queue)가 있습니다. 이들은 일렬로 늘어선 선형(Linear) 구조로 특정한 순서에 따라 자료를 넣고 꺼낼 수 있습니다. 스택이 한쪽 끝에서만 자료를 넣고 꺼낼 수 있었다면, 큐는 한쪽 끝에서 자료를 넣고, 반대 쪽 끝에서 꺼낼 수 있는 선입선출(First In Last Out) 형태입니다. 학교에서 급식을 먹을 때나 놀이공원에서 줄을 설 때, 줄을 선 순서대로 배식 받거나 놀이기구를 타는 것이 큐의 동작과 같습니다.

스택과 큐 자료 구조는 우리가 사용하는 컴퓨터 프로그램의 어떤 작업에 사용되고 있을까요. 은행이나 병원 등에서 번호표를 뽑은 순서대로 먼저 호출하고, ARS 고객센터나 프린터 출력 등에서도 먼저 오면 먼저 처리하는 큐 구조로 표현할 수 있습니다. 큐는 순서대로 처리하는 것이라 현실 세계를 추상화할 때 자주 사용될 것이라는 것은 예상할 수 있겠죠.

그럼 스택은 어떨까요. 여러분이 인터넷 검색을 할 때 자주 사용하는 웹브라우저를 떠올려보세요. 스택이 과연 어디에 사용됐을까요. 대부분의 웹브라우저에는 ‘뒤로 가기’ 기능이 있습니다. 예를 들어, 동아일보 메인 페이지에서 ‘신문과 놀자’를 검색하고 검색 결과 페이지에서 기사를 선택해 읽은 후 뒤로 가기 버튼을 누르면 다시 신문과 놀자 검색 결과 페이지로 돌아갈 수 있습니다. 이것은 웹브라우저가 사용자의 웹페이지 이동 기록을 차곡차곡 쌓아 두고 있다가 뒤로 가기 버튼이 클릭되면 스택의 가장 위쪽 페이지 주소를 꺼내 보여주는 것입니다. 웹페이지 A에서 웹페이지 B로 이동할 때, 웹페이지 A의 URL이 스택에 입력됩니다. 그리고 많은 응용 프로그램에서 볼 수 있는 가장 최근에 실행된 명령을 취소하는 실행 취소(ctrl+z) 기능도 스택 구조를 이용하는 예입니다.

스택과 큐는 자료가 일렬로 늘어선 선형 구조를 가질 때 사용한다고 했습니다. 그러나 현실에는 선형으로 표현하기 어려운 상황이 많습니다. 예를 들어, 학교에서 체육대회를 하는데, 축구는 모든 반이 한 번씩 경기를 치르는 리그전으로 하고, 줄다리기는 경기에서 이긴 반이 다시 경기를 해서 최종 승자를 정하는 토너먼트 방식으로 하는 상황에서 대진표를 작성해야 한다면, 보통 대진표를 위 그림(비선형 자료 구조)과 같이 작성할 것입니다.

이러한 구조는 자료의 전후 관계가 1 대 1인 선형 구조와 달리, 자료 사이의 관계가 1 대 n 또는 n 대 m으로 자료 다음에 여러 개의 자료가 존재할 수 있는 형태로 비선형 자료 구조라 합니다. 여러 연결 관계를 갖는 비선형 구조의 자료를 저장하고 처리하기 위한 방법으로 트리와 그래프 구조를 사용합니다. 트리는 순환 구조가 존재하지 않는 그래프로, 크게 그래프의 범주에 포함됩니다. 그래프는 원과 선으로 표현되고, 그래프에서 원은 노드(node)라고 하며, 노드를 잇는 선을 간선(edge)으로 부릅니다. 각 반을 노드로 만들고, 두 반이 경기를 하는 경우를 간선으로 만들면, 체육대회에서 경기를 할 상대와 순서 등을 단순화해 그래프로 표현할 수 있습니다.

스택과 큐, 트리와 그래프 등의 자료 구조를 이용해 복잡한 상황을 단순화시켜 꼭 필요한 내용만 나타내는 방법인 추상화를 다뤄 보았습니다. 추상화는 컴퓨터과학자가 세상을 바라보는 여러 방법 중 매우 중요한 요소로 컴퓨터과학 분야에서 다양하게 사용하는 생각의 도구입니다.


김학인 한성과학고 교사