자료구조와 알고리즘(2)

자료구조와 알고리즘은 기초 코딩 능력을 기르기 위해 필요하다.

자료구조 종류

자료구조는 메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표이다.

📌오늘 배운 내용

선형구조

• 배열
• 연결리스트
• 스택
• 큐 📌
• 해시 테이블 📌

비선형구조

• 트리
• 그래프 📌
  
  
  

큐

큐는 First In First Out(FIFO) 형태의 선형 자료구조이다.

배열로 구현하기

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++];
    return value;
  }

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

  size() {
    return this.rear - this.front;
  }
}

연결리스트로 구현하기

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 newValue = new Node(newValue);
    if (this.head === null) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.size--;
    return value;
  }

  peek() {
    return this.head.value;
  }
}

해시 테이블

키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조이다.

해시 함수

😋 해시 함수는 입력받은 값을 특정 범위 내 숫자로 변경하는 함수이다.

🧨해시 충돌 해결법

• 선형 탐사법 - 충돌이 발생하면 옆으로 한 칸 이동한다.
• 제곱 탐사법 - 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
• 이중 해싱 - 충돌이 발생하면 다른 해시 함수를 이용한다.
• 분리 연결법 - 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

배열로 구현하기

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

객체로 구현하기

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

Map으로 구현하기

const table = new Map();
table.set("key1", 100);
table.set("key2", "Hello");
console.log(table["key1"]); // undefined
console.log(table.get("key1")); // 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()); // { 'key1', 'key2' }
console.log(table.values()); // { 100, 'Hello' }
table.clear();
console.log(table.values()); // {}

Set로 구현하기

const table = new Set();
table.add("key1"); // Key와 Value가 동일하게 들어간다.
table.add("key2");
console.log(table.has("key1")); // 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

그래프

그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.

그래프 종류

• 연결 그래프 - 모든 정점이 서로 이동 가능한 상태인 그래프

무방향 그래프

방향 그래프

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

• 완전 그래프 - 모든 정점끼리 연결된 상태인 그래프
  

• 사이클 - 이름 그대로 순환되는 영역을 의미한다.
  

그래프 구현

인접 행렬로 구현하기

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

인접 리스트로 구현하기

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