새내기 자료구조 멘토링 - Stack,Queue,Tree,Graph

오늘은 교내 학술동아리 신입회원분들을 대상으로한 멘토링에서

자료구조 멘토링을 진행했습니다.

 

Stack, Queue, Tree, Graph를 위주로 퀴즈를 풀어가면서

자료구조를 빠르고 쉽게 찍어먹어 봤습니다.

 

제 소개를 드리고 배울 내용에 대해 소개드렸습니다. (멘토 소개 생략)

인터넷에 검색해보면 Primitive Data Structure는 

char, integer, real, string, pointer.. 처럼 다양하게 적혀있습니다.

아마 프로그래밍 언어별로 다를 수도 있는 것 같습니다.

 

그래서 그냥 크게 신경쓰지 않고 

Boolean, Char, Integer, Floating-Point로 나눴습니다.

 

Non-Primitive Data Structure도 검색해보면 많이 다르게 나뉘는데

그냥 대충!! 적당히 저정도만 알아두면 된다고 생각해서 저렇게 나눠놨습니다.

2학기인 이상, 1/2학년 분들이 멘토링 듣기에 배열은 이미 아실거고,

연결리스트는 간단하게 개념 설명하고서 Stack, Queue, Tree, Graph에 초점을 맞춰

멘토링을 진행한다고 했습니다.

 

먼저 Stack입니다

Stack은 Push/Pop이 Top에서 작동되는 형태입니다.

위로 점점 쌓인다고 생각하면 됩니다

LIFO라고 Last In First Out, 나중에 들어온게 가장 Top에 쌓여서 제거될 때 가장 먼저 제거됩니다.

 

Stack구조는 일상생활에서 

책을 쌓을 때 밑에서부터 쌓이고

위에서 부터 책을 다시 뺄 수 있다는 것과 같은 예시를 찾아볼 수 있습니다.

 

이제 Stack구조에 대해서 이해를 했으니 간단한 퀴즈를 풀어봅시다.

 

수도코드는 실제로 문법적으로 작동하지는 않지만 기능의 동작을 보여주는 간단한 형태의 코드입니다.

C문법과 비슷한 수도코드를 보면서 위 코드는 어떤 기능을 표현하고 있는건지 살펴봅시다.

 

라고 말씀드리고 2분정도 기다린 후 같이 풀었습니다.

답은 1번입니다. 첫 while문에서는 n에대한 2진수를 뒤에서부터 stack에 저장하는데

두 번째 while문에서 stack에서 답을 다시 빼낼 때는 가장 나중에 들어온 것이 가장 먼저 제거되어 출력되므로

2진수를 순서대로 출력하게 됩니다.

 

 

다음은 Queue입니다.

Queue는 Stack의 Top과 달리 Front와 Back이 존재합니다.

Back에서 값을 Push하고 Front에서 값을 Pop할 수 있습니다.

 

그래서 값을 넣고 제거하는 동작이 FIFO(First In First Out)으로 진행됩니다. 

 

일상 생활에서 Queue에 대한 예를 살펴보면

1차선에서 맨 앞에 있는 차가 가장 먼저 나가고, 버스를 기다릴 때 맨 앞사람이 먼저 타는 것과 같습니다.

 

Queue에 대한 개념 또한 어렵지 않죠? 이번에도 역시 퀴즈를 풀어봅시다.

웃긴게, 저는 이 문제를 풀이 할 때 새내기 분들은 다 맞았는데

제가 틀렸습니다. 그래서 새내기 분들한테 잊으라고 했었죠..ㅎ

 

위 문제에서 deQueue()를 Pop이라 생각하고 enQueue를 Push라고 생각하면 됩니다.

Q에서 순서대로 Pop이 되지만 Stack에 쌓이고서 Pop될 때는 Top부터 나가지기 때문에

정답은 2번입니다.

 

 

다음은 Tree입니다. 

Tree는 각 정점(Node)들과 간선(Edge)로 이루어져있습니다.

한 정점에서 간선을 통해 다른 정점으로 이어질 때

위에 있는 노드를 부모, 아래있는 노드를 자식이라고합니다. (Parent-child관계)

 

가장 위에있는, Parent가 없는 노드가 Root노드입니다.

그리고 child를 leaf로 표현해서 노드들을 leaves라고 표현하기도합니다.

 

실생활의 예로는 가계부를 들었는데 트리구조는 맞지만 뭔가 애매하죠, 루트 노드가 없네요

 

정답은 9입니다. 이 문제를 풀기전에 이진 트리(binary tree)에 대해서 설명드렸는데

이진 트리는 한 노드에서 최대로 나오는 자식 노드가 2개입니다. 그리고 자식 노드는 왼쪽에서 오른쪽으로 채워집니다.

 

다음은 Graph입니다.

 

그래프는 트리처럼 각 정점과 간선으로 이어져있지만 root와 같은 노드는 없습니다. 상하 관계가 없습니다!

일상에서 쉽게 찾아볼 수 있는 예로는 지도에서 도시를 이어서 거리를 나타내는 경우를 들 수 있을 것 같습니다.

실제로 이와 관련된 문제들이 많습니다. 예를 들어 대표적으로 외판원 순회같은 문제가 있습니다.

 

그래프 퀴즈입니다.

위 퀴즈는 최소신장트리(MST, Minimum spanning tree) 알고리즘을 이용해서 풀수있는데, 

그중에서 크루스칼 알고리즘을 이용해서 풀이했습니다. 답은 19입니다.

 

마지막으로 보너스 Heap에 대해 설명했습니다.

트리로 구현할 수 있고 Priority Queue로도 구현할 수 있고

최소 힙과 최대 힙이 각 무엇인지 개념을 설명했습니다.

 

끝!