TIL5 - 2023.09.25

큐 (Queue)

First In First Out(FIFO)라는 개념을 가진 선형 자료구조

Linear Queue(선형 큐) 와 Circular Queue(환형 큐)가 존재

큐의 가장 앞에 있는 원소의 인덱스(위치)는 front로 나타내며, 가장 뒤에 있는 원소의 인덱스(위치)는 rear라고 한다

 

Linear Queue (선형 큐)

• Array(배열)로 구현

class Queue {
    constructor() {
      this.queue = [];
      this.front = 0;
      this.rear = 0;
    }
  
    enqueue(value) {
      this.queue[this.rear++] = value;
    }
  
    dequeue() {
      const value = this.queue[this.front];
      delete this.queue[this.front];
      this.front++;
      return value;
    }
  
    peek() {
      return this.queue[this.front];
    }
  
    size() {
      return this.rear - this.front;
    }
  }

• Linked List(연결 리스트)로 구현

class Node {
    constructor(value) {
      this.value = value;
      this.next = null;
    }
  }
  class Queue {
    constructor() {
      this.head = null;
      this.tail = null;
      this.size = 0;
    }
  
    enqueue(newValue) {
        const newNode = new Node(newValue);
        if (this.head === null) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.size += 1;
    }
  
    dequeue() {
      const value = this.head.value;
      this.head = this.head.next;
      this.size -= 1;
      return value;
    }
  
    peek() {
      return this.head.value;
    }
  }

Circular Queue (환형 큐)

Front와 Rear가 이어져 있는 Queue

Circular Queue는 Linked List로 구현했을 때 이점이 없다

class Queue {
    constructor(maxSize) {
      this.maxSize = maxSize;  
      this.queue = [];
      this.front = 0;
      this.rear = 0;
      this.size = 0;
    }
  
    enqueue(value) {
      if (this.isFull()) {
        console.log("Queue is full.");
        return;
      }
      this.queue[this.rear] = value;
      this.rear = (this.rear + 1) % this.maxSize;
      this.size += 1;
    }
  
    dequeue() {
      const value = this.queue[this.front];
      delete this.queue[this.front];
      this.front = (this.front + 1) % this.maxSize;
      this.size -= 1;
      return value;
    }

    isFull() {
      return this.size === this.maxSize;
    }

    peek() {
      return this.queue[this.front];
    }
}

---

해시 테이블 (Hash Table)

• 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
• 삽입은 O(1)로 수행 키를 알고 있다면 삭제, 탐색도 O(1)로 수행

 

해시 함수

• 입력받은 값을 특정 범위 내 숫자로 변경하는 함수
• 해시 함수는 특정 구현방법 X 마음대로 구현 가능

해시 테이블의 문제점

• 만약 해시 함수의 결과가 동일하여 겹친다면? 해시 충돌(Hash Collsion) 발생

 

해시 충돌(Hash Collision)

선형 탐사법

• 충돌이 발생하면 옆으로 한 칸 이동한다
• 단순하지만 특정 영역에 데이터가 몰릴 수 있고 이동한 버켓(bucket)에서 또 충돌이 발생한다면 충돌이 발생하지 않을 때까지 이동

제곱 탐사법

• 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다
• 충돌이 발생할수록 범위가 커지기 때문에 데이터가 몰리는 것이 선형 탐사법보다 덜하다.

이중 해싱

• 충돌이 발생하면 다른 해시 함수를 이용하여 새로운 인덱스를 만들어낸다

분리 연결법

• 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다
• 충돌이 일어날 경우 다른 인덱스로 이동하지 않는다
• 하나의 버켓의 무한정 늘어날 수도 있는 단점이 있다

해시 테이블 코드 구현

• Array 사용

const table = [];
table["key"] = 100;
table["key2"] = "Hello";
console.log(table["key"]); // 100
table["key"] = 349;
console.log(table["key"]); // 349
delete table["key"];
console.log(table); // undefined

• Object 사용 - 정석적인 방법

const table = {};
table["key"] = 100;
table["key2"] = "Hello";
console.log(table["key"]); // 100
table["key"] = 349;
console.log(table["key"]); // 349
delete table["key"];
console.log(table); // undefined

• Map 함수 사용 - set() 함수로 값을 넣고 get() 함수로 값을 찾기, 메서드 사용으로 편리함

const table = new Map();
table.set("key", 100);
table.set("key2", "Hello");
console.log(table["key"]); // undefind
console.log(table.get("key")); // 100
const object = { a: 1};
table.set(object, "A1"); // Map은 Object도 Key로 쓸 수 있다
console.log(table.get(object)); // A1
table.delete(object);
console.log(table.get(object)); // undefined
console.log(table.keys()); // {'key', 'key2'}
console.log(table.values()); // {100, 'Hello'}
table.clear();
console.log(table.values()); // { }

• Set 사용 - 중복된 내용을 제거할 때 사용 가능

const table = new Set();
table.add("key"); // Key의 Value가 동일하게 들어간다
table.add("key2");
console.log(table.has("key")); // true
console.log(table.has("key3")); // false
table.delete("key2");
console.log(table.has("key2")); // false
table.add("key3");
console.log(table.size); // 2
table.clear();
console.log(table.size); // 0

---

그래프 (Graph)

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
• 정점 집합과 간선 집합으로 표현할 수 있다

그래프의 특징

• 정점은 여러 개의 간선을 가질 수 있다
• 크게 방향 그래프(방향 존재)와 무방향 그래프(방향 존재 X)로 나눌 수 있다
• 간선은 가중치를 가질 수 있다
• 사이클이 발생할 수 있다 ➜ 무한 루프에 빠지지 않도록 사이클을 찾아야 한다

무방향 그래프

• 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다
• A ➜ B 로도 이동이 가능하고 B ➜ A 로도 이동이 가능

방향 그래프

• 간선에 방향성이 존재하는 그래프
• A ➜ B 와 B ➜ A 는 다른 간선으로 취급된다

연결 그래프

• 모든 정점이 이동 가능한 상태인 그래프
• 특정 정점에서 또 다른 정점까지 모든 경우의 수가 이동 가능해야 한다

비연결 그래프

• 특정 정점쌍 사이에 간선이 존재하지 않는 그래프

완전 그래프

• 모든 정점끼리 연결된 상태인 그래프
• 한 정점의 간선의 수 : (모든 정점의 수 - 1)
• 모든 간선의 수 : (모든 정점의 수 - 1) X 정점의 수

사이클

• 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

그래프의 구현 방법

• 인접 행렬(2차원 배열), 인접 리스트(연결 리스트) 두 가지 방식으로 그래프를 표현할 수 있다.

인접 행렬(Adjacency Matrix)

• 정점의 크기 만큼 2차원 배열을 만들고 연결이 안된 상태로 초기화를 한다
• 행렬의 열 부분을 시작 정점 행 부분을 도착 정점으로 두고 true 값을 넣어준다

const graph = Array.from(
    Array(5),
    () => Array(5).fill(false)
);
graph[0][1] = true; // 0 -> 1
graph[0][3] = true; // 0 -> 3
graph[1][2] = true; // 1 -> 2
graph[2][0] = true; // 2 -> 0
graph[2][4] = true; // 2 -> 4
graph[3][2] = true; // 3 -> 2
graph[4][0] = true; // 4 -> 0

인접 리스트(Adjacency List)

• 정점의 수만큼 배열을 만든 후 연결할 정점을 배열에 추가한다

const graph = Array.from(
    Array(5),
    () => []
);
graph[0].push(1); // 0 -> 1
graph[0].push(3); // 0 -> 3
graph[1].push(2); // 1 -> 2
graph[2].push(0); // 2 -> 0
graph[2].push(4); // 2 -> 4
graph[3].push(2); // 3 -> 2
graph[4].push(0); // 4 -> 0