자바스크립트로 자료구조 구현하기

가연·2026년 1월 8일
Dequequeue우선순위큐

알고리즘

목록 보기
6/6
post-thumbnail

알고리즘을 공부하면서 자바스크립트는 큐나 덱, 우선순위 큐처럼 알고리즘에 자주 쓰이는 자료구조가 표준 라이브러리로 제공되지 않아 해당 자료구조를 사용하는 문제들을 피해왔다. 하지만 알고리즘을 풀면서 시간복잡도나 공간복잡도를 고려하려면 자료구조를 이해하는게 꼭 필요하다는 생각이 들어 정리해보았다.
바킹독 유튜브 를 참고했다.

큐 Queue

가장 먼저 들어온 원소가 먼저 나오는 것. (FIFO)
원소 추가, 제거의 시간복잡도가 O(1)이다.

자바스크립트 리스트에서 pop 할땐 shift() 를 사용하게 되면 시간복잡도가 O(n)이다. 따라서 큐를 사용해 시간초과가 난다면 구현해서 사용해야한다.

구현

큐는 push 할 때 tail(arr.length) 증가, pop 할 때 head 증가로 간단하다. 

class Queue {
  constructor() {
    this.arr = [];
    this.head = 0;
  }

  push(x) {
    this.arr.push(x);
  }

  pop() {
    if (this.empty()) return undefined;
    return this.arr[this.head++];
  }

  size() {
    return this.arr.length - this.head;
  }

  empty() {
    return this.size() === 0;
  }
}

백준 출근(13903) 문제에서도 pop할 때 맨 앞 원소를 가져오기 위해 queue.shift() 를 사용하면 시간초과가 난다. 이때 큐를 구현하거나 다음과 같이 간단하게 head 만 이용해도 된다. 

const queue = [];
let head = 0;
const cur = queue[head++]; // dequeue (O(1))

덱 Deque

덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이다.
원소 추가 ,삭제 , 앞-뒤 확인의 시간복잡도 모두 O(1)이다.

구현

앞 뒤에 요소를 빠르게 삽입하기 위해서는 객체를 사용해 주는게 좋다.(shift, unshift는 O(n))
key 에는 인덱스를, value 에는 값을 넣어주고,front 와 back 을 옮겨가며 덱의 앞과 뒤를 가리키도록 한다. 이렇게 하면 다음과 같은 상태로 저장이 되고, 배열과 달리 자유롭게 맨 앞에 요소를 추가할 수 있게 된다.

data = {
  -1:3
  0:2
  1:5
}

  • front는 현재 가장 앞에 있는 값의 위치

  • back은 다음에 뒤로 push할 위치

    이제 front와 back 을 이용해서 push, pop을 할 수 있다.

  • push
    pushFront(7) 와 pushBack(4) 을 해주면 각각 다음과 같이 된다.
    front는 현재 가장 앞에 있는 값의 위치이므로 값을 넣어주려면 front--를 해주고, back 은 다음에 뒤로 push 할 위치이므로 back 의 위치에 넣은 후 back++를 해준다.

  • pop
    위와 동일하다. front는 값 기준이므로 현재 값을 꺼내 제거한 후, front++를 해준다. back 은 비어있으므로 back--를 해준 후 그 값을 꺼내 제거해준다.

코드로 구현하면 다음과 같다. 위 개념대로 null값만 주의해서 구현해주면 된다.

class Deque {
  constructor() {
    this.data = {};
    this.front = 0;
    this.back = 0;
  }

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

  isEmpty() {
    return this.size() === 0;
  }

  pushFront(value) {
    this.front--;
    this.data[this.front] = value;
  }

  pushBack(value) {
    this.data[this.back] = value;
    this.back++;
  }

  popFront() {
    if (this.isEmpty()) return null;
    const value = this.data[this.front];
    delete this.data[this.front];
    this.front++;
    return value;
  }

  popBack() {
    if (this.isEmpty()) return null;
    this.back--;
    const value = this.data[this.back];
    delete this.data[this.back];
    return value;
  }
}

우선순위 큐 (최소/최대 heap)

우선순위큐는 우선순위가 가장 높은 원소가 먼저 나오는 큐 이다.
최소 힙을 사용하면 최소값이 먼저, 최대 힙을 사용하면 최대값이 먼저 pop된다.

힙

힙은 이진트리로 구성된다. 최소(최대) 힙은 최소값을 찾기 위한 힙으로 루트가 가장 최소(최대)가 된다.

[사진 : 바킹독 우선순위 큐]

최대힙은 다음과 같이 동작한다.

  • 삽입 : 배열의 맨 마지막에 push
    • 부모 노드의 값 < 방금 삽입한 노드 값 이라면 자리를 바꿔준다.
    • 부모를 확인하며 바꿔주면 최악의 경우 최대 높이까지만 비교해주면 된다 → O(logN)
  • 최댓값 삭제
    • 가장 최상위 노드와 가장 마지막 노드를 바꾼 후 최상위 노드를 삭제해준다.
    • 첫번째 노드를 최대힙의 조건을 지켜 조정해준다 : 부모노드 > 자식노드가 되도록
      • 자식들보다 값이 더 작다면 swap한다.
      • 이때, 왼쪽과 오른쪽 child 를 비교해서 더 큰 child와 바꿔준다.

배열로 살펴보기

heap 은 배열 기반으로 구현이 가능하다. 다음은 0-based 힙을 배열로 나타낸 것이다.
1번지의 왼쪽, 오른쪽 자식은 각각 1x2=2 와 1x2+1=3 인 것을 확인할 수 있다.
따라서 x번지의 왼쪽, 오른쪽 자식 : 2x,2x+1, x번지의 부모: (x-1)/2 이다.

이 개념들을 활용해서 구현하면 다음과 같다. 이때 다음 코드는 0-based 힙 이라서 0번째 요소에는 수식이 성립하지 않는다. 따라서 힙의 길이가 1일때(0번째)를 따로 막아주었다. 이게 싫다면 1-based 힙으로 구현해도 된다.

구현

구현할때는 다음과 같이 순서대로 리스트업을 한 후 코드로 바꿔주었다. 이렇게 코드를 요구사항대로 상세하게 정리해주면 코드를 보지 않고도 쉽게 생각이 났다.

  • push
    • 최대 힙 → 값이 큰 애들을 위로 올리기
    • 힙에 v 를 넣고, 힙의 길이가 2보다 크면 비교 시작
    • i = 방금 넣은 v 의 인덱스, 이거랑 부모 노드부터 쭉 확인해보기
    • 부모 노드는 (x-1)/2 → 부모노드의 값이 더 크다면 더 올라갈 수 없으므로 중단
    • 현재 넣은 값이 더 크다면 부모와 위치를 바꿔주고, i 값을 p로 바꿔주기.
  • pop
    • 힙 길이가 1이면 그대로 pop
    • 최솟값(top = h[0])을 저장
    • 마지막 노드를 h[0]에 올림
    • 아래로 내려가며 재조정
      • 왼쪽 / 오른쪽 자식 중 존재하는 것만 비교
      • 두 자식이 모두 있으면 더 큰 자식을 선택
      • 선택한 자식이 부모보다 크면 swap
      • 그렇지 않으면 break
    • 저장한 top 반환
class MaxHeap {
  constructor() {
    this.h = [];
  }
  push(v) {
    let h = this.h;
    h.push(v);
    let i = h.length - 1;
    while (i > 0) {
      let p = Math.floor((i - 1) / 2)
      if (h[p][0] >= h[i][0]) break;
      [h[p], h[i]] = [h[i], h[p]];
      i = p;
    }
  }
  pop() {
    let h = this.h;
    if (h.length === 0) return null;
    if (h.length === 1) return h.pop();
    const top = h[0];
    h[0] = h.pop();
    let i = 0;
    while (true) {
      let l = i * 2 + 1, r = l + 1, m = i;
      if (l < h.length && h[l][0] > h[m][0]) m = l;
      if (r < h.length && h[r][0] > h[m][0]) m = r;
      if (m === i) break;
      [h[i], h[m]] = [h[m], h[i]];
      i = m;
    }
    return top;
  }
}

예시

백준 옥수수밭

선택할 수 있는 곳 중 가장 가치가 높은 옥수수를 수확하는 문제이다.
기존 bfs 에서는 queue를 사용하며, 상하좌우로 이동할 수 있는데, 이 문제에서는 지금까지 거쳐온 곳들의 상하좌우와 outline 들에서 가중치가 가장 높은 것을 골라주어야 하는 문제이다. 따라서 우선순위큐를 이용하여 bfs를 구현해주면 된다.

let fs = require("fs");
let input = fs
  .readFileSync("test/Test.txt", "utf8")
  .toString()
  .trim()
  .split("\n");
// "/dev/stdin"
// "test/Test.txt"

let [N, M] = input[0].split(" ").map(Number);
let corns = input.slice(1, N + 1).map((line) => line.split(" ").map(Number));
let K = Number(input[N + 1]);

const goX = [0, 0, 1, -1];
const goY = [1, -1, 0, 0];
let visited = Array.from({ length: N }, () => Array(M).fill(false));

class MaxHeap {}//maxheap 코드 생략
const queue = new MaxHeap();
let route = [];

for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (i === 0 || j === 0 || i === N - 1 || j === M - 1) {
      queue.push([corns[i][j], i, j]);
    }
  }
}

while (route.length < K) {
  let [_, curX, curY] = queue.pop();

  if (visited[curX][curY]) continue;
  route.push([curX + 1, curY + 1]);
  visited[curX][curY] = true;
  for (let i = 0; i < 4; i++) {
    let nextX = curX + goX[i];
    let nextY = curY + goY[i];
    if (
      nextX < 0 ||
      nextY < 0 ||
      nextX >= N ||
      nextY >= M ||
      visited[nextX][nextY]
    )
      continue;
    queue.push([corns[nextX][nextY], nextX, nextY]);
  }
}
for (const answer of route) {
  let [x, y] = answer;
  console.log(x, y);
}

한 번 동작을 익히고 외워두면 BFS, 다익스트라, 그리디 같은 문제에서
시간초과를 피하면서 훨씬 자유롭게 접근할 수 있다.

profile
가연
이전 포스트

백준 풀이 - 여행 가자(1976)

0개의 댓글