TIL5 - 2023.09.25

👨‍💻 TIL

TIL5 - 2023.09.25

zunwon 2023. 9. 25. 17:37

큐 (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