큐

저번 게시물에서 스택은 LIFO(Last In First Out) 구조라고 배웠다.

큐는 FIFO(First In First Out) 구조로서 먼저 들어간 데이터를 먼저 뱉어내게 된다.

편의점 알바를 해봤다면 단박에 이해가 갈 수 있는데, 음료를 채울 때, 음료매대 뒤에서 차례로 채우면 제일 먼저 넣은 음료수를 밖에서 가장 먼저 꺼내게 된다.

자바스크립트에서 큐는 배열이나 스택을 이용해서 구현 할 수 있는데, 배열을 이용하는 방법이 더 간단하다!

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(val) {
    this.queue[this.rear++] = val;
  }

  dequeue() {
    const val = this.queue[this.front];
    delete this.queue[this.front++];
    return val;
  }
  peek() {
    return this.queue[this.front];
  }
  size() {
    return this.rear - this.front;
  }
}

위의 코드에서
큐에다 데이터를 넣을때 enqueue라고 하고,데이터를 꺼내는걸 dequeue라고 한다.
dequeue할때 꺼내지는 데이터는 앞쪽,front에 있다고 하고, 가장 최근에 enqueue된 데이터를 뒷쪽,rear에 있다고 한다.
그리고 front에 있는 데이터를 조회하는걸 peek한다고 한다.

해시테이블

데이터를 해싱한다는 말을 들어봤을 수 있다.
해싱이란 어떤 값을 특정한 함수를 통해 다른 값으로 변환하는 것을 말한다.
해시테이블이란 자료구조는 어떤 자료를 저장하는데, 이때, 해싱을 이용해서 저장하겠다는 뜻이다.

위와 같이 저장하고자 하는 값의 주소명을 해시테이블을 통해서 인덱스로 변환하고 그 인덱스에 저장하고자 하는 값을 넣어주면 어떤 효과를 기대할 수 있을까?

배열의 경우 어떤 값에 접근할 때, 그 값의 인덱스를 알고있다면, 시간복잡도는 O(1)이다. 비슷하게, 해시함수는 하나의 값이 들어오면 항상 같은 값을 뱉어내기 때문에, 주소명을 통해 아주 빠른속도로 데이터에 접근 할 수 있다는 것이다.

이때, 해시함수를 통해 값과 주소를 저장하는 곳을 버킷(bucket)이라고 한다.

하지만 주의해야할 사항도 존재한다.
만약에 철수라는 값과 영희라는 값을 해시함수에 집어넣어서 인덱스를 받는데, 인덱스 값이 같다면? 이를 해시충돌이라고 한다.

해시충돌을 최대한 피하기 위한 방법으로는

• 충돌이 더 적게 발생하는 해시함수를 사용한다.
• 충돌시 연결리스트에 연결을 한다.
• 충돌시 트리에 연결을 한다.
• 충돌시 다음 버킷에 값을 넣는다.
• 충돌시 충돌이 일어난 횟수의 제곱만큼 떨어진 버킷에 값을 넣는다.
• 충돌시 다른 해시함수를 통해 해싱해준다.

각각 방식의 이름은 퀴즈 느낌으로 각자 알아서 찾아보는걸로...ㅎㅎ;;

참고로 js에서 해싱은 객체의 key-value 형태를 이용하거나 Map()객체를 이용하는 방법이있다!

그래프

이런 그래프를 말하는게 아니고,,,

그래프는 정점(vertex,node)과 간선(edge)로 이루어진 비선형 자료구조이다. 정점과 정점이 간선으로 연결되어 있으면 인접한다고 한다.

그래프의 종류 크게 는 무방향그래프와 방향그래프로 나눌 수 있고, 방향그래프는 단방향그래프와 양방향그래프로 나눌 수 있다.

무방향그래프는 정점이 간선으로 연결되어 있는데, 딱히 방향이 없어서 각각의 정점에서 연결된 정점으로의 이동이 자유롭다. ex) a<->b

방향그래프는 그럼 방향이 있다는 얘기고
단방향그래프는 한쪽으로만 정점간의 이동이 있고,
ex)a->b
양방향그래프는 각각의 정점에서 연결된 정점으로 이동할 수 있다는 뜻이다.
ex)a->b, b->a

비연결그래프, 완전그래프, 사이클등은 역시 궁금하면 찾아보는 걸로!

그래프를 사용하는 이유는 현실의 관계를 표현하기가 편해서라고 생각한다. 친구관계가 막 큐처럼 "나는 무조건 내 앞뒤 두명하고만 친구야" 그런건 아니니까.... 사물간의 연결관계 등등 도 나타내기 쉽기도 하다.

js에서 그래프를 구현하는 방법으로는

• 인접행렬 : 이중배열을 만들고 노드끼리 연결되어있으면 배열값을 표시해주는 방법
• 인접리스트 : 연결되어있는 노드를 연결리스트를 통해 추가해서 기록하는 방법

이 있다!

이미지 출처

https://www.geeksforgeeks.org/