자료구조(Data Structure) : 스택/큐/그래프/트리

정현웅·2021년 3월 7일

여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의하며, 특정한 상황에 문제를 해결하는데 사용된다.
자료(Data) : 문자,숫자,그림 등의 형태로 된 의미 단위

자료를 더 효율적으로 저장하고, 관리하기 위해 사용하며, 잘 선택된 자료구조는 실행시간을 단축시켜주거나 메모리 용량의 절약을 이끌어 낼 수 있다.

자료구조의 선택 기준

자료의 처리 시간
자료의 크기
자료의 활용 빈도
자료의 갱신 정도
프로그램의 용이성

자료구조의 전체 분류

1. 스택(Stack)

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다. 마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는 직역 그대로, 자료(data)를 쌓는 자료구조다. 이처럼 Stack의 특성은 입출이 하나인 제한적 접근에 있다.

후입선출 (LIFO : last in, first out)
👉 맨 위에 있는 데이터 즉, 제일 마지막에 저장한 데이터를 제일 먼저 꺼낸다.

[ 일상생활 예시 ]
브라우저에서 뒤로 가기, 앞으로 가기 기능을 구현

새로운 페이지로 접속할 때 현재 페이지를 Prev Stack에 보관한다.
뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때는 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때는 Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
마지막으로 현재 페이지를 Prev Stack에 보관한다.

2. 큐(Queue)

Queue는 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있다.
Stack과 반대되는 개념으로, 먼저 들어간 자료(data)가 먼저 나오는 FIFO(First In First Out) 의 특성을 가지고 있는 자료구조다.

선입선출 (FIFO : first in, first out)
👉 맨 앞에 있는 데이터 즉, 제일 처음에 저장한 데이터를 제일 먼저 꺼낸다.

[ 일상생활 예시 ]
명절에는 고향으로 가기 위해 많은 자동차들이 고속도로를 지나간다. 고속도로에는 톨게이트가 있고, 자동차는 톨게이트에 진입한 순서대로 통행료를 내고 빠져나온다.

톨게이트를 Queue 자료구조, 자동차는 자료(data)로 비유할 수 있다.

이처럼 Queue는 자료(data)가 입력된 순서대로 처리해야 할 필요가 있는 상황에서 사용된다.

3. 그래프(Graph)

노드(정점=vertex)와 간선(edge)으로 구성된 자료구조.
쉽게 말해, 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조다.

방향성에 따라 무방향 그래프(undirected graph/대칭 관계)와 방향 그래프(directed graph/비대칭 관계)로 나뉘며 간선에 비용이나 가중치를 할당하는 가중치 그래프(weighted graph)가 있다. 그 외에 완전 그래프, 부분 그래프, 연결 그래프, 단절 그래프 등이 존재한다.

그래프 용어

정점(Vertex) : 연결한 객체들을 의미
인접 정점(Adjacent vertex) : 간선에 의해 직접 연결된 정점
간선(Edge) : 정점들을 연결하는 선
차수(Degree) : 정점에 연결되어 있는 간선의 수, 방향 그래프에서 진입/진출 차수의 합
진입차수(In-Degree) : 방향 그래프에서 정점을 머리로 하는 간선의 수, 정점으로 들어오는 간선
진출차수(Out-Degree) : 방향 그래프에서 정점을 꼬리로 하는 건선의 수, 정점에서 나가는 간선
경로(Path) : 정점A에서 정점B까지 간선에 따라 갈 수 있는 길을 순서대로 나열한 것
- 단순 경로(Simple-path): 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로
- 사이클(Cycle) : 경로의 시작 정점과 마지막 정점이 같은 경로를 의미

3.1 그래프 표현방식

1) 인접행렬 방식 (Adjacency matrix)
그래프의 연결관계를 이차원 배열 로 나타내는 방식

정점 A에서 정점 B로 가는 간선이 있으면 1, 아니면 0

하나의 정점에서 자기 자신으로의 자체 간선은 있을 수 없으므로 인접 행렬의 대각선의 값은 항상 0이다. 무방향 그래프에서는 간선[a, b]와 [b, a]가 같기 때문에, 대각선을 기준으로 윗부분과 아랫부분이 대칭을 이룬다.
그와 반대로, 방향 그래프에서는 간선[a, b]와 [b, a]가 서로 다른 간선이기 때문에 대칭을 이루지 않는다.

장점

2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1) 의 시간 복잡도면 가능하다.
구현이 비교적 간편하다.

단점

모든 정점에 대해 간선 정보를 대입해야 하므로 O(n²) 의 시간복잡도가 소요됩니다.
무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비됩니다.

2) 인접리스트 방식 (Adjacency list)
인접 리스트는 각 정점이 어떤 정점과 인접한지 리스트의 형태로 볼 수 있는 표현 방식이다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트에는 자신과 인접한 다른 정점들이 담겨 있다.

장점

정점들의 연결 정보를 탐색할 때 O(n) 의 시간이면 가능하다. (n: 간선의 갯수)
필요한 만큼의 공간만 사용하기때문에 공간의 낭비가 적다.

단점

특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸린다. (배열보다 탐색 속도 느림)
구현이 비교적 어렵다.

그래프 탐색 방법

하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 그래프 탐색 이라고 한다. 그래프 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색이 있다.

1) 깊이 우선 탐색 : DFS(Depth First Search)
깊이 우선 탐색은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회 방법이다. Stack 사용

2) 너비 우선 탐색 : BFS(Breath Frist Search)
너비 우선 탐색은 시작 정점으로 부터 인접한 정점들을 모두 차례로 방문한 후, 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법으로, 가까운 정점들을 먼저 방문하고 멀리 있는 정점들은 나중에 방문하는 순회 방법이다. Queue 사용

4. 트리(Tree)

노드로 구성된 계층적 자료구조로 최상위 노드(루트)를 만들고, 그 아래 자식 노드를 추가하는 방식.
그래프의 여러 구조 중 사이클이 없는 그래프이며 일방향 그래프의 한 구조로, 최소연결트리로 불린다.
그러므로, 루트에서 어떤 노드로 가는 경로는 유일하다.

트리 용어

노드(node) : 트리의 구성요소
간선(edge) : 노드와 노드를 잇는 선
- 노드가 N개인 트리는 항상 N-1개의 간선(링크)를 가진다
루트 노드(root node) : 트리의 최상위 존재하는 노드
단말 노드(leaf node) : 차수가 0인 노드, 즉 자식 노드가 없는 노드
내부 노드(internal node) : 차수가 1 이상인 노드, 단말 노드가 아닌 노드
부모(parent) : 부속트리(subtree)를 가진 노드
자식(child) : 부모에 속하는 노드
형제(sibling) : 같은 부모를 가지는 노드
크기(size) : 자신을 포함한 모든 자식 노드의 개수
차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
깊이(depth) : 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 루트 노드의 깊이는 0이다
높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이
레벨(level) : 트리의 깊이와 정의가 비슷하지만 그 기준이 간선이 아닌 노드의 개수이다. 따라서 depth + 1 = level이 성립한다

4-1. 이진탐색트리(BST: Binary Search Tree)

모든 왼쪽 자식들은 루트나 부모보다 작은 값이고, 모든 오른쪽 자식들은 루트나 부모보다 큰 값인 특징을 가지고 있는 이진 트리를 이진 탐색 트리라고 정의한다.

이진트리(Binary Tree) 란?

자식 노드가 최대 두 개인 노드들로 구성된 트리를 이진 트리라고 정의한다. 이 두 개의 노드는 왼쪽 자식과 오른쪽 자식으로 분류한다. 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉜다.

이진트리의 종류

정 이진 트리: 각 노드가 0 개 혹은 2 개의 자식 노드를 갖는다.
포화 이진 트리: 정 이진 트리이면서 완전 이진 트리인 경우다. 모든 단말노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리다.
완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.