자료구조, 자료구조의 종류

✍️ Today I Learned

1. 자료구조란?

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

데이터에 편리하게 접근하고 변경하기 위해 데이터를 저장하거나 조직을 효율적으로 해야한다.

그러한 행위로 분류된 데이터를 자료구조라 한다. ~~( + 알고리즘은 그 저장된 데이터를 처리하는 과정이다.)~~

2. 자료구조의 종류

2-1. Stack

스택(Stack)은 쌓다, 쌓이다, 포개지다란 뜻을 내포한다. 직역 그대로 데이터(data)를 순차적으로 쌓는 구조이다.
순차적으로 쌓다보니, 가장 먼저 들어간 자료는 가장 나중에 나올 수 있다. 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근에 있다.
이러한 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out) 이라 일컫는다

위 사진 처럼 push(), pop()을 쓰는 배열이 대표적인 Stack 자료구조이다.
대표적으로 활용되는 예시는 브라우저의 뒤로 가기, 앞으로 가기 기능 & 엑셀 등 문서작업에서 되돌리기 등의 기능을 구현 할 때 자료구조 Stack의 활용이 필요하다.

2-2. Queue

큐(Queue)는 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 내포한다.

Stack과는 반대되는 개념으로, 먼저 들어간 데이터가 먼저 처리되는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있는다.

위 사진 처럼 자료구조 Queue는 데이터가 입력된 순서대로 처리할 때 주로 사용한다.
대표적으로 활용되는 예시는 프린터가 출력되는 인쇄작업 Queue에 사용된다.

자료구조 Queue를 활용함으로써 프린터는 인쇄작업 Queue에 들어온 문서를 순서대로 인쇄할수있다.

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

이를 버퍼(buffer) 라 일컫는다.

2-3. Graph

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있겠으며, 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
그래프에서 하나의 점을 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 한다.

정점과 정점사이에 간선이 존재하는데, 이 간선은 정점 사이의 관계를 나타낸다.

정점 사이에 직접적, 간적적으로 간선이 없는 경우를 그래프에선 “관계가 없다” 라고 표현한다.
일상생활에선 매일같이 자료구조 그래프를 사용하고 있다.

포털 사이트의 검색 엔진, SNS, 네비게이션(길찾기) 등 에서 사용되는 자료구조이다.

간단한 예를 들자면,

서울에 사는 A는 부산에 사는 B와 오랜 친구 사이입니다.

이번 주말에 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려고 합니다.

대전에 살고 있는 친구 C도 B의 결혼식에 참석을 한다고 하여, A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동을 하려고 합니다.

위 예시에서는 3개의 정점이 존재한다(A,B,C). 각각 서울,부산,대전을 그래프의 정점으로 삼는다면, 이 3개의 정점은 서로 이어지는 간선(관계)를 가지고 있다.

정점 : 서울(A), 대전(B), 부산(C)

간선 : 서울-대전, 대전-부산, 부산-서울

이를 간단한 JS 객체를 이용하여 비유한다면 아래와 같다.
```
const isConnected = {
  seoul : {
    busan : true,
    daejeon : true
  }
  daejeon : {
    seoul : true,
    busan : true
  }
  busan : {
    seoul : true,
    daejeon : true
  }
}

console.log(isConnected.seoul.busan) // true
```
현재는 특정 도시가 이어져 있다는 무향그래프라는 노드3개와 간선 3개라는 사실만 알려줄 뿐, 그 외의 정보를 포함하고 있진 않다.

이러한 그래프를 비가중치 그래프라 한다.
그래프를 학습하기에있어, 알아둬야 할 용어들이 있다. 간단하게 살펴보자.
1. 무(방)향그래프(underected graph) : 네비게이션(길찾기)에서 보이는 그래프들은 무향 그래프이다. 서울에서 부산을 갈 수 있듯, 반대로 부산에서 서울로 올 수도 있다.
  
  반대 개념인 단방향 그래프(directed graph) 로 구현 된다면, 한쪽 방향으로만 가능할 것이다. 예를 들면 도로의 일방통행은 단방향 그래프로 길찾기를 구현 할 수 있다.
2. 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지 나타내는 용어이다.
3. 인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
4. 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현하며, 다른 정점을 거치지 않는다는 것이 특징이다.
5. 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.
인접은 위에서 말했듯이 직접 이어져 있는 정점의 관계를 나타낸다. 표현 방식을 수식화 할 땐 아래와 같은 방법으로 표현한다.
1. 인접 행렬 (adjacency matrix) : 그래프에서 정점(vertext)들이 어떻게 연결되었는지 나타내는 행렬이다.
- 2차원 배열로 작성하게 되며, 정점들 사이에 간선이 존재하는지 여부를 나타내거나, 가중치가 있는 그래프인 경우에는 정점관의 관계에서 의미 있는 값을 저장한다.
  
  참조 : http://stoimen.com
1. 인접 리스트 (adjacency list) : 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담는다.
- 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지하므로 메모리의 효율성을 위한 작업이 필요할땐 인접리스트가 효율적이다.

2-4. Tree

자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있다. 엄밀히 말하면 그래프의 여러 구조중 무방향 그래프의 한 구조라 말할수있다.

또한, 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다. 그리고 루트 노드를 기준으로 아래로만 층층이 뻗어나가기 때문에 계층적으로 표현이 되며 그래프와 달리 사이클은 존재하지 않는다.
트리를 학습하기에있어, 알아둬야 할 용어들이 있다. 간단하게 살펴보면,
1. 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
2. 루트(Root) : 트리 구조의 시작점이 되는 노드
3. 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
4. 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
5. 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드

tree

트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다.

각 데이터를 정점이 아닌 노드(Node)라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가지게 된다.

위 그림에서 A는 B,C,D의 부모 노드(Parent Node)이면서 루트(Root)이며, E와 F는 B의 자식 노드(Child Node)이다. 자식이 없는 C,D,E,F 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라고 부른다.
자료구조 Tree는 계층으로 구현되기 때문에 깊이와 높이, 레벨 등을 측정할 수 있다.
1. 깊이(depth) : 트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있다. 쉽게 생각하면 루트에서 현재노드 사이까지의 간선의 갯수라 생각하면 간단하다. 위 그림에서 루트 A의 depth는 0이고, B,C,D의 깊이는 1이다. 그리고 E와 F의 깊이는 2가 된다.
2. 레벨(level) : 트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현한다다. depth가 0인 루트 A의 level은 1이며, depth가 1인 B,C,D의 level은 2이다. 그리고 E와 F의 레벨은 3이 된다. 또한 같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node) 라 부른다.
3. 높이(height) : 루트부터 가장 경로가 긴 노드까지의 간선의 갯수가 높이가 된다.
마지막으로 트리는 큰 트리 내부에 트리 구조를 갖춘 작은 트리를 내포한다.

이는 서브 트리 라 부르며, 해당 서브 트리는 잘게 쪼개어 하나의 노드를 가지기 전까지는 모두 또 다시 서브 트리를 갖게된다.

즉, 한개 이상의 노드를 가진 트리는 재귀적인 구조를 지닌다.

🤔 Understanding

자료구조.. 개념은 어렵진 않다. 효율적인 데이터 구조는 효율적인 코드를 완성시키는 첫 걸음이라 생각된다. 지금이야 솔직히 말하면 별로 필요 없는듯 보인다..

~~지금은 코린이 수준의 코드이기 때문에.. ,장난감 집은 쉽게 짓고 대충 만들어도 완성되지만 고층 아파트는 구조 설계가 필수적이다!~~
기초학문 느낌이 물씬 난다. 구조적인 개념이 많이 등장되기 때문에, 들으면 생소한 느낌은 없다.

다만, 이를 어떻게 실제 코딩에 접목을 하느냐가 굉장히 난감하다.. 객체로 선입선출되는 자료구조를 어떻게..? 이런 느낌이다.

아직 생소하다보니 겪는 문제라 생각든다. 덩치가 큰 개발이 필요한 경우. 개발진행 전 자료구조를 꼭 생각하고 개발에 진행해야 되겠다는 생각은 든다.

탐색기 같은 프로그래밍 설계가 필요하다면 트리구조를 먼저 떠올린다. 등등..

✍️ Today I Learned
- 1. 자료구조란?
- 2. 자료구조의 종류
🤔 Understanding