[Algorithm] 큐 | 해시테이블 | 그래프 | 230607 |*

Chaeyeon Lee·2023년 6월 7일

TIL 국비지원교육 그래프 데브코스 코딩부트캠프 큐 프로그래머스 데브코스 프론트엔드 데브코스 해시테이블

데브코스 TIL

목록 보기

6/16

TIL

필자 프로그래머스 코딩테스트 lv1,
오늘자 강의의 실습 문제로 lv2, 3이 대거 나오면서 와장창 털렸다.

알고리즘을 공부하는 시간을 따로 만드는 게 좋을 것 같다는...판단...
실력 늘면 혼자 실습 문제 풀어보고 여기다 인증할 거임

Queue 큐

FIFO방식
linear queue와 circular queue가 존재한다.

(1) Linear Queue

배열과 연결리스트, 두 가지 방식으로 구현이 가능하지만, 배열은 dequeue 후 앞당기는 작업이 필요하므로 조금 더 복잡하다.

링크드리스트로 구현하는 방법

자바스크립트로 구현하기

//Array로 구현하기 : 구현하기 쉬우므로 코딩테스트에서 사용하기 추천
class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enequeue(value) {
    this.queue[this.rear++] = value;
  }

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

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

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

const queue = new Queue();
queue.enequeue(1);
queue.enequeue(2);
queue.enequeue(4);
console.log(queue.dequeue()); //1
queue.enequeue(8);
console.log(queue.size()); //3
console.log(queue.peek()); //2
console.log(queue.dequeue()); //2
console.log(queue.dequeue()); //4

//----------------------------
//LinkedList로 구현하기: 배열로 구현하는 것보다 복잡하므로 코딩테스트에서는 배열로 구현할 것을 추천. shift는 수가 작을 때 권장
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;
  }
}

const queue = new Queue();
queue.enequeue(1);
queue.enequeue(2);
queue.enequeue(4);
console.log(queue.dequeue()); //1
queue.enequeue(8);
console.log(queue.size); //3
console.log(queue.peek()); //2
console.log(queue.dequeue()); //2
console.log(queue.dequeue()); //4

(2) Circular Queue

front와 rear가 이어져 있는 큐. 연결리스트로 구현했을 때 딱히 이점이 없다.

//Array로 구현하기: JS에서 circular 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("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];
  }
}

const queue = new Queue(4);
queue.enequeue(1);
queue.enequeue(2);
queue.enequeue(4);
queue.enequeue(8);
queue.enequeue(16); //Queue is full
console.log(queue.dequeue()); //1
console.log(queue.dequeue()); //2
console.log(queue.size); //2
console.log(queue.peek()); //4
queue.enqueue(16);
queue.enqueue(32);
console.log(queue.isFull()); //true

Queue 실습하기
프로그래머스 lv2. 프로세스: https://school.programmers.co.kr/learn/courses/30/lessons/42587
해설: [Day5] 프린터 문제 풀이

Hash Table 해시테이블

해시테이블은 한정된 배열 공간에 키를 인덱스로 변환하여 값을 넣는다. like 사물함
키와 값을 받아 키를 해싱하여 나온 인덱스에 값을 저장하는 선형 자료구조.

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

해시충돌: 입력 값의 결과가 동일한 경우

해시 충돌 해결법
(1) 선형 탐사법: 충돌이 발생하면 옆으로 한 칸 이동한다.

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

(3) 이중해싱: 충돌 발생시 다른 해시 함수를 이용한다.

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

해시테이블은 언제 사용할까?

ex) 학생 정보를 관리하는 출석부

연결리스트 사용 시 학생 정보를 찾을 때 너무 오래 걸림
배열은 인덱스를 모를 경우 오래 걸림
해시테이블은 빨리 찾을 수 있음!

HashTable 실습하기
프로그래머스 lv3. 베스트앨범: https://school.programmers.co.kr/learn/courses/30/lessons/42579
해설: [Day5] 베스트앨범 문제 풀이
참고하면 좋을 블로그

Graph 그래프

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조. 정점 집합과 간선집합으로 표현할 수 있다.
vertex : 정점. 노드
edge : 간선. 노드 사이를 연결하는 선
weighted/unweighted : 가중/비가중

ex) 지하철 노선도, Page Rank 알고리즘

230609
BFS/DFS를 공부하다가, 그래프랑 트리랑 다른 게 뭐야 싶은 의문이 들었는데 찾아보니 트리는 그래프의 일종이라고 한다. !! 역쉬
대신, 트리와 달리 부모 노드나 root노드는 정해져 있지 않다. 그래프에서 노드(정점)은 모두 똑같이 취급되며 서로 다른 방식으로 연결된다.