JavaScript를 위한 자료구조

 

학부 시절부터 지금까지, 자료구조와 알고리즘은 지루하기만 하고, 하기 싫은 숙제처럼 나를 괴롭혀왔다.. 하지만 현업에 들어오면서 "아 이 내용이 이런 식으로 활용되는구나" 몸소 깨달으면서 코드를 작성하는 일에 조금씩 재미를 느껴온 지 3년 차, 의구심이 들었다.

 

나는 과연 JavaScript의 기본적인 알고리즘 패턴을 제대로 이해하고 있는가?

 

실무에서 JavaScript를 다루면서 기본은 충실하게 이해하고 있는지 궁금해졌다. 그렇게 시작한 알고리즘 테스트 방법은 바로 "프로그래머스의 코딩 테스트 연습 문제" Level 순서대로 풀어보기! 기본적인 것도 익숙지 않은 문제 형태로 만나게 되면 머릿속이 백지처럼 바뀌는 마법...(그리고 몰려오는 현자 타임..)

 

따라서 이 글에서는 최근 알고리즘 공부를 하면서 자주 사용되는 쓸만한 간단한 자바스크립트 자료구조를 정리해보고자 한다.

 

Stack

가장 단순하게 쓰이는 스택부터 정리해 보자. 스택은 LIFO(Last In, First Out) 구조를 가진다. 자바스크립트에서는 스택 Object가 없으므로 직접 만들어야 하지만 Array.prototype 형태로 스택과 비슷한 메소드들이 구현되어 있어 쉽게 응용이 가능하다. 기본적인 push/pop과 같은 경우는 prototype에 정의된 메소드를 사용하고, peek은 적절하게 배열 접근으로 구현하면 좋다. (사실 Push/pop만으로 웬만한 알고리즘 문제를 푸는 데에는 지장이 없다.) 스택 같은 경우는 괄호 매칭이나 구간합을 구하는 데 응용하면 편리하다.

const stack = [];

stack.push(1);
stack.push(2);
stack.push(3);

stack[stack.length - 1]; // peek 3
stack.pop(); // 3
stack.pop(); // 2
stack.pop(); // 1

 

 

Queue

큐는 FIFO(First In, First Out) 구조를 가진다. 큐 또한 구현체가 없으므로, Array를 이용하여 간단하게 구현할 수 있다. 큐의 주요 메소드에는 euqueue와 dequeue가 있는데 enqueue는 큐에 삽입을 하는 메소드이고 dequeue는 큐에서 제일 처음으로 들어간 값을 빼는 메소드이다. 적절하게 prototype 메소드를 이용하면 된다. 큐는 BRS(Breadh-First Search)를 구현할 때 자주 이용하므로, 잘 기억해 두도록 하자.

 

const queue = [];

queue.push(1); // enqueue 1
queue.push(2); // enqueue 2
queue.push(3); // enqueue 3

queue.shift(); // dequeue 1
queue.shift(); // dequeue 2
queue.shift(); // dequeue 3

 

Linked List

C++ 에는 있지만 JavaScript에는 없는 포인터. 포인터가 없는 Linked List를 자바스크립트에서 객체를 참조하는 방식으로 구현할 수 있다. (오히려 더 간단하다!)

function Node(val) {
  this.val = val;
  this.next = null;
}

let head = new Node(0);
let node1 = new Node(1);
let node2 = new Node(2);

head.next = node1;
node1.next = node2;

물론, 이중 연결 리스트(Double Linked List)도 쉽게 구현이 가능하다. prev만 추가해서 양방향으로 참조하도록 구현하자.

function Node(val) {
  this.val = val;
  this.next = null;
  this.prev = null;
}

let head = new Node(0);
let node1 = new Node(1);
let node2 = new Node(2);

head.next = node1;
node1.next = node2;
node1.prev = head;
node2.prev = node1;

리스트 같은 경우엔 다른 자료구조를 표현하는데 많이 사용된다. 또 이중 연결 리스트는 LRU Cache 같은 것을 구현할 때 사용이 되므로 알아 두면 좋다.

 

 

Tree

트리는 보통 이진트리(Binary Tree)를 많이 구현하므로, 여기서는 이진트리를 어떻게 표현하는지 알아보도록 하자. 구현 방법은 크게 두 가지가 있는데, 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이다. 우선 배열을 이용하는 방법부터 알아보도록 하자. 배열은 단순하게  트리 번호대로 배열에 집어넣으면 끝이다. 한 가지 포인트는 index 0은 비워두는 것인데, root를 1부터 시작하게 해서, 왼쪽 자식 노드는 index * 2, 오른쪽 자식 노드는 index * 2 + 1로 참조하기 쉽게 약간의 트릭을 쓴다.

/*       5
 *     /   \
 *    3      8
 *   / \   /  \
 *  1   4  7   9
 */
const tree = [null, 5, 3, 8, 1, 4, 7, 9];

연결 리스트를 이용한 구현 방법은 위에서 구현한 Node 구현체와 거의 비슷하다. left, right를 이용하여 자식 노드를 참조하도록 구현한다.

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

let root = new Node(5);
let left = new Node(3);
let right = new Node(8);
root.left = left;
root.right = right;

한 가지 더. 트리 문제에서 불가분의 관계를 가지고 있는 게 순회(traversal)이다. 연결 리스트를 이용해 트리를 구현했을 경우, 다음과 같이 재귀 함수를 이용하면 쉽게 트리를 순회할 수 있다.

function traversal(node) {
  if (node === null) return;
  
  traversal(node.left);
  traversal(node.right);
}

트리의 순회 방법에는 루트 노드의 방문 순서에 따라 크게 세 가지로 나눌 수 있는데, preorder, inorder, postorder가 있다. 핵심이 루트 노드 방문 순서이므로, 어느 시점에서 접근하냐에 따라 트리 순회 방법을 표현할 수 있다. 참고로 이진 탐색 트리에서 inorder는 오름차순으로 정렬된다.

function traversal(node) {
  if (node === null) return;
  
  console.log('preorder', node.val);
  traversal(node.left);
  console.log('inorder', node.val);
  traversal(node.right);
  console.log('postorder', node.val);
}

 

 

Map

Map은 O(1)의 접근성을 가지는 매우 강력한 무기이다. ES5에서는 {}를 사용해서 구현하지만, ES6에는 Map 자료 구조가 추가되었으므로 취향에 따라서 골라 사용하도록 하자. Map은 시간 복잡도를 줄이는데 결정적인 역할을 하는 경우가 많은데, 많은 문제를 풀어보면서 어떻게 활용하는지 알아두면 굉장히 좋다.

const map = {};
map['p1'] = 1;
map['p2'] = 2;

map['p1']; // 1
map['p2']; // 2

// or 
const map = new Map();
map.set('p1', 1);
map.set('p2', 2);

map.get('p1'); // 1
map.get('p2'); // 2

 

 

Set

Set은 Map과 비슷하지만, 중복된 값을 허용하지 않는다. 따라서, 중복이라는 키워드가 떠오른다면 Set을 적절하게 사용하자. 구현은 ES6 Set을 사용하는 게 가장 편하다.

const set = new Set();
set.add(1);
set.add(2);

set.has(1); // true
set.has(2); // true
set.has(3); // false

 

 

Graph

그래프의 경우에는 그냥 문제에 따라서 위에서 언급한 자료구조를 적절히 이용해서 표현한다. 주로 인접 행렬이나 연결 리스트를 이용한다.

 

 

 

---

처음 프로그래머스의 Level 1 문제들을 풀어보면서 이렇게 간단한 문제를 푸는 것이 도움이 될까? 하는 안일한 생각이 들었다. 하지만 심플한 문제에서 간결한 코드를 생각하기는 생각보다 쉽지 않았다. 시간 복잡도도 생각해야 하고, 예외 처리를 하는 방식까지 생각하다 보면 3년이라는 시간이 반성될 만큼 효율적이고 성능 이슈에 적합한 코드를 작성하기는 쉽지 않다. 주니어 FE 개발자에서 좀 더 발전할 수 있는 계기가 되는 것 같다. 알고리즘 공부를 시작하는 이들에게 조금이나마 도움이 되었으면 좋겠다.