[데브코스] TIL - 4일차

오늘 공부한 내용 💻

• 큐(Queue)
• [실습] 프린터
• 프린터 문제풀이
• 해시 테이블
• [실습] 베스트 앨범
• 베스트 앨범 문제풀이
• 그래프
  
  

어려웠던 내용 🤢

- 큐(Queue)

• 먼저 들어간 값이 먼저 나오는 FIFO(First In First Out)인 선형 자료구조!

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

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

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

const queue = new Queue();

배열 또는 연결 리스트로 구현할 수 있다. 위 코드는 배열로 구현한 것.

자바스크립트로 큐 구현할 때 shift/unshift 사용하면 선형시간(O(n))이 소요되므로 큐를 올바르게 사용하기 위해서는 front/rear로 구현하는 것이 올바름 !!

- 해시 테이블(Hash Table)

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

• 삽입은 O(1)이며 키를 알고 있다면 탐색, 제거도 O(1)로 수행한다!
  
  

- 해시 함수

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

• 각각 다른 키의 해시함수의 결과가 동일하다면? 해시 충돌(Hash Collision) !!

• 해시 충돌 해결법
  1) 선형 탐사법: 충돌이 발생하면 인덱스를 한 칸 옆으로 이동해 저장한다.
  2) 제곱 탐사법: 충돌이 발생한 횟수의 제곱만큼 옆으로 이동해 저장.
  3) 이중 해싱: 충돌이 발생하면 다른 해시 함수를 이용.
  4) 분리 연결법: 버킷의 값을 연결리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가해 나간다.
  

더 공부할 내용 📃

• [실습] 프린터 다시 풀어보기
• [실습] 베스트 앨범 어떻게든 이해 해보기 ,,, 자신 없긔 ,,
  
  

느낀점 👀

> ' 나... 뒤쳐지고 ,,, 있는 걸지도 ,,,?'

어제에 이어서 자료구조&알고리즘 수업 !
큐에 대해서는 정확하게 알고 있다고 생각했는데 막상 구현을 해보려니 할 수가 없더라 ... 객체지향 프로그래밍 아직 너무 익숙하지가 않아요 ...

그리고 좀 징징대자면 ...
실습이 두개나 있는 날이었는데 프린터는 shift없이는 구현을 못하겠고 ,,,
베스트 앨범은 전적으로 손도 대지 못해서 약간은 우울했던 하루 ...
아직 4일차인데 벌써 벅찬 느낌이 들어서 살짝은 무섭지만 ...

일희일비 하지말자 ~ 너 아직 갈길이 멀그든 ~~

참고 사이트 🙄

- https://programmers.co.kr/