JS/알고리즘 자료구조 기초

 

 

• 학습 내용

저번 시간에 학습했던 재귀에 이어 자료구조의 아주 기본적이고 기초적인 자료구조의 정의와 Stack, Queue 그리고 그래프와 트리에 대해서 간단히 학습했다. 물론 앞으로 해야 할 알고리즘 학습에 아주 일부분인 내용이다. 그러나 이 내용들을 잘 알아둬야 앞으로 꾸준히 진행해야 할 학습에 기반이 될 것이라 생각한다. 

• 자료구조

자료구조란 여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의한 것이다. 문자, 숫자, 그림, 영상 등 실생활을 구성하고 있는 모든 값을 우리는 데이터라고 한다. 그런데 이 데이터란 분석과 정리의 과정을 거쳐야 활용하는 데 있어 의미와 가치가 생긴다. 특히 이것은 필요와 특성에 따라 잘 분석하고 정리할수록 더욱 활용가치가 올라간다고 할 수 있다. 이로 인해 많은 개발자들은 데이터를 더욱 효율적으로 다루기 위해 많은 방법들을 연구했고, 연구된 이 방법들을 자료구조라고 부른다. 그래서 자료구조는 특정한 상황에 놓인 문제를 해결하는 것에 특화되어 있다. 그렇기에 많은 자료구조를 학습한다면 필요한 상황에 알맞은 자료구조를 적용하여 문제를 효율적이고 쉽게 해결할 수 있게 된다.

 자료구조를 학습하는 방법을 간단히 정리하자면 이렇다. 

1. 각 자료구조가 가진 특징을 학습한다.
2. 각 자료구조를 사용하기 적합한 상황을 이해한다.
3. 다른 자료구조와의 차이점을 이해하기 위해 자료구조 내부를 직접 구현해본다.
4. 자료구조를 구현하며 자료구조의 동작원리를 이해한다.

기본적으로 자료구조를 활용할 때는 class 키워드를 사용하여 자료구조의 데이터 타입을 직접 정의하는 것이 좋다. 그러나 이런 접근은 알고리즘 문제를 풀 때는 적합하지 않을 수 있다. 왜냐하면 다소 시간이 많이 소요되기 때문이다. 이때 JavaScript에서 제공하는 다양한 데이터 타입을 이용하면 해결하는데 도움이 된다.

 

• Stack

stack은 쌓다, 쌓이다, 포개지다는 뜻을 가진 단어이다. 자료구조에서 stack이란 말 그대로 데이터를 순차적으로 쌓는 것을 의미한다. stack은 가장 먼저 들어간 데이터는 가장 마지막(FILO First In Last Out)에 가장 마지막에 들어간 데이터는 가장 먼저(LIFO Last In First Out) 나올 수 있는 특징을 가지는데, 대표적으로 브라우저의 뒤로 가기와 앞으로 가기 버튼의 기능이 이러하다. 구체적으로 살펴보면 새로운 페이지에 접속할 때 현재 페이지는 Prev Stack이라는 공간에 저장된다. 그리고 뒤로 가기 버튼을 누르면 현재 페이지를 Next Stack에 저장하고 Prev Stack에는 가장 나중에 보관했던 페이지를 현재 페이지로 렌더링 한다. 앞으로 가기 버튼 역시 마찬가지로 현재 페이지를 Prev Stack에 저장하고 Next Stack에 가장 마지막에 저장했던 페이지를 렌더링 한다. class로 기능을 구현하면 이렇다.

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }
  
  size() {
    return this.top
  }
  
  push(element) {
    this.storage[this.top] = element
    this.top += 1
  }
  
  pop() {
    if (this.top === 0) {
      return;
    }
    
    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    this.top -= 1;
    
    return result;
  }
}

JavaScript의 데이터 타입인 배열을 이용해서도 구현할 수 있다. 배열의 내장 메소드를 사용하면 간단하다.

const stack = [];

stack.push(1); // [1]
stack.push(2); // [1, 2]

stack.pop(); // [1]
stack.pop(); // []

 

• Queue

queue는 줄을 서서 기다리다, 대기 행렬이라는 뜻을 가진 단어이다. 위에서 살핀 stack과는 반대로 먼저 들어간 데이터가 먼저 나오고(FIFO First in First Out) 마지막에 들어간 데이터는 마지막에 나오는(LILO Last In Last Out) 특징을 가진다. 주로 데이터가 입력된 순서대로 처리할 때 사용한다. 예로 프린터의 데이터를 처리하는 것이 이러한데, 프린터가 데이터를 처리하는 과정에서 출력 버튼을 누르면 해당 데이터가 먼저 queue에 들어간다. 그리고 처리된 데이터들은 들어온 순서대로 프린터가 인쇄한다. 여기서 데이터의 크기에 따라 데이터끼리 속도나 시간의 차이가 발생할 수 있는데, queue는 이것을 극복하기 위한 임시 기억 장치로 사용되는 것이다. 이것을 버퍼(buffer)라고 한다. 프린터에서 여러 작업이 비슷하게 들어왔을 때 인쇄를 위한 데이터 작업이 빨리 끝났다고 해도 queue를 통해 들어온 순서대로 처리가 되는 것이다. queue 역시 class로 구현하면 이렇다.

class Queue {
  constructor() {
    this.storage = {}
    this.front = 0;
    this.rear = 0;
  }
  
  size() {
    return this.rear - this.front;
  }
  
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  
  dequeue() {
    if (this.front === this.rear) {
      return;
    }
    
    const result = this.storage[this.front];
    delete this.storage[this.front]
    this.front += 1;
    
    return result;
  }
}

queue 역시 배열로 구현할 수 있다.

const queue = [];

queue.push(1); // [1]
queue.push(2); // [1, 2]

queue.shift(); // [2]
queue.shift(); // []

 

Graph

컴퓨터 공학에서 말하는 그래프는 우리가 아는 수학 그래프와 다르다. 거미줄처럼 여러 개의 점들이 선으로 이어져 있는 복잡한 네티워크 망과 같은 모습을 가지고 있는 자료구조 그래프이다.

이것은 여러 개의 점들이 복잡하게 연결된 관계를 표현한 자료구조인 것이다. 여기에서 하나의 점은 정점(vertex)라고 부르고 하나의 선을 간선(edge)라고 부른다. 주로 포털 사이트의 검색엔진이나 SNS의 친구 찾기 기능, 내비게이션 등에 많이 사용된다. 예를 들어 서울과 대전 그리고 부산의 길을 그래프로 구현하고자 하면 이렇게 할 수 있다.

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejean: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}

이렇게 하면 정점 간의 간선이 존재하는지 그리고 그 간선이 단방향인지 양방향인지 나타낼 수 있다. 물론 여기서는 인접 여부만 나타내고 얼마나 멀고 가까운지에 대한 정보는 표시하지 않았다. 그래서 이것은 비 가중치 그래프라고 할 수 있다. 여기에 거리등을 포함하면 가중치 그래프가 되는 것이다.

 

• 그래프의 표현 방식

그래프의 두 정점을 이어 주는 간선이 있으면 두 정점은 인접하다고 말한다. 이것을 행렬을 사용하여 그래프의 상태를 표현하기도 하는데, 이것을 인접 행렬이라고 한다. A라는 정점과 B라는 정점이 이어져 있으면 1 아니면 0으로 표시하여 행렬을 구성한다. 물론 가중치 그래프의 경우 해당 수치를 기입할 수도 있다.

인접 행렬의 경우 두 정점 사이에 관계가 있는지 없는지를 파악하는 데에 유리하다. 그래서 주로 가장 빠른 경로를 찾을 때 주로 사용한다.

class GraphWithAdjacencyMatrix {
  constructor() {
    this.matrix = [];
  }
  
  addVertex() {
    const currentLength = this.matrix.length;
    for (let i = 0; i < currentLength; i++) {
      this.matrix[i].push(0)
    }
    this.matrix.push(new Array(currentLength + 1).fill(0)
  }
  
  constains(vertex) {
    return !!this.matrix[vertex];
  
  addEdge(from, to) {
    const currentLength = this.matrix.length;
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    this.matrix[from][to] = 1;
  }
  
  hasEdge(from, to) {
    if (this.matrix[from][to] === 1) {
      return true
    } else {
      return false
    }
  }
  
  removeEdge(from, to) {
    const currentLength = this.matrix.length;
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.")
      return;
    }
    if (from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
      return;
    }
    this.matrix[from][to] = 0;
  }
}

 

• 인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접한 지를 리스트의 형태로 표현한 것이다. 정점마다 하나의 리스트를 가지고, 인접한 정점들을 담고 있다. 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 주로 사용한다. 인접 행렬의 경우 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지하기 때문이다.

class GraphWithAdjacencyList {
  constructor() {
    this.vertices = {};
  }
  
  addVertex(vertex) {
    if (Array.isArray(this.vertices[vertex])) {
      return;
    }
    this.vertices[vertex] = new Array;
  }
  
  contains(vertex) {
    return !!this.vertices[vertex];
  }
  
  addEdge(fromVertex, toVertex) {
    if(!this.contains(fromVertex) || !this.contains(toVertex) {
      return;
    }
    if (!this.hasEdge(fromVertex, toVertex)) {
      this.vertices[fromVertex].push(toVertex)
    }
    if (!this.hasEdge(toVertex, fromVertex)) {
      this.vertices[toVertex].push(fromVertex)
    }
  }
  
  hasEdge(fromVertex, toVertex) {
    if (!this.contains(fromVertex)) {
      return fals;
    }
    return !!this.vertices[fromVertex].includes(toVertex);
  }
  
  removeEdge(fromVertex, toVertex) {
    if (!this.contains(fromVertex) || !this.contains(toVertex)) {
      return;
    }
    if (this.hasEdge(fromVertex, toVertex)) {
      const index = thsi.vertices[fromVertex].indexOf(toVertex);
      this.vertices[fromVertex].splice(index, 1);
    }
    if (this.hasEdge(toVertex, fromVertex)) {
      const index = this.vertices[toVertex].indexOf(fromVertex);
      this.vertices[toVertex].splice(index, 1);
    }
  }
  
  removeVertex(vertex) {
    if (this.contains(vertex) {
      delete this.vertices[vertex]
    }
    for (let prop in this.vertices) {
      for (let el of this.vertices[prop]) {
        if (el === vertex) {
          const index = this.vertices[prop].indexOf(el);
          this.vertices[prop].splice(index, 1);
        }
      }
    }
  }
}

 

• Tree

자료구조의 Tree는 나무 형태를 가졌다. 면밀히 말하자면 나무를 거꾸로 뒤집어 놓은 형태라고 할 수 있다. 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조인 것이다. 즉, 데이터를 순차적으로 나열시킨 선형 구조가 아니라 하나의 데이터 뒤에 여러 데이터가 존재할 수 있는 비선형 구조이다. 계층적으로 표현되기에 사이클 역시 없다. 트리는 루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결된다. 여기서 각 데이터들을 노드(Node)라고 부르고, 두 개의 노드가 상하 계층으로 연결된 것을 부모/자식 관계를 가졌다고 말한다. 그리고 더 이상 자식이 존재하지 않는 노드를 리프 노드(leaf Node)라고 부른다.

또한 트리는 깊이와 높이, 레벨을 지정한다. 깊이(depth)는 루트로부터 하위 계층의 특정 노드까지를 의미한다. 예를 들어 위 트리의 루트의 경우 depth는 0이고 B와 C 노드는 1이 D, E, F, G는 2가 된다. 레벨(Level)은 같은 깊이를 가진 노드를 묶은 것이다. depth가 0이면 level은 1 마찬가지로 1이면 2, 2이면 3이 된다. 마지막으로 높이(Height)는 리프 노드로부터 루트까지를 의미한다. 리프 노드와 직간접적으로 연결된 노드의 높이를 표현하며, 부모 노드는 자식 노드의 가장 높은 height 값에 +1이 된다. 리프 노드의 높이는 0이다. 

 트리 구조 내부에 또 다른 트리 구조를 갖는 작은 트리가 존재할 수도 있는데, 이것을 서브 트리라고 부른다. 트리는 대표적으로 컴퓨터 디렉토리 구조에서 많이 볼 수 있는데, 폴더에 들어가는 경우가 트리에서 하위 노드로 내려가는 것과 같다고 볼 수 있다. 

class Tree {
  constructor(value) {
    this.value = value;
    this.children = [];
  }
  
  insertNode(value) {
    const childNode = new Tree(value);
    this.children.push(childNode);
  }
  
  constains(value) {
    if (this.value === value) {
      return true;
    } else {
      for (let el of this.children) {
        if (el.contains(value)) {
          return true;
        }
      }
    }
    return false;
  }
}

 

• 이진 탐색 트리 (Binary Serach Tree)

많은 개발자들이 효율적인 탐색을 위해 새로운 트리의 모습을 만들기 위해 노력했다. 그래서 많은 종류의 트리가 생겨났고, 그중에서도 가장 간단하고 많이 사용되는 트리가 이진트리(binary tree)와 이진 탐색 트리(binary serach tree)이다. 이진트리의 경우 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 그래서 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나뉠 수 있다. 또 이진트리는 자료의 삽입, 삭제 방법에 따라 정 이진트리 (Full binary tree), 완전 이진트리 (Complete binary tree), 포화 이진트리 (Perfect binary tree)로 분류할 수 있다. 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.

	정 이진 트리	각 노드가 0개 혹은 2개의 자식 노드를 갖는다.
	포화 이진 트리	정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고 모든 레벨이 가득 채워져 있는 트리이다.
	완전 이진 트리	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽은 채워져야 한다.

class BinarySerchTree {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  
  insert(value) {
    if (value < this.value) {
      if (this.left === null) {
        this.left = new BinarySearchTree(value);
      } else {
        this.left.insert(value)
      }
    } else if (value > this.value) {
      if (this.right === null) {
        this.right = new BinartSearchTree(value);
      } else {
        this.right.insert(value)
      }
    } else {
      return;
    }
  }
  
  contains(value) {
    if (this.value === value) {
      if (this.left === null) {
        return false;
      } else {
        if (this.left.contains(value)) {
          return true
        }
      }
    }
    if (value > this.value) {
      if (this.right === null) {
        return false;
      } else {
        if (this.right.contains(value)) {
          return true;
        }
      }
    }
    return false;
  }
  
  // 전위 순회
  // 가장 먼저 루트를 방문한 후 루트에서 시작해 왼쪽의 노드들을 순차적으로 둘러본 후 왼쪽이 끝나면 오른 쪽 노드를 탐색하는 방법
  preorder(callback) {
    callback(this.value);
    if (this.left) {
      this.left.preorder(callback)
    };
    if (this.right) {
      this.right.preorder(callback)
    };
  }
  
  // 중위 순회
  // 루트를 가운데 두고 제일 왼쪽 끝에 있는 노드부터 순회하여 루트를 기준으로 왼족에 있는 노드의 순회가 끝나면 루트를 거쳐 오쪽에 있는 노드로 인동하여 탐색하는 방법
  inorder(callback) {
    if (this.left) {
      this.left.inorder(callback)
    }
    callback(this.value);
    if (this.right) {
      this.right.inorder(callback)
    }
  }
  
  // 후위 순회
  // 루트를 가장 마지막으로 하여 제일 왼쪽 끝에 있는 노드부터 순회하여 오른쪽으로 이동해 순회한 뒤 마지막에 루트를 탐색하는 방법
  postorder(callback) {
    if (this.left) {
      this.left.postorder(callback)
    }
    if (this.right) {
      this.right.postorder(callback)
    }
    callback(this.value);
  }
}

 

• BFS와 DFS

그래프 탐색의 목적은 하나의 정점에서 시작하여 원하는 정점을 찾아 필요한 데이터를 찾는 것이다. 그러나 그래프의 데이터는 배열처럼 정렬되어 있지 않기 때문에 원하는 자료를 찾으려면 하나씩 모두 방문해야만 한다. 그렇게 그래프를 탐색하는 대표적인 방법 두 가지가 바로 BFS와 DFS이다. 비록 모든 자료를 하나씩 확인해본다는 점은 같지만 탐색하는 순서에는 차이가 있다.

1) BFS(Breadth-First Search)

BFS는 가까운 정점부터 탐색하는 방법이다. 더 탐색할 정점이 없을 때 그다음 떨어져 있는 정점을 순서대로 방문하는 것이다. 이것을 너비 우선 탐색이라고 한다. BFS를 적용하여 문제를 해결할 때는 보통 queue를 이용해서 해결하는 경우가 많다.

function bfs(adjList, vertex, visited) {
  //bfs는 가장 가까운 정점부터 탐색하기 때문에 queue를 사용함
  const queue = [vertex];
  //해당 정점을 방문했음을 표시함
  visited[vertex] = true;
  
  //queue의 길이가 0일 때까지 순환함
  while (queue.length > 0) {
    //queue의 경우 선입선출이기 때문에 shift메소드를 사용함
    const cur = queue.shift();
    
    //그래프 cur 정점에 있는 간선들을 전부 순회함
    for (let i = 0; i < adjList[cur].length; i++) {
      //방문하지 않은 queue인 경우, 삽입하고 해당 버텍스의 방문을 표시함
      if (!visited[adjList[cur][i]]) {
        queue.push(adjList[cur][i]);
        visited[adjList[cur][i]] = true;
      }
    }
  }
}

 

2. DFS(Depth-First Search)

DFS는 깊이를 우선적으로 탐색하는 깊이 우선 탐색이다. 한 정점에서 다른 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색한 후에 다음 정점으로 넘어가는 것이다. DFS를 적용해 문제를 해결할 때는 일반적으로 재귀를 사용해서 해결한다.

function dfs(adjList, vertex, visited) {
  //해당 정점에 방문했음을 표시
  visited[vertex] = true;
  //해당 버텍스의 모든 간선을 순회함
  for (let i = 0; i < adjList[vertex].length; i++) {
    if (!visited[adjList[vertex][i]]) {
      //dfs를 호출해 모두 방문함 (다음 정점을 넣어 재귀)
      dfs(adjList, adjList[vertex][i],visited);
    }
  }
}

 

• 느낀점

빡세다. 이게 기초라니 역시 보통이 아니다 싶다. 심지어 아직 갈길이 태산이라는 것이다. 지금 진행하는 부트 캠프의 진도를 따라가느라 여러모로 정리하고 복습하는 시간이 딜레이 되다 보니 블로깅 역시 계속 늦어진다. 그러나 복습하면서 느낀 것은 처음 볼 때랑 두번째로 볼때 그리고 지금 블로깅 하면서 내용을 정리 할 때 보이는게 다르다는 것이다. 확실히 어떤 것이든 반복 과정이 있으면 훨씬 난이도가 낮아짐을 느낀다. 다행인 것은 이런 과정이 계속 반복되다 보니 새롭거나 어렵다 느껴지는 것에 대한 두려움이 조금씩 덜어지는 것이다.