[Javascript로 정리하는 이코테] 3. 스택, 큐, 재귀

http://www.yes24.com/Product/Goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

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);

 

배열과 객체의 삽입/삭제 연산 속도 비교

• 원소를 십만 번, 이십만 번의 연산으로 테스트한 결과이다.
• 연결 리스트로 구현한 큐에서 삭제 연산 속도가 확실히 빠르며, 원소의 개수가 많아질수록 효과가 커짐을 알 수 있다.

좌) n=100,000 / 우) n=200,000

 

 

재귀

• 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

• https://velog.io/@longroadhome/자료구조-JS로-구현하는-.큐-Queue
• https://dwbyun.tistory.com/6