우선순위 큐 우선순위 큐란? 일반적인 큐(FIFO)와 달리 우선순위가 높은 데이터가 먼저 나가는 자료구조 구현방법 삽입 삭제 배열 O(1) O(N) 링크드리스트 O(1) O(N) 힙 O(logN) O(logN) ⏩️ 우선순위 큐의 삽입, 삭제가 필요할 때는 힙으로 구현하자. 최소 힙 이진트리 구조 모든 부모 노드는 자식 노드보다 값이 작다 최대 힙 이진트리 구조 모든 부모 노드는 자식 노드보다 값이 크다 비겁하지만... 힙이 JS에는 구현이 안되어 있어서 직접 구현해야 한다. 코딩테스트에서 파이썬 사용이 가능하다면 파이썬으로 푸는게 더 유리하다. 파이썬에서는요 import heapq # 힙 배열로 선언 heap = [] # 원소 push heapq.heappush(heap, 1) # 원소 pop cur ..
1. 배열로 스택 구현하기 그냥 JS 배열 메서드를 사용하면 스택을 활용할 수 있다. 2. 객체로 스택 구현하기 class Stack { #storage; constructor() { this.#storage = {}; this.length = 0; } push(item) { this.#storage[this.length++] = item; } pop() { if (!this.length) return; const item = this.#storage[--this.length]; delete this.#storage[this.length - 1]; return item; } } 3. 링크드리스트로 스택 구현하기 push(item) class Node { constructor(data) { this.dat..
BFS 문제를 풀다가 JS에는 큐가 구현되어 있지 않다는 것을 알게 되었다 ^__^ 코딩테스트에서 큐가 필요한 상황이 오면 어떻게 해야 할까? 1. 시간복잡도 O(N) 시간제한이 널널할 때는 Array.shift() 를 사용하자. 큐의 pop과 동일한 기능을 한다. 하지만 배열의 원소를 하나씩 당기기 때문에 시간복잡도가 O(N)이다. 2. 시간복잡도 O(1) pop할 원소의 인덱스를 변수를 만들어 저장하자. let front = 0; while (front < queue.length) { const [x, y, z] = queue[top]; front += 1; /* ... */ } 인덱스를 옮김으로써 가장 앞의 원소가 어떤 것인지 판별할 수 있게 되었다. 실제 원소가 삭제되지는 않지만 FIFO 흉내내..
