programmers-예상 대진표를 풀다가 queue를 활용하지 않고 일반 배열을 사용하여 문제풀이에서 시간초과가 났다. 해결책은 일반 array가 아닌 queue를 활용하여 앞에서 요소를 제거(python: popleft(); javascript: shift())할 때의 시간 복잡도 O(1)를 활용하는 것이다. 따라서 배열의 앞의 요소를 빼거나 집어넣을 때 어떻게 동작하는 지 확인할 필요가 있다.
python은 from collections import deque를 활용하면 되지만 javascript는 queue를 제공해주는 library가 없어 직접 구현해야 한다. 따라서 직접 구현도 할 겸 정리도 할 겸 블로그로 정리해 본다.
queue를 알아보기 전에 왜 일반 배열에서 앞 요소를 제거할 때 O(n)이 나오는지 알아보자.
🍀 O(n) when shift
아래와 같이 길이가 6인 배열의 array = [1, 2, 3, 4, 5, 6]이 있다고 가정하자.
pop()과 push()와 같은 경우는 뒤에서 넣다 빼는 것으로 index가 10이던 1억이던 상관없이 index + 1에 값을 집어넣어주게 되므로 시간 복잡도는 상수값을 가지게 된다.
하지만, shift()와 unshift()는 index가 0인 곳에서 값을 제거하거나 넣게 되므로 각각의 index는 한 칸 씩 밀리게되어 O(n - 1) -> O(n)인 시간 복잡도를 가지게 된다. pop과 push와 다르게 속도가 엄청 차이남을 뜻한다. 이 글이 이해가 안 된다면 아래그림🔽을 참고하자
위와 같이 인덱스가
한 칸씩 앞으로(index - 1)땡겨지게 된다.
📒 따라서, 앞에서 넣다 뺐다 하는 연산이 많을 경우에는 일반 배열을 사용하게 되면 속도적인 측면에서 낮은 효율이 나오게 된다. 그러므로 shift 또는 unshift시 연산 횟수는 배열의 길이인 n과 비례하므로 시간 복잡도는 O(N)으로 나타낼 수가 있다.
🤔 그러면 shift와 unshift를 pop과 push와 같은 시간 복잡도를 가지게 할 수 있을까???
Linked List(연결 리스트)를 이용하면 shift와 unshift가 O(1)을 가질 수 있게 할 수 있다.
🍀 Linked List
Linked List는 Array와 다르게 요소와 요소 간의 연결(link, pointer)을 이용해서 리스트를 구현한 것이다. node(value와 다른 노드를 가리키는 pointer가 있음)가 다음 node를 가리키는 구조를 하고 있으며 첫 번째 노드를 가리키는 pointer와 마지막 노드를 가리키는 pointer가 있다.
다음 그림은 linked list를 이용하여 queue를 구성한 그림이다.
말만 queue이지 사실상 linked list라고 봐도 무관하다. queue라고 한 것은 queue는 FIFO이므로 enqueue와 dequeue만을 구현하기 때문에 이 블로그에서 queue라고 표현했다.
용어
- first: pointer로서
맨 앞 node를 가리킨다. - last: pointer로서
맨 뒤의 node를 가리킨다. - node:
요소(값)와 다음 노드를 가리키는 pointer인next로 이루어져 있으며vertex(정점)이라고도 한다. - enqueue: 일반 배열에서 unshift로 queue에서는 맨 앞에서 요소를 추가하는 것을
enqueue라고 한다. - dequeue: 일반 배열에서 shift로 queue에서는 맨 앞에서 요소를 제거하는 것을
dequeue라고 한다.
장점(props)
요소의 추가 삭제가 빠르다.- 필요할 때
메모리를 동적으로 할당한다.
단점(cops)
- 일반 배열보다
많은 메모리를 차지한다. - 특정한 요소에 랜덤하게 접근할 수 없다. 즉, 일반 배열은 특정한 요소에 빠르게 접근할 수 있지만, linked list는
처음 node부터 순차적으로 찾아야하므로 시간이 오래 걸린다. - 역순으로 값을 탐색할 수 없다. -> 이것은 Doubly Linked List로 해결할 수 있다.
시간 복잡도(time complexity)
- Access: O(n)
- Search: O(n)
- insertion: O(1)
- Deletion: O(1)
🚀 구현
Node 구현
node는 value와 next라는 pointer만 설정해주면 되어 간단하다.
node code
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}Queue 구현
👉🏻 enqueue(unshift) pseudo code
- value에 대한 node를 생성한다.
- queue에 node가 없다면(first === last === null or !first or !last) 생성된 노드를 first pointer와 last pointer를 newNode에 가리키게 한다.
- queue에 노드가 존재한다면 생성된 노드를 last pointer만 가리키게 한다.
- queue의 size를 1만큼 증가시킨다.
👉🏻 dequeue(shift) pseudo code
- queue가 비어있다면(first === last === null or !first or !last) null을 return
- queue에 node가 1개만 존재(first === last)한다면 node의 value를 return하고 first pointer와 last pointer를 null로 설정
- queue에 노드가 2개 이상 있다면 first pointer를 다음 node를 가리키게 한다.
- queue의 size를 1만큼 감소시킨다.
queue code
class Queue {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
enqueue(value) {
const newNode = new Node(value);
if (!this.first) {
this.first = this.last = newNode;
} else {
this.last.next = newNode;
this.last = newNode;
}
this.size++;
}
dequeue() {
const tempNode = this.first;
if (!this.first) return null;
if (this.first === this.last) this.last = null;
this.first = this.first.next;
this.size--;
return tempNode.value;
}
}동작 검증
const q = new Queue();
console.log(q);
q.enqueue(1); // queue에 아무것도 없을 때 node 추가
console.log(q);
q.enqueue(2); // queue에 node가 존재할 때 node추가
console.log(q);
console.log("dequeued value ->", q.dequeue()); // queue에 node가 2개 이상일 때 제거
console.log(q);
console.log("dequeued value ->", q.dequeue()); // queue에 node가 1개일 때 제거
console.log(q);
console.log("dequeued value ->", q.dequeue()); // queue에 아무 node가 없을 때 제거
console.log(q);출력
잘 동작한다!!!😄
효율성 검증
그냥 잘 동작하는지 검증만 하고 끝내려고 했지만 일반 배열과 얼마나 차이가 나나 궁금해서 효율성 검증을 스스로 해 보기로 했다. 배열의 길이는 1억 십만으로 테스트했다.(1억은 메모리초과 오류가 난다.... -> 오류 해결)
test efficiency code
function fillValueQueue(queue, value, range) {
for (let i = 0; i < LENGTH; i++) {
queue.enqueue(value);
}
}
const LENGTH = 1000000;
const normalArray = Array(LENGTH).fill(0); // initialize normal array
const queue = new Queue();
fillValueQueue(queue, 0, LENGTH); // initialize queue
// get takes time to shift all elements of normal array
console.time("shift normal array");
while (normalArray.length > 0) {
normalArray.shift();
}
console.timeEnd("shift normal array");
// get takes time to deque all elements of queue
console.time("dequeue queue");
while (queue.size > 0) {
queue.dequeue();
}
console.timeEnd("dequeue queue");결과
십만을 가지고 테스트 했는데 결과는 어마무시하게 차이가 난다...
일반 배열에서 모든 요소를 shift하는 것은 O()이고 queue에서는 O(1)이다.
효율성 검증을 처음 해봤는데 이렇게 하는게 맞나 싶지만 결과가 말해주지 않나 싶다.😴
🚗 마치며
예전에 자료구조를 공부하면서 python으로 linked list를 구현한 적이 있지만 바로 구현하려하니 시간이 좀 걸렸다. 하지만, 한 번 공부했던 내용이라 그런지 큰 어려움 없이 개념을 재확립할 수 있었다. 그리고 속도가 얼마나 차이가 나나 궁금해서 코드를 짜봐서 했는데 저렇게 차이가 많이 날 줄은 몰랐으며 자료구조의 중요성을 일캐워주는 시간이었다. 따라서, 적절한 상황에 맞게 자료구조를 쓰면 효율성을 많이 증가시킬 수 있을 것 같다.
👉🏻 참고
