TIL(20210722) - 자료구조(Stack, Queue, Tree, Graph)

🎁 Today

- Stack, Queue, Tree, Graph 자료구조 이해와 각 자료구조의 개념과 구조 파악

- 상황에 맞는 자료구조를 사용하여 알고리즘 문제 풀이

🤔 Learned

자료구조(Data Structures)란?

데이터는 분석하고 정리하여 활용해야 의미를 가질 수 있고, 데이터의 특징을 잘 파악(분석)하여 활용해야 한다.

이를 위해 데이터를 효율적으로 다룰 수 있는 방법들을 모은 것이 자료구조이다.

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

각 자료구조들의 특징을 잘 이해하고 상황에 맞는 자료구조를 사용하여 문제를 해결해야 한다.

---

스택(Stack)

스택(Stack)은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다.

가장 먼저 들어간 데이터는 가장 나중에 나올 수 있고, 가장 나중에 들어간 데이터(data)는 가장 먼저 나오는

LIFO(Last In First Out) 혹은 FILO(First In Last Out)을 특징으로 가지고 있다.

실사용의 예제로는 브라우저의 뒤로 가기, 앞으로 가기 기능이 있다.

// Stack 구현을 위한 기본 코드

class Stack {
  //stack constructor를 생성합니다.
  constructor() {
    this.storage = {};
    this.top = 0;
  }
  // stack의 사이즈를 구합니다.
  // this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로 size를 구할 수 있습니다.
  // this.top은 스택에 새롭게 추가될 요소의 인덱스를 나타냅니다. 0부터 1씩 증감하며 표현하기 때문에 전체 요소의 개수를 나타낼 수 있습니다
  size() {
    return this.top;
  }
  //stack에 element를 추가합니다.
  //새롭게 추가될 요소의 인덱스를 나타내는 this.top을 키로, 요소를 값으로 하여 storage에 할당합니다.this.top은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
  // stack에서 element를 제거한 뒤 해당 element를 반환합니다.
  // 만약 size가 0이라면 아무 일도 일어나지 않습니다.
  // top-1로 최상단을 설정한 후 변수에 저장하고, 스택에서 삭제합니다.
  // 하나를 제거했으니 top도 감소합니다.
  pop() {
    if (this.size() <= 0) {
      return;
    }
    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    return result;
  }
}

---

큐(Queue)

큐(Queue)는 줄을 서서 기다리다, 대기 행렬이라는 뜻을 가지고 있다.

Queue는 Stack과 반대로,

먼저 들어간 데이터(data)가 먼저 나오고, 나중에 들어간 데이터는 나중에 나오는

FIFO(First In First Out) 혹은 LILO(Last In Last Out)을 특징으로 가지고 있다.

실사용의 예제로는 프린터의 인쇄 대기열이 있다.

// Queue 구현을 위한 기본 코드

class Queue {
  //가장 앞에 있는 요소를 front,
  //가장 뒤에 있는 요소를 rear 라고 했을 때
  //queue constructor 생성
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  // queue의 사이즈를 구합니다.
  // queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 각 값을 알아야 size를 구할 수 있습니다.
  size() {
    return this.rear - this.front;
  }
  // queue에 element를 추가합니다.
  // 새롭게 추가될 요소의 인덱스를 나타내는 this.rear를 키로, 요소를 값으로 하여 storage에 할당합니다. this.rear은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  // queue에서 element를 제거 한 뒤 해당 element를 반환합니다.
  // 만약 size가 0이라면 아무 일도 일어나지 않습니다.
  // this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제합니다.
  dequeue() {
    if (this.size() === 0) {
      return;
    }
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    return result;
  }
}

---

그래프(graph)

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

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.

간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.

하나의 점을 그래프에서는 정점(vertex)이라고 표현하고,

하나의 선은 간선(edge)이라고 한다.

실사용의 예시로는 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션 (길찾기) 등이 있다.

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

그래프 용어

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

---

트리(Tree)

자료구조 Tree는 이름 그대로 나무의 형태를 가지고 있습니다. 정확히는 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있습니다. 그래프의 여러 구조 중 무방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 해서 트리 구조라고 부릅니다.

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

마치 가계도와 흡사해 보이는 이 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조입니다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 뒤에 여러 개의 데이터가 존재할 수 있는 비선형 구조입니다. 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클이 없습니다.

깊이 (depth)

트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있습니다. 루트 노드는 지면에 있는 것처럼 깊이가 0입니다. 위 그림에서 루트 A의 depth는 0이고, B와 C의 깊이는 1입니다. D, E, F, G의 깊이는 2입니다.

레벨(Level)

트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있습니다. depth가 0인 루트 A의 level은 1입니다. depth가 1인 B와 C의 level은 2입니다. D, E, F, G의 레벨은 3입니다. 같은 레벨에 나란히 있는 노드를 형제 노드(sibling Node) 라고 합니다.

높이(Height)

트리 구조에서 리프 노드를 기준으로 루트까지의 높이(height)를 표현할 수 있습니다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1한 값을 높이로 가집니다. 트리 구조의 높이를 표현할 때에는 각 리프 노드의 높이를 0으로 놓습니다.위 그림에서 H, I, E, F, J의 높이는 0입니다. D와 G의 높이는 1입니다. B와 C의 높이는 2입니다. 이때 B는 D의 height + 1 을, C는 G의 height + 1 을 높이로 가집니다. 따라서, 루트 A의 높이는 3입니다.

서브 트리(Sub tree)

트리 구조에서 root에서 뻗어나오는 큰 트리의 내부에, 트리 구조를 갖춘 작은 트리를 서브 트리 라고 부릅니다. (D, H, I)로 이루어진 작은 트리도 서브 트리이고, (B, D, E)나 (C, F, G, J)도 서브 트리입니다.

실사용 예시로는 디렉토리 구조가 있다

---

이진탐색트리(Binary Search Tree)

트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 합니다.

많은 트리의 모습 중, 가장 간단하고 많이 사용하는 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)

먼저, 이진트리(Binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리입니다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있습니다.

이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리(Perfect binary tree)로 나뉩니다.

이진 트리 종류	영어 표기	설명
정 이진 트리	Full binary tree	각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
포화 이진 트리	Perfect binary tree	정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
완전 이진 트리	Complete binary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.

이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있습니다.

이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있습니다. 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야할 문제입니다. 이 문제를 해결하기 위해 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 추가할 수 있습니다.

---

분명히 큐, 스택에 대한 정의와 특징들을 이해하고 코드를 봤는데

추상적인 그림으로 이해한 것과 직접 코드로 구현된 것과는

너무 달라서 당황스럽고, 머리속에서 구현된 코드와 자료구조가 매칭이 안된다.

반복이 답이니까 완전히 이해 될 때까지 자주 보고 또 보고 또 봐야겠다.

---

🌈 Tomorrow

- Graph, Tree, BST, BFS&DFS 학습 및 정리