[TIL] Day5 큐, 해시테이블, 그래프 개념

Loopy·2023년 6월 7일
KDTTIL데브코스프로그래머스프론트엔드
0

프로그래머스 데브코스 FE

목록 보기
5/18
post-thumbnail

회고

스크럼회의에서 처음으로 각자가 푼 알고리즘 문제를 풀이하는 시간도 가지고 모던 JS 딥다이브 북스터디 시작을 위한 회의도 진행했다.오늘 정말 코어타임동안 바빴던것 같다. 북스터디 깃허브 저장소를 만들기 위해 깃을 사용했는데 너무 오랜만이라 그런지 많이 삐걱댄 것 같다🤖🤖
자료구조의 종류들인 큐, 해시테이블, 그래프에 대한 강의도 들었는데 특히 연결리스트와 관련된 내용들과 베스트앨범 문제는 주말에 보충학습을 해야할 듯 하다. 화이팅 할 수 있다!!🔥

큐

  • First In First Out이라는 개념을 가진 선형 자료구조다.
  • Linear Queue와 Circular Queue가 존재한다.
  • 큐에 값을 넣는것을 enqueue, 빼는것을 dequeue라고 한다.

선형 큐 Linear Queue 표현 방법

  1. 배열로 표현
    한정된 공간의 배열이 꽉찬다면 더이상 큐에 값을 넣을 수 없다. 물론 JS에서는 배열이 자유롭게 증감해서 문제는 없지만 front나 rear의 인덱스 값이 무한대로 커질 수 있다. 따라서 배열에서 공간을 앞당기는 작업이 추가적으로 필요하며 이는 O(n)을 요구한다. 이런 문제를 해결하기 위해 연결리스트로 표현하면 된다.

    //큐를 배열로 표현하기
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() { //front값 반환
    return this.queue[this.front];
  }

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

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

  2. 연결리스트로 표현하기

    • 인덱스에 대한 고민을 하지 않아도 된다.
    • 하지만 배열보단 조금 더 복잡하기 때문에 코테에선 배열로 구현하는 것을 권장한다.
    • front = head, rear = tail
    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.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); //1
queue.enqueue(8);
console.log(queue.size); //3
console.log(queue.peek()); //2
console.log(queue.dequeue()); //3
console.log(queue.dequeue()); //4

⭐ shift 함수는 권장하지 않는다!!
shift()는 선형시간O(n)이 걸리기 때문에 큐에서 기대하는 로직이 수행되지 않는다

원형 큐 Circular Queue

Front와 Rear가 이어져있는 큐. 원형 큐는 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];
  }
}

const queue = new Queue(4);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
queue.enqueue(8);
queue.enqueue(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

해시 테이블

  • 사물함과 유사하다
  • 키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조
  • 삽입은 O(1)이며 키를 알고 있다면 삭제,탐색도 O(1)로 수행한다.

해쉬란?
고기와 감자를 잘게 다져 요리한것
입력받은 key를 잘게 잘라 숫자로 만든다는 것

해시함수

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

만약 해시 함수의 결과가 동일하여 겹친다면?(=해시 충돌이 일어난다)

해시충돌을 해결하기 위한 방법

  1. 선형 탐사법 = 충돌이 발생하면 옆으로 한 칸 이동한다.충돌이 발생하지 않을때까지 이동하여 최악의 경우 O(n)이 걸릴 수 있다.
  2. 제곱 탐사법 = 충돌이 발생한 횟수의 제곱만큼 옆으로 이동
  3. 이중 해싱 = 충돌이 발생하면 다른 해시 함수를 이용
  4. 분리연결법 = 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다. 최악의 경우 하나의 버킷이 무한대로 늘어날 수 있음

해시 테이블 어디에 사용하는가?

  • 학생 정보 관리 시스템

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

JS에서 해시 테이블 사용법

  1. 배열은 객체 타입이라 해시 테이블처럼 사용 가능. 하지만 추천X
const table = [];
table["key"] = 100;
table["key2"] = "Hello";
console.log(table["key"]);
table["key"] = 349;
console.log(table["key"]); //349
delete table["key"];
console.log(table["key"]); //undefined

  1. 객체 이용. 제일 간단하고 정석적인 방법이다.

  2. Map사용

    • set함수를 이용하여 값을 넣고 get함수를 이용하여 값을 찾을 수 있다.
    • 기존 객체와는 다르게 key값으로 Object나 복잡한 타입도 key로 사용 가능하다.
    • 객체의 경우 들어오는 값이 정수가 아닌경우 전부 문자열로 바꿔버리기 때문에 다양한 타입을 넣고 싶다면 Map을 쓰는것이 좋다.
    • 여러 편한 메소드 제공한다.
    • 순회를 편하게 할 수 있다.

  3. Set 사용

    • Set은 키와 값이 동일하게 저장되는 방식 이용한다.
    • 일종의 집합 연산이다.
    • 중복된 내용 제거할 때 많이 사용한다.

그래프

  • 정점(Node)과 정점 사이를 연결하는 간선(edge)으로 이루어진 비선형 자료구조다
  • 정점 집합과 간선집합으로 표현할 수 있다.
  • 예시) 지하철 노선도, 드라마 인물관계도, 페이지랭크
  • 정점은 여러 개의 간선을 가질 수 있다.
  • 크게 방향그래프와 무방향 그래프로 나눌 수 있다.
  • 간선은 가중치를 가질 수 있다.
  • 사이클이 발생할 수 있다.

무방향 그래프

  • 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.
  • 표현하기에 (A,B)와 (B,A)는 같은 간선으로 취급된다.
  • ex) 양방향 통행 도로

방향 그래프

  • 간선에 방향성이 존재하는 그래프다
  • 양방향으로 갈 수 있더라도 <A,B>와 <B,A>는 다른 간선으로 취급된다.
  • 예시) 일방 통행

연결 그래프

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

비연결 그래프

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

완전 그래프

  • 모든 정점끼리 연결된 상태인 그래프
  • 한 정점의 간선 수 = 모든 정점의 개수의 -1
  • 모든 간선의 수 = (모든 정점 개수 -1) * 정점 개수

사이클

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

그래프 구현 방법

  1. 인접 행렬로 나타내기 → 이차원 배열 이용
  2. 인접 리스트로 나타내기 → 연결리스트 이용

참고자료

해시함수 위키백과 https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98

프로그래머스 데브코스 FE 강의

profile
Loopy
이전 포스트

[TIL] Day4 자료구조

다음 포스트

[TIL] Day6 트리, 힙, 트라이, 정렬

0개의 댓글