230925 [Day5] JavaScript 주요 문법 (4)

자료구조&알고리즘 - 큐

 

 

• 큐는 FIFO(first in first out)이라는 특징을 가진 선형 자료구조이다.
• enqueue함수를 통해서 데이터를 뒤에 집어넣고 dequeue함수를 통해서 젤 앞에 있는 데이터를 빼고 peek함수를 통해서 젤 앞에 있는 데이터를 제공하는 메소드들이 있다.
• 언제 이 자료구조를 사용할 수 있을까?
  • 현실세계에서는 줄을 세울때 사용된다고 예상할수 있다. 순서대로 빠져나가고 들어갈때 사용될수 있는 자료구조이다.

 

Linear Queue 선형 큐

• Array로 표현하기
  • 간단하게 구현할수 있지만 array 특징인 dequeue시 빈공간은 채워지지 않게된다.
    • 그로 인해서 공간이 꽉차게 되면 더이상 채워지지 않지만 js는 동적으로 자유자재로 늘어난다는 점에서 괜찮긴하나 front, rear이 무한정 커질 수 있고 빈공간을 채워줘야하는데 선형시간이 걸린다는 단점이 있다. 
      • 코딩테스트에서는 배열을 사용하자!

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();
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

 

• Linked List로 구현하기
  • head=front, tail=rear라고 생각하고 구현하면 편하다.
  • 배열과 다르게 인덱스에 대한 고민은 하지 않아도 된다.

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

 

Circular Queue

• 원형큐는 한정된 공간에서 효율적으로 사용할때 쓰는 자료구조이다.(연결리스트로 구현하는거랑 크게 다른점 x)
• front와 rear가 이어져있는 큐이다.
• 구현할때 특징이 최대크기로 나머지 연산을 진행한다.
  • 이 연산을 통해서 범위가 벗어날 경우 처음부터 실행된다는 점이 있어서 공간을 효율적으로 사용할 수 있다.

 

• Array로 표현하기

class Queue {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.queue = [];
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }
  
  enqueue(value) {
    if (this.inFull()) {
      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;
    return value;
  }
  
  isFull() {
    return this.size === this.maxSize;
  }
  
  peek() {
    return this.queue[this.front];
  }
}

 

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

 

• 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조
  • 해싱이란 어떤 값을 특정한 함수를 통해 다른 값으로 변환하는 것을 말한다.
• 위와 같이 저장하고자 하는 값의 주소명을 해시테이블을 통해서 인덱스로 변환하고 그 인덱스에 저장하고자 하는 값을 넣어주면 어떤 효과를 기대할 수 있을까?
  • 배열의 경우 어떤 값에 접근할 때, 그 값의 인덱스를 알고있다면, 시간복잡도는 O(1)이다.
  • 비슷하게, 해시함수는 하나의 값이 들어오면 항상 같은 값을 뱉어내기 때문에, 주소명을 통해 아주 빠른속도로 데이터에 접근 할 수 있다.
    • 해시함수 : 입력받은 값을 특정 범위 내 숫자로 변경하는 함수
  • 이때, 해시함수를 통해 값과 주소를 저장하는 곳을 버킷(bucket)이라고 한다.
    • 해시 테이블의 index는 buket / 테이블의 각 요소 : 키와 값을 저장

 

해시 테이블의 문제점

• 만약 학생수가 많이 증가 되어서 선생님이 실수로 같은 번호를 줬을때 어떻게 대처해야할까?
  • 해시 함수 결과가 동일할때 hash 충돌이 발생한다.
  • 대처방법 4가지
    • • 선형 탐사법
        • 충돌 발생 → 옆으로 한 칸 이동
        • 이동한 곳에서 또 충돌이 발생하면 충돌이 발생하지 않을 때 까지 이동
        • 최악의 경우 : O(n) → 계속 한칸씩 이동! (탐색에 선형시간이 걸릴 수 있음)
      • 제곱 탐사법
        • 충돌 발생 지점에서 충돌이 발생한 횟수의 제곱 만큼이동
        • 충돌이 발생할수록 범위가 커진다.
        • 데이터 쏠림 현상이 줄어든다.
  • • • 이중해시
        • 충돌 발생 → 또 다른 해시 함수 실행
      • 분리연결법
        • 충돌 발생 → 연결리스트로 만들어 값 추가
        • 단점 : 하나의 버켓에 쏠림 발생할수 있다.

 

js에서 해시 테이블 사용법

Array(추천x) , Object(제일 간단,정석)

const table = []; //object는 {}
table["key"] = 100;
table["key2"] = "Hello";
console.log(table["key"]); // 100
table["key"] = 349;
console.log(table["key"]); // 349
delete table["key"];
console.log(table["key"]); // undefined

 

Map

const table = new Map();
table.set("key", 100);
table.set("key2", "Hello");
console.log(table["key"]); //undefined
console.log(table.get("key")); // 100
const object = { a: 1 };
table.set(object, "A1");
console.log(table.get(object)); // A1
table.delete(object);
console.log(table.get(object)); // undefined
console.log(table.keys()); // { 'key, 'key2' }
console.log(table.values()); // { 100, 'Hello' }
table.clear();
console.log(table.values()); // {}

 

Set

const table = new Set();
table.add("key");
table.add("key2");
console.log(table.has("key")); // true
console.log(table.has("key3")); // false
table.delete("key2");
console.log(table.has("key2")); // false
table.add("key3");
console.log(table.size); // 2
table.clear();
console.log(table.size); // 0

 

 

그래프

 

• 정점(vertex,node)과 간선(edge)로 이루어진 비선형 자료구조이다.
• 정점과 정점이 간선으로 연결되어 있으면 인접한다고 한다.
  • 정점은 여러 개의 간선을 가질 수 있다.

• 간선은 가중치를 가질 수 있다.(역과 역 사이 거리) 
• 사이클이 발생할 수 있다. (서로 순환이 되는 부분) → 탐색시 무한루프 발생 주의! 

• 그래프는 방향 유무에 따라 무방향 그래프와 방향 그래프로 나눌 수 있다.
  • 방향 그래프는 간성에 방향성이 존재한다.
  • 양방향으로 갈 수 있더라도 <A,B>와 <B,A>는 다른 간선으로 취급 ex)일방 통행 
  • 방향 그래프는 단방향그래프와 양방향그래프로 나눌 수 있다.
    • 단방향 그래프는 한쪽으로만 정점간의 이동이 있다. ex)a->b
    • 양방향 그래프는 각각의 정점에서 연결된 정점으로 이동할 수 있다. ex)a->b, b->a
  • 무방향 그래프는 정점이 간선으로 연결되어 있는데, 딱히 방향이 없어서 각각의 정점에서 연결된 정점으로의 이동이 자유롭다.
  • ex) a<->b

 

• 그래프는 연결 유무에 따라 연결 그래프와 비연결 그래프로 나눌 수 있다.
  • 연결 그래프
    • 모든 정점이 서로 이동이 가능한 상태
  • 비연결 그래프
    • 특정 정점쌍 사이에 간선이 존재하지 않은 그래프
    • 여기서 파생된게 연결된 컴포넌트(연결된 하위 그래프 = 비연결 그래프)
    • 연결된 컴포넌트도 코테에 등장

 

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

 

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

 

 

그래프의 구현 방법

인접 행렬 

이중 배열을 만들고 노드끼리 연결되어있으면 배열 값을 표시해주는 방법

const graph = Array.from(Array(5), () => Array(5).fill(false));
graph[0][1] = true; // 0 -> 1
graph[0][3] = true; // 0 -> 3
graph[1][2] = true; // 1 -> 2
graph[2][0] = true; // 2 -> 0
graph[2][4] = true; // 2 -> 4
graph[3][2] = true; // 3 -> 2
graph[4][0] = true; // 4 -> 0

 

인접 리스트

연결 되어있는 노드를 연결리스트를 통해 추가해서 기록하는 방법

const graph = Array.from(Array(5), () => []);
graph[0].push(1); // 0 -> 1
graph[0].push(3); // 0 -> 3
graph[1].push(2); // 1 -> 2
graph[2].push(0); // 2 -> 0
graph[2].push(4); // 2 -> 4
graph[3].push(2); // 3 -> 2
graph[4].push(0); // 4 -> 0