자바스크립트로 알고리즘 풀기 외길 인생을 즐기고 있습니다 .. ✨
자바스크립트로 알고리즘을 풀면 가끔 너무 외로운 순간들이 있습니ㄷ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)이 될 수 있는 이유는 부모만 비교해서 올라가면 되기 때문이다.
1 ) Insert 함수 구현하기 ( * MaxHeap 예제)
- 만약 20이라는 숫자를 추가하고 싶다면, 일단 마지막에 위치시킨다.
- 부모와 비교를 한다. (반복)
- 만약, 현재 부모가 자신보다 같거나 크다면 반복문 종료
- 현재 내가 비교하는 노드(20)이 root 노드에 있다면 반복문 종료
2) 힙에서 최상단의 값을 가져오고, 재정렬 (*MaxHeap 예제)
- Max 값을 없애준다. (만약에 최솟값 재갱신이 필요없다면 이걸로 마무리)
- 마지막 노드에 있는 값을 root 노드로 보내주고, 마지막 노드를 삭제한다.
- 자식과 비교를 해준다. (반복문)
- 자식 노드가 아예 없는 경우
- 왼쪽 자식만 있는 경우
- 왼쪽, 오른쪽 자식이 모두 있는 경우 (현재에서 더 큰 값을 선정해주어 교체해준다.)
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]);
};
}
'STUDY > Algorithms' 카테고리의 다른 글
[JS] 징검다리 건너기 (0) | 2023.04.25 |
---|---|
[JS] 순위 검색 (0) | 2023.04.20 |
[JS] 교점에 별 만들기 (0) | 2023.04.07 |
[JS | 알고리즘] BFS 와 0-1 BFS (0) | 2023.02.05 |