자료구조(Data Structure)

자료구조

 

Base

1.스택 Stack

LIFO: 마지막에 들어간 데이터가 가장 먼저 나오는 구조이다. 

비유를 들자면 장독 같은 거라고 보면 되겠다.

자바스크립트로 보자면 배열의 push 와 pop 이라고 생각하면 된다.

const arr = [1,2];

arr.push(3);   // [1,2,3]

arr.pop();      // [1,2]

 

2.큐 Queue

FIFO: 먼저 들어간 데이터가 가장 먼저 나오는 구조이다.

비유를 들자면 놀이동산에서의 줄서기라고 보면 되겠다.

자바스크립트 배열의 push와 shift 를 생각하면 된다.

const arr = [1,2];

arr.push(3);   // [1,2,3]

arr.shift();     // [2,3]

 

Advanced

1. Linked List

Linked List는 Array List와는 다르게 엘리먼트와 엘리먼트 간의 연결(link)을 이용해서 리스트를 구현한 것을 의미합니다.

 

[A] -> [B] -> [C]

 

A,B,C 각각을 노드(node) 또는 버텍스(vertex) 라고 부르고, 

-> 메모리의 위치(주소)를 가리키는 포인터라고 한다.

 

일반적으로 리스트는 배열(Array)과는 달리, 데이터가 메모리상 연속된 위치에 저장되지 않고,

떨어진 영역에 흩어져서 저장된다.

흩어져서 저장되어 있으므로, 처음부터 포인터를 따라 순서대로 접근해야 원하는 데이터 접근할 수 있다. (시퀀셜 엑세스 라고 한다)

즉, C 에 접근하려면 A, B 를 거쳐야 한다.

 

* 노드 사이에 새로운 노드 추가하기

[A] -> [B] -> [C] 

리스트에서 인덱스가 1인 자리에 D를 추가한다고 해보자.

[A] -> [D] -> [B] -> [C]

그러면 이런식으로 A가 D를 가리키게 하고 D가 B를 가리키게 하면된다.

 

삭제방법

[A] -> [D] -> [B] -> [C]

 

B를 삭제해보자.

[A] -> [D]  x  [B] -> [C]                              

             |_______________↑

 

D의 포인터를 C로 변경하면 된다.

B는 별도로 처리하지 않아도 괜찮다. 이후에 이 영역이 사용될 때 덮어쓰기가 되어 재활용할 수 있다.

 

 

2. Graph

 

 

원을 노드, 선을 링크(또는 엣지)라고 한다. 그래프는 정점과 간선으로 연결된 것을 말한다.

일방향만 가능하다는 것을 나타내고 싶을 때는 방향성을 표시할 수 있다.

 

방향성 그래프

 

 

비방향성 그래프

* 간선에 가중치를 추가할 수 있다.

예를 들어, 지하철 노선도라고 한다면 노드와 노드사이를 걸리는 시간 등을 가중치로 표시할 수 있다.

 

 

3. Tree

크게 보면 그래프의 일종이다.

특징은, 여러 노드가 한 노드를 가리킬 수 없다는 것이다. (서로 다른 정점끼리 연결된 패스가 하나인 것)

최상위 노드를 루트 노드라고 하고, P -> C 형태라고 한다면, P는 부모 노드, C는 자식 노드라고 한다.

자식이 없는 노드는 리프(Leaf) 노드라고 한다.

 

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

 

 

 

4. Binary Search Tree

그래프의 트리구조를 사용하는 데이터 구조.

 

https://visualgo.net/en/bst

맨 위에 있는 노드를 루트 노드라고 한다.

50은 왼쪽 가지의 모든 노드들보다 크고, 오른쪽 가지의 모든 노드들보다 작다.

모든 노들이 위와 같은 성질을 가지고 있다.

이 성질을 이용하면 최대값과 최소값을 구할 수 있다.

맨 오른쪽 노드가 바로 최대값 : 70, 맨 왼쪽 노드가 바로 최소값: 9

 

*노드 추가

최상단 루트 노드를 시작으로 추가하고자 하는 노드의 값이 작으면 왼쪽으로 크면 오른쪽에 위치시킨다. (재귀)

 

* 노드 삭제

- 자식 노드가 없는 경우

   ㄴ 바로 삭제

- 자식 노드가 하나인 경우

   ㄴ 삭제하고자 하는 노드를 지우고 그 위치에 자식 노드를 이동시킴.

- 자식 노드가 둘인 경우

   ㄴ 삭제하고자 하는 노드를 지우고 왼쪽 가지에서 최대 노드를 이동시키거나, 오른쪽 가지에서 최소 노드를 이동시킨다.

 

 

 * 노드 탐색

최상단 루트 노드를 시작으로 찾고자 하는 노드의 값이 현재 노드(최초 루트 노드)보다 작으면 왼쪽 가지로 크면 오른쪽 가지로 이동해서 찾는다.

 

계산 시간 O(log n) 

경우에 따라 한쪽으로 치우쳐지면 O(n) 

 

 

 

5. Hash Table

해시함수를 이용해 키, 벨류 형태의 데이터를 저장.

해시란, 불규칙한 숫자로 변환해주는 것으로 역산하는 것이 거의 불가능한 성질을 가지고 있다. (암호에 이용)

 

만약 저장할 위치의 값이 같다면 '충돌' 이라고 한다.

충돌인 경우 리스트로 연결한다.

 

 

 

해시테이블 같은 경우 어레이의 길이는 데이터 대비

25%< 최적 < 75% 라고 한다.

array 8 이고 입력한 데이터가 6개면 75% 이다.

7개가 되면 87.5%가 되어서 어레이의 길이를 늘려주고 다시 해싱 해주어야 효율적으로 활용할 수 있다.