자료구조를 시작할려고 한다. 2년전에 자료구조와 알고리즘이 같이 들어있는 얇은 알고리즘 책을 읽은 적이 있다. 그때 사용했던 언어는 C언어였다. 지금은 JavaScript로 자료구조를 정리해볼려고 한다. 자료구조는 공학에서는 수학이라고 생각할 만큼 중요하다고 생각한다. 그만큼 자세히 다루고 싶고 깊게 이야기해보고 싶다.

자료구조를 배워야 하는 이유

뭐든 배울때 이유가 있어야 배우기 쉽다. 동기부여 관점에서도 그렇지만 배우는 이유를 확실하게 잡아 놓으면 원리가 보인다. 나의 경우엔 그렇다. 그리고 이 이유를 내가 스스로 답문하는 걸 좋아한다. 이유를 알아내는 재미가 공부를 하게 한다. 현재 자료구조를 배워야 하는 이유는 앞으로 할 프로그래밍에 가장 효율적으로 결과를 내놓기 위함이라 생각한다. 너무 불필요한 과정으로 자료구조를 만들게 되면 시스템이 무거워져 비효율적이다. 잘못하면 컴퓨터가 무리간다.(쿨링팬이 이륙한다.) 이는 효율적인 알고리즘과 연결이 되는데 이 때문에 서점에서는 알고리즘과 자료구조를 한 책에 묶어 같이 내놓기도 한다. 이유에 대해서는 이 정도로 정리하고 내가 앞으로 정리할 자료구조에 대해 소개하겠다.

앞으로 공부할 자료구조

Stack, Queue, Linked List, Hash Table, Graph, Tree, Binary Search Tree이다. 하나하나 자료구조에 대해 정리해 나갈 것이다. 일단 이론적인 내용부터 정리를 한 후 JavaScript로 정리해서 코드 리뷰는 나중에 해보겠다. JavaScript로 정리뒤 좀 더 메모리단에서의 정리를 위해 C로도 코드를 올릴 예정이다.

Stack

스택은 우리가 실생활에서 많이 보는 자료구조이다. 프링글스 과자통과 같이 가장 먼저 들어간 과자가 제일 늦게 나온 구조이다. LIFO(Last In First Out)의 구조이다. 실생활에 밀접한 구조이기 때문에 많은 설명은 필요없을 것 같다.

Queue

큐는 우리 실생활에서 편의점을 생각해보면 된다. 음료가 들어가있는 냉장고를 보면 선입선출 할 수 있도록 나타나있다. 먼저 들어간 자료가 먼저 나온다. ![]

Linked List

연결리스트는 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. 데이터는 노드에 저장되어있고 이 노드들은 이전 노드와 이후 노드와 연결되어 있다. 한 쪽 방향으로만 연결이 이루어져 있다면 단일 연결 리스트를 뜻하고 양 방향으로 연결이 이루어져 있다면 이중 연결 리스트를 뜻한다. 단일 연결 리스트로 이루어져 있으며 마지막 노드가 처음 노드와 연결 시키면 원형 연결리스트이다.

단일 연결리스트

이중 연결리스트

원형 연결리스트

HashTable

해쉬테이블은 key와 value를 가진 데이터 구조이다. key를 넣으면 알맞는 value를 찾는 구조이다. 자물쇠 역할을 하는 것과 같다. key는 hash function이라는 함수에 들어가 value를 찾기 위한 구조로 변화가 된다. 이 구조를 hash value(해쉬 값)이라고 한다. 이 해쉬값을 인덱스로 삼아 특정 인덱스에 데이터를 저장한다. 저장해놓은 값을 찾기 위해서는 key를 다시 hash function에 입력시켜 hash value를 받아 알맞는 인덱스에 접근 시키면된다. 하나하나 어떤 자료가 들었는지 찾아야하는 다른 자료구조에 비해 검색이 한번에 이루어 진다는 장점이 있다. hash는 미리 사이즈를 정해 놓는다. Hash Table은 보통 저장가능한 배열의 갯수를 만들어 놓는다. 그리고 이 중 75퍼센트가 넘으면 배열의 갯수를 늘려주고 25퍼센트 밑으로 저장이 되면 배열을 줄인다.

Hash collision

해쉬충돌은 hash function으로 나온 인덱스가 겹치는 현상이다. key값이 서로 다르지만 hash function으로 같은 인덱스를 배정 받게 될 수 있다. 이 점에서 1대1로 나오는 hash function이 가장 이상적인 것이지만 이를 만들어내기는 쉽지 않을 것이다. 이를 해결하기 위한 방법을 제시한다. 그리고 내 의견을 말해보겠다.

Open Address 방법

해시가 충돌이 일어났을 때 다른 key값이 그 인덱스(이제부터는 이 인덱스를 버킷이라고 부르겠다.)를 사용하는 중이라면 다른 해시 버킷에 해당 자료를 삽입하는 방식이다. 나쁜 경우에 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 오게 된다. 다시 주소를 찾아야 하며 2차 해쉬 함수를 통해 새로운 주소를 할당해야 하는 비효율 때문에 연산량이 추가되어 좋은 방법으로 생각 되지는 않는다.

Seperate Chaining

Seperate Chaining에 경우 두가지 방식이 존재한다.

연결리스트를 사용하는 방식

각각의 버킷에 연결리스트를 만들어 collision이 발생하면 해당 bucket에 list를 만들어 연결리스트를 통해 추가하는 방식이다. 연결리스트를 사용하기 때문에 collision시 삭제, 삽입이 간단하다. 하지만 연결리스트의 단점을 그대로 이어 받기 때문에 이에 대해 생각해봐야한다. 가장 좋은 방법은 연결리스트를 쓰지 않게 hash collision 자체를 일어나지 않게 하는 방법이다.

Tree를 사용하는 방식

아직 시간 복잡도에 대해 이야기하진 않았지만 연결리스트보다 tree가 시간 복잡도에서 유리함이 있다. 그렇기 때문에 자료가 많아지게 된다면 tree를 이용해서 collision시 버켓에 저장하는 방법이 좋다. 하지만 데이터가 적다면 연결리스트를 그대로 사용하는 것이 좋을 것이다. tree는 메모리 사용량이 많아지게 되어 데이터가 적다면 오히려 비효율적일 것이다.(트리구조는 아직 언급하지 않았다.)

Graph

graph는 node(vertice)와 edge(arcs)로 구성되어 있다. node들이 edge를 통해 연결 되는 구조이다. 인터넷 네트워크를 graph에 대표적인 모델로 삼고있다.
그래프는 방향성에 따라 Undirected graph와 directed graph로 나눌 수 있다. 방향성에 따라 표현하는 방식이 다르다.

위 그래프를 기준으로 인접 행렬(Adjacency Matrix)와 인접 리스트(Adjacency List)를 나눠 설명하겠다.

인접 행렬(Adjacency Matrix)

노드를 2차원으로 배열해 만든 것이다. 노드와 노드간 연결이 이루어지면 1로 표시한다. 0과 1이 연결 되어 있기 때문에 0과 1이 만나는 양 부분에 1이 나타나 있다. 모든 정점들의 연결 여부를 행렬로 저장하기 때문에 공간에 대한 효율성은 떨어지지만 연결여부를 확인하는 작업에서는 효율적이다.

인접 리스트(Adjacency List)

노드에 연결되어 있는 노드들을 리스트로 표현 한 것이다. 연결된 간선 정보만 저장하기 때문에 공간의 효율성은 높다. 하지만 서로 연결 되어 있는지 확인 하기 위해서는 비효율적이다. 하나하나 검색해 나아가기 때문이다. (리스트의 기능)

Tree

트리는 노드로 이루어진 구조로 노드의 값과 자식의 값들로 이루어져있는 구조이다.
한 부모 노드가 여러개의 자식 노드를 가질 수 있다. 부모가 없는 노드를 루트 노드라 하고 자식이 없는 노드를 단말 노드라고 한다. 노드이 연결되는 구조가 부모가 자식을 가지고 있는 구조이다. 이렇기 때문에 일반적인 List 검색방식과 Hash 방식과는 다른 검색 방식을 가지고 있다. 노드들을 딱 한번씩만 방문하는 과정이라 불리는 순회방식으로 트리를 검색할 수 있다.

위에 그림을 이용해서 순회의 방법에 대해 논해보겠다.

순회

전위 순회: F, B, A, D, C, E, G, I, H (root, left, right)
중위 순회: A, B, C, D, E, F, G, H, I (left, root, right)
후위 순회: A, C, E, D, B, H, I, G, F (left, right, root)

전위 순회는 맨 위 F부터 시작해서 왼쪽으로 검색을 시작한 후 오른쪽으로 점차 가는 것이다. 위에서 아래로 내려오는 순서이다.
중위 순회는 밑에서 부터 시작하는데 중위순회는 BST(Binary Search Tree)에서 많이 쓰이기 때문에 여기서 다시 다뤄 보도록 하겠다.
후위 순회는 맨 왼쪽 그리고 아래에서 부터 검색을 시작하는데 중위 순회와 다르게 진행된다. 중위순회는 맨 왼쪽 밑 그 다음 자신의 부모를 방문한 뒤에 그 부모의 자식 단 맨 아래 왼쪽을 방문하고 그리고 그 방문한 노드의 부모를 검색한뒤 다시 오른쪽 아랫 단으로 검색을 하는 방법이다. 후위 순회는 이와 다르게 맨 왼쪽 최하단부터 오른쪽으로 가며 최하단만 검색을 끝낸뒤 점차 부모 단으로 올라오는 방식이다.

BST(Binary Search Tree)

BST는 Tree의 한 구조로 이진 탐색 트리라고 불린다.

위에 그림을 참고해서 BST에 대해 설명해보겠다. 처음 맨 윗단 부모값(루트)이 18이다. 이때 7을 Tree에 삽입하는 과정은 루트값인 18과의 대소 관계를 따진다. 7은 18보다 작기 때문에 자식 단 중에서도 왼쪽으로 삽입된다. 26이 들어오면 18보다 크기 때문에 오른쪽으로 들어온다. 다음 21을 넣는 과정은 18보다 크기때문에 오른쪽으로 들어가는데 이미 오른쪽에는 26이라는 숫자가 존재해서 26의 자식으로 편성되어야 한다. 이때 26보다 작아서 26의 왼쪽단에 위치한 자식 노드로 위치한다. BST의 특징 중 하나는 자식을 2개 밖에 가지지 못한다는 점이 있다.

정리해보자면

• BST는 자식을 2개밖에 가지지 못한다.
• 삽입과정에서 루트 값보다 크면 오른쪽, 작으면 왼쪽에 위치한다.
• 만약 삽입과정에서 자식 노드에 어떤 값이 위치해있다면, 그 값을 부모로 삼고 그 값과 비교해 작다면 왼쪽 자식, 크다면 오른쪽 자식으로 삽입된다.
  
  만약 BST 구조에서 순차적으로 작은 수부터 오름차순으로 정리하고 싶다면 중위순회를 이용해 행렬을 만들어 주면 된다. 위 화살표 순서로 검색이 되기 때문에 오름차순으로 검색이 진행된다.

앞으로

자료구조에 대한 코드를 작성할 예정이다. 큰 범주로 설명했지만 이보다 더 자세한 내용은 하나하나 파고들어가며 코드를 배경으로 설명해볼까한다. 자료구조와 알고리즘은 계속해서 블로깅하며 TIL을 올릴예정이다.