누구나 자료구조와 알고리즘 #6

17장 트라이(trie)해 보는 것도 나쁘지 않다.

• 트라이

  • 트라이(trie)는 자동 완성 같은 텍스트 기반 기능에 이상적인 자료구조로 추출(retrieval)이라는 단어에서 유래되었으나 트리(tree)와의 혼동을 막기 위해 트라이로 발음한다.
  • 트라이도 트리처럼 다른 노드를 가리키는 노드들의 컬렉션이지만 자식 노드 개수에 제한이 없다.
  • 각 트라이 노드마다 해시 테이블을 포함하는 형태로 트라이 노드를 구현할 수 있다.

  class TrieNode:
    de __init__(self):
      self.children = {}

• 단어 저장

  • "ace"라는 단어를 저장할 경우 루트 노드의 키 "a"의 트라이 노드의 키 "c"의 트라이 노드의 키 "e"의 트라이 노드의 키 "*"에 nil 값을 저장한다.

  {
    "a": {
      "c": {
        "e": {
          "*": nill
        } 
      } 
    }
  }

• 별표(asterisk)의 필요성

  • 별표를 사용하는 이유는 "bat"와 "batter"이라는 단어를 저장하고 싶다고 할때 "bat"라는 단어가 겹치기 때문에 "t"에서 값이 끝나는지 다음 알파벳이 이어지를 구분하기 위해 "*"이라는 키를 사용하여 구분할 수 있다.

• 트라이 검색

  • 자동완성 기능에서 검색의 목적은 문자열이 완전한 단어인지 알아내는 것과 어떤 단어의 접두사인지를 알아내는 것인데 후자를 구현하면 완전한 단어도 자연스레 찾을 수 있다.
  • 접두사 검색 알고리즘은 다음과 같은 단계를 수행한다.
    1. currentNode라는 변수를 만든다. 알고리즘을 시작할 때 이 변수는 루트 노드를 가리킨다.
    2. 검색 문자열의 각 문자를 순회한다.
    3. 검색 문자열의 각 문자를 가리키며 currentNode에 그 문자를 키로 하는 자식이 있는지 본다.
    4. 자식이 없으면 검색 문자열이 트라이에 없다는 뜻이니 None을 반환한다.
    5. currentNode에 현재 문자를 키로 하는 자식이 있으면 currentNode를 그 자식 노드로 업데이트 한다. 이어서 2단계로 돌아가 검색 문자열 내 각 문자를 계속 순회한다.
    6. 검색 문자열을 끝까지 순회했으면 검색 문자열을 찾았다는 뜻이다.

    def search(self, word):
      currentNode = self.root
      
      for char in word:
        if currentNode.children.get(char):
          currentNode = currentNode/children[char]
        else:
          return Node
          
      return currentNode

  • True를 반환하지 않고 currentNode를 반환하는 이유는 자동 완성 기능(접두사 검색 알고리즘)을 지원하기 위해서이다.

• 트라이 검색의 효율성

  • 트라이 검색은 딱 단어의 문자 수 만큼의 단계가 걸린다. "cat"의 경우에 3단계가 걸린다.
  • 단계 수가 검색 문자열의 길이에 따라 달라지기 때문에 상수가 아니며 O(1)이라 말할 수 없지만 N은 일반적으로 자료 구조 내 데이터 양을 말하므로, O(N)이라고 말하면 오해의 소지가 있다.
  • N은 트라이 내 노드 수를 뜻하므로 이 값은 검색 문자열 내 문자 수보다 훨씬 크다.
  • 많은 교재에서 이 복잡도를 O(K)라고 표현하며 데이터의 양이라고 할 수 있는 트라이 노드의 크기가 커지더라도 O(K) 알고리즘은 항상 K단계가 걸리기 때문에 매우 효율적이다.

• 트라이 삽입

  1. currentNode라는 변수를 만든다. 알고리즘을 시작할 때 이 변수는 루트 노드를 가리킨다.
  2. 검색 문자열의 각 문자를 순회한다.
  3. 검색 문자열의 각 문자를 가리키며 currentNode에 그 문자를 키로 하는 자식이 있는지 본다.
  4. 자식이 있으면 currentNode를 그 자식 노드로 업데이트하고 2단계로 돌아가 검색 문자열 내 다음 문자로 넘어간다.
  5. currentNode에 현재 문자와 일치하는 자식 노드가 없으면 자식 노드를 생성하고 currentNode를 이 새 노드로 업데이트한다. 이어서 2단계로 돌아가 검색 문자열 내 다음 문자로 넘어간다.
  6. 삽입할 단어의 마지막 문자까지 삽입했으면 마지막 노드에 "*" 자식을 추가해 단어가 끝났음을 알린다.

    class Trie {
      constructor() {
        this.root = new TrieNode();
      }
  
      insert(word) {
        let currentNode = this.root;
  
        for (const char of word) {
          if(currentNode.children[char]) {
            currentNode = currentNode.children[char];
          } else {
            let newNode = new TrieNode();
            currentNode.children[char] = newNode;
  
            currentNode = newNode;
          }
        } 
  
        currentNode.children["*"] = null;
      }
    }

  • 검색처럼 트라이 삽입에도 K + 1 => O(K)의 시간복잡도를 가진다.

• 자동 완성 개발

  • 단어 수집

    collectAllWords(node=null, word="", words=[]) {
      let currentNode = node || this.root;
    
      for (let [key, childNode] of Object.entries(currentNode.children)) {
        if (key === "*") {
          words.push(word);
        } else {
          this.collectAllWords(childNode, word + key, words)
        }
      }
      return words;
    }

    트라이 내에 있는 모든 단어를 배열에 담아 리턴하는 변수로 루트 노드에서 word에 해당하는 글자를 추가하면서 재귀 함수가 실행되는 형태로 구현하였다.

  • 자동 완성 기능

    autocomplete(prefix){
      let currentNode = this.search(prefix)
      if (!currentNode) {
        return null
      }
      return this.collectAllWords(curentNode, prefix)
    }

    search 메서드를 사용하여 현재 단어와 일치하는 노드를 찾고 collectAllWords로 해당 노드에 포함된 모든 단어를 담은 배열을 출력하면 자동완성 기능이 구현된다.

  • 자동완성 기능은 사용자가 입력할 수 있는 모든 단어를 보여주는 것이 아니라 자주 사용할 만한 단어를 보여주는 것이 일반적이므로 *의 값으로 null이 아니라 검색 되는 횟수를 저장하여 점수가 높은 단어를 우선적으로 리턴할 수 있도록 구현할 수 있다.

18장 그래프로 뭐든지 연결하기

• 그래프
  • 그래프는 관계에 특화된 자료구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜주며 노드와 노드간의 관계를 나타내는 간선으로 이루어져 있다.
  • 모든 트리는 그래프의 한 종류이지만 그래프는 노드가 서로 순환적으로 참조하는 사이클(cycle)을 허용하고 간선이 없는 노드도 존재하므로 반대의 관계는 될 수 없다.
  • 그래프에서 각각의 데이터를 정점(vertex)라고 부르고 정점을 잇는 선을 간선(edge), 간선으로 연결된 정점은 서로 인접한다(adjacent)라고 말하며, 인접한 정점을 이웃(neighbor)이라고 한다.
• 방향 그래프
  • 소셜 네트워크에서는 관계가 상호적이지 않고 일방적으로 다른 사람을 팔로우 할 수 있기 때문에 이를 구현하기 위해 간선에 방향을 포함한 자료구조를 방향 그래프라고 한다.
• 객체 지향 그래프

  class Vertex
    attr_accessor :value , :adjacent_vertices
    
    def initialize(value)
      @value = value
      @adjacent_vertices = []
    end
    
    def add_adjacent_vertex(vertex)
      @adjacent_vertices << vertex
    end
  end

  Vertex 클래스의 value는 한 사람을 나타내고 adjacent_vertices 배열은 그 사람과 연결된 모든 사람을 포함한다.

    def add_adjacent_vertex(vertex)
      return if adjacent_vertices.includes?(vertex)
      @adjacent_vertices << vertex
      vertex.add_adjacent_vertex(self)
    end
  end

  모든 친구 관계가 상호적인 소셜 네트워크를 위한 무방향 그래프를 만든하면 add_adjacent_vertex 메서드를 위와 같이 수정하여 항상 양방향으로 간선이 추가되게 할 수 있다.

• 그래프 탐색

  • 그래프의 탐색은 그래프 내 한 정점에 접근할 수 있을 때 그 정점과 어떻게든 연결된 또 다른 특정 정점을 찾는 것이다.
  • 연결된 그래프에서 한 정점에 접근하여 탐색할 때 같은 노드를 찾는 경로가 여러개 일 수 있다.

• 깊이 우선 탐색(Depth-First Search)

  • 그래프 탐색에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 두 방식이 널리 쓰이고, 먼저 깊이 우선 탐색은 다음과 같이 동작한다.
    1. 그래프 내 임의의 정점에서 시작한다.
    2. 현재 정점을 해시 테이블에 추가해 방문했던 정점임을 표시한다.
    3. 현재 정점의 인접 정점을 순회한다.
    4. 방문했던 인점 정점이면 무시한다.
    5. 방문하지 않았던 인접 정점이면 그 정점에 대해 재귀적으로 깊이 우선 탐색을 수행한다.

  //부트캠프에서 구현한 무방향 그래프의 깊이 우선 탐색
  function connectedVertices(edges) {
    const maxVertex = Math.max(...edges.flat())
  
    const adjList = {};
    for (let i = 0; i <= maxVertex; i++) {
      adjList[i] = [];
    }
  
    for (let i = 0; i < edges.length; i++) {
    adjList[edges[i][0]].push(edges[i][1]);
    adjList[edges[i][1]].push(edges[i][0]);
    }
  
    const visited = {};
    let count = 0; 
    for (let vertex = 0; vertex <= maxVertex; vertex++) {
      if (!visited[vertex]) { 
        dfs(adjList, vertex, visited); 
        count++; 
      }
    }
    return count;
  
    function dfs(adjList, vertex, visited) {
      visited[vertex] = true;
      for (let i=0; i<adjList[vertex].length; i++) {
        if(!visited[adjList[vertex][i]]) {
          dfs(adjList, adjList[vertex][i], visited)
        }
      }
    }
  }

• 너비 우선 탐색(Breadth-First Search)

  • 너비 우선 탐색은 재귀를 사용하지 않고 큐(Queue)를 활용하여 순회하며 다음과 같은 순서로 동작한다.
    1. 그래프 내 아무 정점에서나 시작한다. 이 정점을 "시작 정점"이라 부른다.
    2. 시작 정점을 해시 테이블에 추가해 방문했다고 표시한다.
    3. 시장 정점을 큐에 추가한다.
    4. 큐가 빌 때까지 실행하는 루프를 시작한다.
    5. 루프 안에서 큐의 첫 번째 정점을 삭제한다. 이 정점을 "현재 정점"이라 부른다.
    6. 현재 정점의 인접 정점을 순회한다.
    7. 이미 방문한 인접 정점이면 무시한다.
    8. 아직 방문하지 않은 인접 정점이면 해시 테이블에 추가해 방문했다고 표시한 후 큐에 추가한다.

  //부트캠프에서 구현한 무방향 그래프의 너비 우선 탐색
  function connectedVertices(edges) {
    const maxVertex = Math.max(...edges.flat())
  
    const adjList = {};
    for (let i = 0; i <= maxVertex; i++) {
      adjList[i] = [];
    }
  
    for (let i = 0; i < edges.length; i++) {
    adjList[edges[i][0]].push(edges[i][1]);
    adjList[edges[i][1]].push(edges[i][0]);
    }
  
    const visited = {};
    let count = 0; 
    for (let vertex = 0; vertex <= maxVertex; vertex++) {
      if (!visited[vertex]) { 
        bfs(adjList, vertex, visited); 
        count++; 
      }
    }
    return count;
  
    function bfs(adjList, vertex, visited) {
      visited[vertex] = true;
      const queue = [vertex]
      while (queue.length > 0) {
        const cur = queue.shift()
        for (let i=0; i<adjList[cur].length; i++) {
          if(!visited[adjList[cur][i]]) {
            queue.push(adjList[cur][i])
            visited[adjList[cur][i]] = true;
         }
        }
      }
    }
  }

• 깊이 우선 탐색 대 너비 우선 탐색

  • 그래프를 탐색하는 동안 시작 정점과 가까이 있고 싶은가 아니면 무조건 멀리 떨어지고 싶은가에 따라 효율성이 달라지므로 시나리오에 따라 적절한 탐색을 사용해야 한다.

• 그래프 탐색의 효율성

  • 최악의 경우에 BFS와 DFS 모두 모든 정점을 순회해야 하므로 O(N)처럼 보이나 인접 정점까지 모두 순회하여 방문했던 정점인지 확인하는 과정이 추가적으로 필요하다. 즉, 각 정점의 인접 정점이 몇 개인지도 함께 고려 해야 한다.
  • 특이하게도 그래프 탐색의 빅오표기법에는 N이 아닌 정점(vertex)을 뜻하는 V, 간선(edge)를 뜻하는 E가 사용된다.
  • 그래프 탐색에서 간선을 두 번 이상 방문하기 때문에 V + 2E로 표현되고 빅오표기법으로 O(V + E)로 표기한다.

• 가중 그래프

  • 가중 그래프(weighted graph)는 간선에 정보가 추가된 자료구조이다.

    class WeightedGraphVertex
      attr_accessor :value, :adjacent_vertices
      
      def intialize(value)
        @value = value
        @adjacent_vertices = {}
      end
      
      def add_adjacent_vertex(vertex, weight)
        @adjacent_vertices[vertex] = weight
      end

    adjacent_vertices를 배열이 아닌 해시 테이블로 구현하여 weight를 저장하므로써 가중 그래프를 구현하였다.
  • 최단 경로 문제
    • 각 공항을 정점으로, 항공 경로롤 간선, 항공료를 가중치로 표현하는 가중 그래프를 구현하여, 가장 저렴한 비행 비용을 구할 수 있는 최단 경로 문제(Shortest Path Problem)를 해결할 수 있다.

• 데이크스트라의 알고리즘

  • 데이크스트라의 알고리즘은 최단 경로 문제를 해결할 수 있는 알고리즘으로 특정 지역으로 가는 최소 비용 뿐만 아니라 모든 지역으로 가는 최소 비용을 알 수 있다.

  • 데이크스트라 알고리즘 준비

    • 시작 도시부터 다른 목적지까지의 최소 비용을 포함하는 cheapest_prices_table 표를 구현한다.
    • 최소 비용으로 가는 직전 경유지를 저장하는 cheapest_privious_stopover_city_table를 구현한다.

  • 데이크스트라의 알고리즘 단계

    1. 시작 도시에 방문해 "현재 도시"로 만든다.
    2. 현재 도시에서 각 인접 도시로의 비용을 확인한다.
    3. 시작 도시에서 각 인접 도시로의 비용이 현재 cheapest_prices_table의 비용보다 저렴하면(혹은 인접 도시가 아직 cheapest_prices_table에 없으면),
       a. cheapest_prices_table을 더 저렵한 비용을 업데이트한다.
       b. 인접 도시를 키로, 현재 도시를 값으로 해서 cheapest_privious_stopover_city_table을 업데이트한다.
    4. 다음으로 시작 도시에서 방문하지 않은 도시 중 비용이 가장 저렴한 도시에 방문해 현재 도시로 만든다.
    5. 알려진 도시에 모두 방문할 때까지 2~4단계를 반복한다.

  • 최단 경로 찾기

    • 데이크스트라 알고리즘을 마친 이후에, 가장 저렴한 비용을 알고 싶을때는 cheapest_prices_table 최단 경유를 알고 싶을 때는 cheapest_privious_stopover_city_table를 통해 알 수 있다.

    class City
      attr_accessor :name, :routes
    
      def initialize(name)
        @name = name
        @routes = {}
      end
    
      def add_route(city, price)
        @routes[city] = price
      end
    end
    
     def dijkstra_shortest_path(starting_city, final_destination)
       cheapest_prices_table = {}
       cheapest_previous_stopover_city_table = {}
    
       unvisited_cities = []
    
       visited_cities = {}
    
       cheapest_prices_table[starting_city.name] = 0
    
       current_city = starting_city
    
       while current_city
    
         visited_cities[current_city.name] = true
         unvisited_cities.delete(current_city)
    
         current_city.routes.each do |adjacent_city, price|
    
           unvisited_cities << 
             adjacent_city unless visited_cities[adjacent_city.name]
    
           price_through_current_city = 
             cheapest_prices_table[current_city.name] + price
    
           if !cheapest_prices_table[adjacent_city.name] ||
            price_through_current_city < cheapest_prices_table[adjacent_city.name]
    
             cheapest_prices_table[adjacent_city.name] = price_through_current_city
             cheapest_previous_stopover_city_table[adjacent_city.name] = 
               current_city.name
           end
         end
    
         current_city = unvisited_cities.min do |city|
           cheapest_prices_table[city.name]
         end
       end
    
       shortest_path = []
    
       current_city_name = final_destination.name
    
       # We loop until we reach our starting city:
       while current_city_name != starting_city.name
    
         shortest_path << current_city_name
    
         current_city_name = cheapest_previous_stopover_city_table[current_city_name]
       end
    
       shortest_path << starting_city.name
    
       return shortest_path.reverse
     end
    
     atlanta = City.new("Atlanta")
     boston = City.new("Boston")
     chicago = City.new("Chicago")
     denver = City.new("Denver")
     el_paso = City.new("El Paso")
    
     atlanta.add_route(boston, 100)
     atlanta.add_route(denver, 160)
     boston.add_route(chicago, 120)
     boston.add_route(denver, 180)
     chicago.add_route(el_paso, 80)
     denver.add_route(chicago, 40)
     denver.add_route(el_paso, 140)
    
     p dijkstra_shortest_path(atlanta, el_paso)

  • 데이크스트라의 알고리즘의 효율성

    • 방문하지 않은 도시를 단순 배열에 저장하면 각 정점이 그래프 내에 다른 모든 정점으로 이어지는 간선을 하나씩 포함하는 최악의 시나리오일 때 O(V2) 단계가 걸리지만 배열 대신 큐로 구현하면 더 속도가 빠르고 데이크스트라의 알고리즘은 여러가지 변형이 있으므로 정확환 시간복잡도를 위해서는 제각각 분석해야 한다.

마치며

이번 파트에서는 트라이와 그래프에 대해서 학습하고 각 자료구조의 효율성과 추가적인 알고리즘에 대해서 학습하였다. 트라이 같은 경우 관련된 코딩 문제를 풀어본 적이 있으나 트라이라는 이름을 가지고 있었는지 효율성은 어떤지에 대해 알지 못했었고 그래프 역시 BFS, DFS 외에 데이크스트라와 같은 알고리즘을 추가로 알 수 있는 내용이 포함되어 있어서 도움이 되었다.