[Day 4] JavaScript 주요 문법 (4)

 

 

 

자료구조&알고리즘 - 큐

 

1. 큐

- First In First Out 개념을 가진 선형 자료구조

- Linear Queue와 Circular Queue가 존재함

- EnQueue, Rear, Front, DeQueue 

 

1) 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;
  }
}

 

ⓑ 연결리스트로 구현

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++;
  }

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

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

}

 

+ shift는 쓰지 말자! (선형시간 걸림)

 

2) Circular Queue

- Front와 Rear가 이어져 있는 Queue

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("큐가 다 찼습니다.");
      return;
    }
    this.queue[this.rear] = value;
    this.rear = (this.rear + 1) % this.maxSize;
    this.size++;
  }

  dequeue(){
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front = (this.front + 1) % this.maxSize;
    this.size--;
    return value;
  }

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

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

 

💡 실습 문제 - 프린터 큐

 

[프로그래머스] 프린터(JavaScript) (tistory.com)

[프로그래머스] 프린터(JavaScript)

 

 

 

 

자료구조&알고리즘 - 해시 테이블

 

1. 해시테이블 

- 키와 값을 받아 해싱하여 나온 index에 값을 저장하는 선형 자료구조

- 삽입 : O(1), 키를 알고 있다면 삭제, 탐색 O(1)

 

1) 해시 함수 : 입력받은 값을 특정 범위 내 숫자로 변경하는 함수

 

2) 해시 충돌 : 해시테이블의 결과가 같을 때

ⓐ 선형 탐사법 : 충돌이 발생하면 옆으로 한 칸 이동한다

ⓑ 제곱 탐사법 : 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다

ⓒ 이중 해싱 : 충돌이 발생하면 다른 해시 함수를 이용한다.

ⓓ 분리 연결법 : 버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.

 

3) 해시 테이블을 사용하는경우

- 빠르게 값을 찾아야 하는 경우 해시 테이블을 사용하는 것이 좋다

 

4) 자바스크립트 해시 테이블

ⓐ Array 이용 (권장 x)

ⓑ Object 이용 (해시테이블과 거의 유사)

ⓒ map 이용 

const table = new Map();
table.set("key", 100);
console.log(table["key"]);
console.log(table.get("key"));

ⓓ set 이용 : 중복된 내용 없이 저장

 

 

💡 실습 문제 - 베스트 앨범

[프로그래머스] 베스트앨범 (JavaScript) (tistory.com)

[프로그래머스] 베스트앨범 (JavaScript)

 

 

자료구조&알고리즘 - 그래프

 

1. 그래프

- 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조

- 정점 집합과 간선 집합으로 표현할 수 있다.

 

1) 특징

• 정점은 여러개의 간선을 가질 수 있다.
• 크게 방향/무방향 그래프로 나뉜다
• 간선은 가중치를 가질 수 있다
• 사이클이 발생할 수 있다

2) 종류

ⓐ 방향에 따른 그래프

◼ 무방향 그래프(양방향)

- 뱡향이 없는 그래프

- 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다

 

◼ 방향 그래프

- 간선에 방향이 있는 그래프

 

ⓑ 연결에 따른 그래프

◼ 연결 그래프

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

 

◼ 비연결 그래프

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

 

◼ 완전 그래프

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

 

3) 사이클 

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

 

4) 구현 방법

ⓐ 인접 행렬 : 2차원 배열 형태로 선언하여 연결 여부를 값에 넣어준다

let graph = Array.from(
  Array(5),
  () => Array(5).fill(false)
);

graph[0][1] = false;
graph[2][4] = true;
...

 

ⓑ 인접 리스트 : 노드를 기준으로해 2차원 배열로 선언하여 각 노드(인덱스)에 값을 추가하는 방식

const graph = Array.from(
  Array(5),
  () => []);
  
graph[0].push(1);
graph[0].push(3);
graph[0].push(5);
// 0 정점은 1, 3, 5 로 나가는 간선이 있다