Data Structure 핵심 개념들

"자료 구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것"

 

데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다.
우리의 이름, 나이, 키, 집 주소, 목소리 혹은 유전자 DNA까지 데이터로 분류할 수 있다.
그러나 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다.
예를 들어 나이라는 데이터만 알고 있다면, 사람의 나이인지 나무의 나이인지 알 수 없다.

이처럼 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.

뿐만 아니라 데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용할 수 있다.
전화번호부를 작성할 때, 숫자를 3개 또는 4개씩 묶음짓고 하이픈(-)으로 합친다.
이 숫자의 묶음에 이름을 붙여 보관해야 한다면, 해당 데이터를 꺼낼 때에는 항상 특정 이름을 입력해야 숫자를 얻을 수 있다.
전화번호부를 만든다면 그대로 사용해도 무방하지만, 거리를 구하거나 다섯 자리가 넘는 숫자를 보관해야 할 때에는 하이픈(-)이 필요하지 않다.
이처럼 필요에 따라 데이터의 특징을 잘 파악하여 정리하고 활용해야 한다.
데이터를 정해진 규칙 없이 저장하거나, 하나의 구조로만 정리하고 활용하는 것보다 데이터를 체계적으로 정리하여 저장해두는 것이 데이터를 활용하는 데 있어 훨씬 유리하다.

 

선배 개발자들은 무수한 상황에 데이터를 효율적으로 다룰 수 있도록 여러 방법들을 연구해 두었다.

• 번호를 다 알지 않아도, 이름을 아는 것만으로 전화를 할 수 있는 방법은 무엇이 있을까?
• 웹 브라우저에서 뒤로 / 앞으로 가는 방법은 무엇이 있을까?
• 게임 매칭을 잡을 때, 수많은 사람들을 통제하는 방법엔 무엇이 있을까?

선배 개발자들은 무수한 상황에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아, 자료 구조 라는 이름을 붙였다.
이번 포스팅에서는 가장 많이 쓰이고 Algorithm 테스트에도 자주 등장하는 네 가지 자료 구조를 알아볼 것이다.

Stack, Queue, Tree, Graph

대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.
따라서 많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있다.

 

 

Stack

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다.
이 자료구조는 직역 그대로, 데이터를 순서대로 쌓는 자료구조 이다.
그리고 가장 먼저 들어간 요소는 가장 나중에 나올 수 있으며, 가장 나중에 들어간 요소는 가장 먼저 나올 수 있다.
이처럼 자료구조 Stack의 특징은 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근 에 있다.
이러한 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 라고 부르기도 한다.

 

Stack의 실사용 예제

브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack이 활용된다.

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

 

 

Queue

Queue는 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있다.
자료구조 Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 를 특징으로 가지고 있다.
이러한 자료구조 Queue는 데이터가 입력된 순서대로 처리할 때 주로 사용한다.

 

Queue의 실사용 예제

컴퓨터에서 광범위하게 활용된다.
컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하려면 어떻게 해야 할까?

1. 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 Queue에 들어감
2. 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄

이처럼 컴퓨터 장치들 사이에서 데이터를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다.
이것을 통틀어 Buffer 라고 한다.

 

 

Graph

그래프라는 단어를 들으면 X축과 Y축이 존재하는 그래프를 주로 떠올릴 수 있다.
하지만 컴퓨터 공학에서 이야기하는 자료구조 그래프는 전혀 다른 모습을 가지고 있다.
자료구조의 그래프는 마치 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 가지고 있다.
직접적인 관계 가 있는 경우 두 점 사이를 이어주는 선이 있다.
간접적인 관계 라면 몇 개의 점과 선에 걸쳐 이어진다.
하나의 점을 그래프에서는 정점(vertex) 이라고 표현하고, 하나의 선은 간선(edge) 이라고 한다.

 

Graph의 실사용 예제

포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 내비게이션 등에서 사용하는 자료구조가 바로 그래프이다.
세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이어져 있다.

 

내비게이션 시스템이 어떤 방식으로 자료구조 그래프를 사용하는지 살펴보도록 하자.

서울에 사는 A는 부산에 사는 B와 오랜 친구이다.
이번 주말에 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려고 한다.
대전에 살고 있는 친구 C도 B의 결혼식에 참석을 한다고 하여, A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동을 하려고 한다.

• 정점 : 서울, 대전, 부산
• 간선 : 서울 - 대전, 대전 - 부산, 부산 - 서울

간선은 내비게이션에서 이동할 수 있음 을 나타낸다.
정점에 캐나다의 토론토를 추가한다면, 자동차로는 토론토에서 한국으로 이동할 수 없기 때문에 간선도 추가할 수 없다.
그래프에선 이런 경우를 관계가 없다 라고 표현한다.
간선을 살펴보면 서울, 대전, 부산이 서로 관계가 있다는 것은 알 수 있지만, 각 도시가 얼마나 떨어져 있는지는 알 수 없다.
이처럼 추가적인 정보를 파악할 수 없는 그래프, 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않으면 비가중치 그래프 라고 한다.

 

JavaScript를 활용해서 간단하게 비유한다면 다음과 같다.

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true,
  },
  daejeon: {
    seoul: true,
    busan: true,
  },
  busan: {
    seoul: true,
    daejeon: true,
  },
};

console.log(isConnected.seoul.daejeon); // true
console.log(isConnected.daejeon.busan); // true

내비게이션이라면 적어도 각 도시 간의 거리가 얼마나 되는지는 표시해야 할 것이다.
그래프를 가중치 그래프 로 바꾸고, 각 도시 간의 거리를 표시하면 더 자세한 정보를 담을 수 있다.

• 정점 : 서울, 대전, 부산
• 간선 : 서울 -140km- 대전, 대전 -200km-부산, 부산-325km-서울

 

알아둬야 할 Graph 용어들

• 무향 그래프(undirected graph) : 앞서 보았던 내비게이션 에제는 무향 그래프이다.
  서울에서 부산으로 갈 수 있듯이 부산에서 서울로 갈 수도 있다.
  하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 갈 수 없다.
  만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있다.
• 진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입하고 진출하는 간선이 몇개인지를 나타낸다.
• 인접(adjacency) : 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
• 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다고 표현한다.
  다른 정점을 거치지 않는다는 것이 특징이다.
• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.

 

인접 행렬

두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기한다.
인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타낸다.
만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표이다.
가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장한다.

 

인접 행렬은 언제 사용할까?

• 두 정점 사이에 관계가 있는지 없는지 확인하기에 용이하다.
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용된다.

 

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다.
각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

 

순서는 보통의 경우 중요하지 않다.
그래프, 트리, 스택, 큐 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있다.
그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선순위를 고려해서 구현할 수 있다.
이 때, 리스트에 담겨진 정점들을 우선순위별로 정렬할 수 있다.
우선순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.
우선순위를 다뤄야 한다면 더 적합한 자료구조를 사용하는 것이 합리적이다.

 

인접 리스트는 언제 사용할까?

• 메모리를 효율적으로 사용하고 싶을 때 사용한다.
  (인접 행렬은 모든 경우의 수를 저장하기에 상대적으로 메모리를 많이 차지한다.)

 

 

Tree

자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다.
정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다.
그래프의 여러 구조 중 무방향 그래프 의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부른다.
트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 이다.
데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조 이다.
트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없다.
트리 구조는 Root 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.
각 데이터를 Node라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가진다.
자식이 없는 노드는 나무의 잎과 같다고 하여 Leaf Node 라고 부른다.

 

용어 정리

• Node : 트리 구조를 이루는 모든 개별 데이터
• Root : 트리 구조의 시작점이 되는 노드
• Parent node : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• Child node : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• Leaf : 트리 구조의 끝이고, 자식 노드가 없는 노드

자료구조 Tree는 깊이와 높이, 레벨 등을 측정할 수 있다.

 

깊이 (depth)

트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이 를 표현할 수 있다.
루트 노드는 지면에 있는 것처럼 깊이가 0이다.

 

레벨 (Level)

트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨 로 표현할 수 있다.
깊이가 0인 루트의 레벨은 1이다.
같은 레벨에 나란히 있는 노드를 형제 노드(sibling node)라고 한다.

 

높이 (Height)

트리 구조에서 리프 노드를 기준으로 루트까지의 높이 를 표현할 수 있다.
리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가진다.
트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓는다.

 

서브 트리 (Sub tree)

트리 구조에서 root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부른다.

 

Tree의 실사용 예제

가장 대표적인 예제는 컴퓨터의 디렉토리 구조이다.
어떤 프로그램이나 파일을 찾을 때, 바탕화면 폴더나 다운로드 폴더 등에서 다른 폴더에 진입하고, 또 그 안에서 다른 폴더에 진입하면서 원하는 프로그램이나 파일을 찾는다.
모든 폴더는 하나의 루트 폴더에서 시작되어, 가지를 뻗어나가는 모양새를 띈다.

 

Binary Search Tree

트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다.
수많은 선배 개발자들은 효율적인 탐색을 위해 고민하고 발전시켜 새로운 트리의 모습을 만드는 등 치열한 노력을 쏟았다.
그렇기 때문에 트리 구조는 가지고 있는 특징에 따라 여러 가지 이름으로 불린다.
많은 트리의 모습 중, 가장 간단하고 많이 사용하는 것은 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)이다.

 

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

종류	영어 표기	설명
정 이진 트리	Full binary tree	각 노드가 0개 혹은 2개의 자식 노드를 가짐
포화 이진 트리	Perfect binary tree	정 이진 트리이면서 완전 이진 트리인 경우모든 리프 노드의 레벨이 동일모든 레벨이 가득 채워져 있음
완전 이진 트리	Complete binary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 함마지막 레벨의 노드는 왼쪽이 채워져야 함

이진 탐색 트리(Binary Search Tree) 는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.
이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야할 문제이다.
이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 Algorithm을 추가할 수 있다.

 

 

Tree traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회 라고 한다.
1에서 10까지의 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시이다.
트리 구조는 계층적 구조라는 특별한 특징을 가지기 때문에, 모든 노드를 순회하는 방법엔 크게 세 가지가 있다.
바로 전위 순회, 중위 순회, 후위 순회이다.
이 순회 방식과는 논외로, 트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽이다.

 

전위 순회 (Preorder)

루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색한다.

그림으로 확인하기

 

중위 순회 (Inorder)

제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 탐색한다.

그림으로 확인하기

 

후위 순회 (Postorder)

루트를 가장 마지막에 순회한다.
제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여, 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.

그림으로 확인하기

 

 

BFS / DFS

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적 이다.
그래프의 데이터는 배열처럼 정렬이 되어 있지 않다.
그래서 원하는 자료를 찾으려면 하나씩 모두 방문해서 찾아야 한다.
그래프의 모든 정점 탐색 방법에는 여러 가지가 있다.
그중에서 가장 대표적인 두 가지 방법이 바로 DFS와 BFS이다.

 

BFS (Breadth-First Search)

BFS는 가장 가까운 정점부터 탐색 한다.
그리고 더는 탐색할 정점이 없을 때, 그 다음 떨어져 있는 정점을 순서대로 방문한다.
BFS는 이처럼 너비를 우선적으로 탐색하기 때문에 Breadth-First Search, 너비 우선 탐색 이라고 한다.
주로 두 정점 사이의 최단 경로를 찾을 때 사용한다.

그림으로 확인하기

 

DFS (Depth-First Search)

DFS는 하나의 경로를 끝까지 탐색한 후, 원하는 정점이 아니라면 다음 경로로 넘어가 탐색 한다.
하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있다.
이렇게 깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색 이라고 한다.
한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다.
BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있다.

그림으로 확인하기

 

 

BFS와 DFS는 모든 정점을 한 번만 방문한다는 공통점을 가지고 있지만, 사용할 때의 장단점은 분명하기 때문에 해당 상황에 맞는 탐색 기법을 사용해야 한다.