Algorithm/Javascript로 정리하는 이코테
[Javascript로 정리하는 이코테] 3. 스택, 큐, 재귀
반응형
http://www.yes24.com/Product/Goods/91433923
DFS/BFS 사전 지식을 알아보자.
스택과 큐
- 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.
- 대표적인 탐색 알고리즘으로 DFS/BFS가 있는데, 이를 이해하기 위해서는 스택과 큐에 대한 이해가 필요하다.
5-1. 스택 예제 - LIFO
- 삽입:
push()
- 삭제:
pop()
const stack = [];
stack.push(5);
stack.push(2);
stack.push(3);
stack.push(7);
stack.pop();
stack.push(1);
stack.push(4);
stack.pop();
console.log(stack); //[5, 2, 3, 1];
console.log(stack.reverse()); //[1, 3, 2, 5]
5-2. 큐 예제 - FIFO
- 삽입:
push()
- 삭제:
shift()
const queue = [];
queue.push(5);
queue.push(2);
queue.push(3);
queue.push(7);
queue.shift();
queue.push(1);
queue.push(4);
queue.shift();
console.log(queue); //[3, 7, 1, 4]
console.log(queue.reverse()); //[4, 1, 7, 3]
연결 리스트로 구현한 큐
- 자바스크립트에서는 큐 내장 메서드가 없기 때문에 위처럼 배열과
push()
,shift()
로 큐를 흉내 낼 수 있다. - 하지만 첫 번째 원소를 제거하는
shift()
의 경우,O(n)
의 시간복잡도를 가지기 때문에 많은 데이터를 빠르게 관리하기 위해서는 연결 리스트(객체)로 큐를 구현해 사용하는 것이 좋다. - 이렇게 객체를 사용하면 원소의 추가, 삭제 연산을
O(1)
시간에 해결할 수 있다.
LinkedList Queue
class Node {
constructor(data){
this.data = data;
this.next = null;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
isEmpty() {
return this.size === 0;
}
enqueue(data) {
const newNode = new Node(data);
if(this.isEmpty()) this.front = newNode;
else this.rear.next = newNode;
this.rear = newNode;
this.size++;
}
dequeue() {
if(this.isEmpty()) return;
const data = this.front.data;
this.front = this.front.next;
this.size--;
return data;
}
}
const q = new Queue();
q.enqueue(5);
q.enqueue(2);
q.enqueue(3);
q.enqueue(7);
q.dequeue();
q.enqueue(1);
q.enqueue(4);
q.dequeue();
console.log(q);
배열과 객체의 삽입/삭제 연산 속도 비교
- 원소를 십만 번, 이십만 번의 연산으로 테스트한 결과이다.
- 연결 리스트로 구현한 큐에서 삭제 연산 속도가 확실히 빠르며, 원소의 개수가 많아질수록 효과가 커짐을 알 수 있다.
재귀
- DFS와 BFS를 구현하려면 재귀 함수에 대한 이해도 필요하다.
- 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다.
5-3. 재귀 함수 예제
무한 루프에 빠진다.
const recursive = () => {
console.log('재귀 함수를 호출합니다.')
recursive();
}
recursive();
5-4. 재귀 함수 종료 예제
재귀 함수는 반드시 종료 조건을 명시해야 한다.
const recursive = (i) => {
if (i === 10) return;
console.log(`${i}번째 재귀 함수에서 ${i + 1}번째 재귀 함수를 호출합니다.`)
recursive(i + 1);
console.log(`${i}번째 재귀 함수를 종료합니다.`)
}
recursive(1);
5-5. 2가지 방식으로 구현한 팩토리얼 예제
재귀 함수는 점화식을 그대로 소스코드로 옮긴 것으로, 반복문보다 코드가 간결하다.
const factorialIterative = (n) => {
let result = 1;
for(let i = 2; i <= n; i++){
result *= i;
}
return result;
}
const factorialRecursive = (n) => {
if(n < 2) return 1;
return n * factorialRecursive(n-1);
}
console.log(factorialIterative(5));
console.log(factorialRecursive(5));
Reference
반응형
'Algorithm > Javascript로 정리하는 이코테' 카테고리의 다른 글
[Javascript로 정리하는 이코테] 5. 정렬 (0) | 2023.03.10 |
---|---|
[Javascript로 정리하는 이코테] 4. DFS/BFS (0) | 2023.03.09 |
[Javascript로 정리하는 이코테] 2. 구현 (0) | 2023.03.07 |
[Javascript로 정리하는 이코테] 1. 그리디 (Greedy) (0) | 2023.03.06 |
[Javascript로 정리하는 이코테] 0. JavaScript 입력받기 & 풀이 로직 분리 (0) | 2023.03.05 |