JS로 알고리즘하기

자바스크립트로 알고리즘 풀기 외길 인생을 즐기고 있습니다 .. ✨

자바스크립트로 알고리즘을 풀면 가끔 너무 외로운 순간들이 있습니ㄷr ..

예를 들면 2022 카카오 테크 인턴십 - 두 큐 합 같게 만들기

파이썬 Queue 로 굴리면 정답인데, JS 배열 이용하면 광탈인 문제가 있다

class를 이용해서 직접 구현해서 풀어야 정답인 그런 문제들.. 🔕

하지만 자식같은 자바스크립트를 내칠 수 없길래 차근차근 구현을 정리해보려고 한다 🫶

 

---

Queue

- 추천 문제 : 2022 카카오 테크 인턴십 - 두 큐 합 같게 만들기 

 

push, pop은 기존 배열에서 O(1)로 가능하지만, 큐와 같은 경우에는 push 는 O(1)이지만, shift 는 O(n)이다.

배열을 사용하면 큐를 편리하게 구현할 수 있을 것 같은데 아무래도 enequeue에 대한 부분에 O(n)을 벗어날 수 없을 것 같다. 따라서 enqueue에 대응하기 위해서 linkedList를 이용해서 큐를 구현해보기로 한다.

 

class Node {
  constructor(n) {
    this.value = n;
    this.next = null;
  }
}

class Q {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  enq(n) {
    const node = new Node(n);

    if (!this.size) this.head = node;
    else this.tail.next = node;

    this.tail = node;
    this.size++;
  }

  deq() {
    if (!this.size) return;

    const n = this.head.value;
    this.head = this.head.next;

    // head만 남고 next가 없는 경우 꼬리를 null로 작업해준다.
    if (!this.head) this.tail = null;
    this.size--;
    return n;
  }

  _size(){
    
  }
}

MinHeap

- 주로 사용하는 곳 : 다익스트라

- 추천 문제 : 백준 1753 최단경로

 

 

다익스트라에서 배열을 계속 갱신해주어야한다. ( Dijk[i] : i번째 index는 i번째까지 오는 최단 경로)

그 때 갱신 조건을 방문하지 않은 노드 중 최소 값으로 하는 순간이 있는데, 그 때 유용하다.

물론 for문을 다 돌면 되지만 .. 😅 가끔 시간 초과 (배열 순회는 O(n)) 가 나는 경우가 있기 때문에 O(1)만에 찾을 수 있는 MinHeap 을 이용하는 것이 좋다. ( heap 에 값을 넣는것은 O(logN) 이다. ) 

O(logN)이 될 수 있는 이유는 부모만 비교해서 올라가면 되기 때문이다. 

 

최상단에 있는 숫자만 찾으면 최솟값이 나오는 것이기 때문에 O(1)이 걸린다.

 

1 ) Insert 함수 구현하기 ( * MaxHeap 예제)

1. 만약 20이라는 숫자를 추가하고 싶다면, 일단 마지막에 위치시킨다.
2. 부모와 비교를 한다. (반복)
   1. 만약, 현재 부모가 자신보다 같거나 크다면 반복문 종료
   2. 현재 내가 비교하는 노드(20)이 root 노드에 있다면 반복문 종료

 

2)  힙에서 최상단의 값을 가져오고, 재정렬 (*MaxHeap 예제)

 

1. Max 값을 없애준다. (만약에 최솟값 재갱신이 필요없다면 이걸로 마무리)
2. 마지막 노드에 있는 값을 root 노드로 보내주고, 마지막 노드를 삭제한다.
3. 자식과 비교를 해준다. (반복문)
   1. 자식 노드가 아예 없는 경우
   2. 왼쪽 자식만 있는 경우
   3. 왼쪽, 오른쪽 자식이 모두 있는 경우 (현재에서 더 큰 값을 선정해주어 교체해준다.)

 

3 ) 코드

코드에서는 단순히 최솟값을 찾아주는 것이 아니라, 최솟값을 계속 갱신해주어야 하기 때문에 Child 노드와 Parent 노드를 비교해주어야하기 때문에 O(1)까지는 나오지 못한다.

class Heap {
  constructor() {
    this.heap = [null];
  }

  insert (n){
    this.heap.push(n);

    let current = this.heap.length - 1;
    let parent = Number.parseInt(current / 2);

    // 부모가 자신보다 클때 부모와swap
    while (current!==1 && this.heap[parent] >= this.heap[current]) {
      let swap = this.heap[parent];
      this.heap[parent] = this.heap[current];
      this.heap[current] = swap;

      current = parent;
      parent = Number.parseInt(current / 2);

      // 현재 current가 루트 노드일 경우 break
      if (current === 1) break;
    }
  };

  checkChild(current){
    // 양쪽이 없는 경우
    if (current * 2 >= this.heap.length) return null;
    // 왼쪽만 있는 경우
    else if (current * 2 + 1 >= this.heap.length) return current * 2;
    else {
      // 모두 있는경우
      return this.heap[current * 2 + 1] < this.heap[current * 2]
        ? current * 2 + 1
        : current * 2;
    }
  };

  pop () {
    // null 인 경우
    if (this.heap.length === 1) return;
    // 하나만 남은 경우
    if(this.heap.length-1 === 1) return this.heap.pop();

    const n = this.heap[1];
    this.heap[1] = this.heap.pop();

    let current = 1;
    let child = this.checkChild(current);

    while (child && this.heap[current] > this.heap[child]) {
      const swap = this.heap[child];
      this.heap[child] = this.heap[current];
      this.heap[current] = swap;

      current = child;
      child = this.checkChild(current);
    }
    return n;
  };

  show () {
    for (let i = 1; i < this.heap.length; i++) console.log(this.heap[i]);
  };
}