자료구조

자료란

데이터라고 하는 편이 더 익숙할지도 모르겠다. 측정된 값을 일컫는 용어이다. 수치화하여 표현할 수 있는 모든 것들을 데이터라고 할 수 있다.

자료구조

이러한 자료들을 모아 어떤식으로 저장하고 관리할지에 대한 다양한 구조들을 총칭하여 자료구조라 한다. 다양한 방식의 자료구조로 구성된 데이터들을 어떻게 해야 더 빠르고 효율적으로 검색하거나 정렬할 수 있는지에 대한 알고리즘이 필연적으로 따라오게 된다.

자주 사용하는 자료구조

어차피 이면에는 서버가 존재하고 다양한 기법을 적용한 서버들이 혼재하기 때문에 웹 프로그래밍을 위한 자료구조라고 명확히 구분할 수는 없다.

그러나 이 문서에서는 웹 페이지를 기준으로 쉽게 경험해보고 공부해볼 수 있는 자료구조로 큐, 스택, 트리 세가지를 소개한다. DBMS를 직접 만들어보고 싶은 사람이 아니라면 단순히 웹 프로그래밍을 하면서 이 틀을 벗어나는 자료구조를 접할 일이 그리 흔치 않을 것이다.

큐와 스택

큐와 스택은 가장 기본적인 자료구조로 데이터를 꺼내는 방식에 따라 구분된다. 둘다 동일하게 저장한 데이터는 순서대로 쌓인다. 그러나 큐는 데이터를 꺼낼때 저장한 순서대로 꺼내는 반면 스택은 역순으로 꺼낸다. FIFO, LIFO, 후입선출, 선입선출 등 다양한 이름으로 불리우기도 하지만 큐와 스택이라는 이름으로 정확하게 기억하는 것이 좋다.

흔하게 접할 수 있는 용례로 큐는 키보드 입력을 생각해볼 수 있다. 컴퓨터가 렉이 걸렸다고 짜증을 낸 경험이 한 두번쯤 있을 것이다. 이때 키보드를 아무리 입력해도 화면에 출력되지 않고 있다가 컴퓨터의 처리가 원할해지면 그동안 입력했던 키보드 입력이 화면에 한꺼번에 출력된다. 가만히 생각해보면 입력한 순서대로 출력되었다는 것을 알 수 있는데 이는 키보드 입력이 순서대로 큐에 저장되어 있다가 순서대로 출력되었다는 것이다.

스택의 경우는 브라우저의 뒤로가기를 들 수 있다. 브라우저를 통해 여러 페이지를 이동하다가 뒤로가기를 누르면 방문했던 역순으로 페이지를 되돌아 갈 수 있다. 방문한 페이지 URL들이 스택에 저장되어 있고 뒤로가기를 실행할 때마다 가장 마지막 데이터를 꺼낸 것이다.

/**
 * Queue
 */
const queue = [];
queue.push(1);
queue.push(2);
queue.push(3);

console.info(queue.shift()); // 1
console.info(queue.shift()); // 2
console.info(queue.shift()); // 3

/**
 * Stack
 */
const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);

console.info(stack.pop()); // 3
console.info(stack.pop()); // 2
console.info(stack.pop()); // 1

큐와 스택은 위 처럼 JavaScript의 배열을 활용하여 아주 간단하게 구현해볼 수 있다. 물론, 이것은 아주 간단하게 구현한 것이고 객체로도 구현할 수도 있기 때문에 자료구조가 어떻게 동작하는지를 이해하고 활용할 수 있는 것이 더 중요하다.

트리

스택과 큐처럼 입구와 출구가 하나인 자료구조를 선형 자료구조라고 한다. 트리의 경우는 비선형 자료구조로 특별히 입구와 출구가 정해져 있지 않다. 비교적 다루기 쉬운 선형 자료구조에 비해 복잡하고 성능이 떨어지지만 다양한 자료를 표현할 수 있어서 많이 사용된다. 트리는 쉽게 조직도를 생각해보면 된다.

/**
 * Linear Tree
 */
const linearTree = [
  { id: 1, name: 'root', parent: null },
  { id: 2, name: 'child1', parent: 1 },
  { id: 3, name: 'child2', parent: 1 },
  { id: 4, name: 'child3', parent: 2 },
  { id: 5, name: 'child4', parent: 2 },
  { id: 6, name: 'child5', parent: 3 },
  { id: 7, name: 'child6', parent: 3 },
];

/**
 * Nested Object Tree
 */
const nestedTree = [
    {
    id: 1,
    name: 'root',
    children: [
      {
        id: 2,
        name: 'child1',
        children: [
          { id: 4, name: 'child3', children: [] },
          { id: 5, name: 'child4', children: [] },
        ],
      },
      {
        id: 3,
        name: 'child2',
        children: [
          { id: 6, name: 'child5', children: [] },
          { id: 7, name: 'child6', children: [] },
        ],
      },
    ],
  }
];

트리를 자료로 표현할 수 있는 방법은 주로 두가지를 사용하는데 1차원 배열로 표현하거나 중첩된 객체로 표현한다. 이 두가지 방법은 각각 장단점이 있기 때문에 상황에 맞게 선택하여 사용하는 것이 좋다.

배열로 표현된 트리의 경우 검색이 용이하고 메모리 사용량이 적다. 중첩된 객체로 표현된 경우 검색을 구현하려면 필연적으로 재귀호출 때문에 복잡해지고 메모리 사용량도 배열에 비해서 많다. 그러나 중첩된 객체로 표현하는 경우 가독성이 높아 트리 전체구조를 파악하기 좋으며 노드의 부분구조를 추출하기 쉽다는 장점이 있다.

알아두어야 할 것

이 문서에서 소개하는 세가지 형태는 아주 기초적인 자료구조이다. 트리만 하더라도 오직 두개의 자식만 가질 수 있는 이진트리, 왼쪽은 작은 값, 오른쪽은 큰 값으로 정렬된 이진탐색트리, 문자열 검색에 최적화된 트라이 등 다양하게 응용하기도 한다.

자료구조를 검색할 때에는 모든 노드를 정해진 순서대로 방문하며 찾아야 하는데 순회 한다고 표현한다. 순회하는 방법에 따라 여러가지 알고리즘이 있으며 비선형, 선형에 대해서 여러가지 방법론들이 존재한다. 또한 이러한 순회 알고리즘은 단순히 순회의 방법에만 목표를 두지 않고 자료가 정렬된 방식과 결합되어 더 높은 성능을 내도록 설계되기도 한다.

따라서, 자료구조를 공부할 때에는 순회와 정렬에 대해서도 함께 공부해야한다. 피벗정렬, 버블정렬, 힙정렬, 퀵정렬, 삽입정렬, 선택정렬 등 다양한 정렬 알고리즘이 존재하며 각각의 장단점이 있다.