📗 자료구조

데브코스 강의를 듣고 보충하여 정리한 글 😚

---

자동 완성

구글이나 네이버 같은 검색 사이트에서 텍스트를 입력하면 그에 맞는 추천 검색어들이 아래에 나타난다.

(시험 기간 가장 많이 검색하는 예시를 가져와봤다.)

과연 이런 자동완성 기능은 어떻게 코드를 짜야 효율적으로 구현할 수 있을까?

물론 GPT한테 물어보면 바로 알려준다.

그래도 혼자서 한 번 방법을 생각해보자.

나는 단순하게, 이미 입력했던 문자열들을 한 리스트에 저장한 뒤, 지금 입력하고 있는 문자열에 해당되는 값만 뽑아 출력하면 되겠다고 생각했다.

하지만 당연히 나보다 더 똑똑한 사람은 존재했고, 당연히 더 효율적인 방법을 알고 있었다. 이제부터 문자열을 효율적으로 저장하고 탐색할 수 있는 Trie 자료구조에 대해 차근차근 학습해보자!

Trie

우리는 사전에서 "tea"라는 단어를 찾을 때, 곧바로 "tea"가 있는지 눈 크게 뜨고 찾지 않는다.

"t"가 있는 페이지로 가서 그 다음 "te"를 찾고, "tea"까지 찾는 과정을 거친다. 즉, 단어의 첫 번째 글자부터 순서대로 찾는다. 이를 논리적으로 컴퓨터에 적용한 자료구조가 바로 Trie이다.

Trie: 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

사진 출처: 위키백과

새로운 단어 추가

Trie 문자열 삽입(Insert)을 간단하게 설명하면 이렇다.

• "tea"를 입력 받는다.
• 앞글자인 "t"부터 저장한다. 이때 이미 자식 노드에 "t"가 존재한다면, 그대로 다음 글자로 넘어간다. 없다면 새로운 노드를 추가하고, "t"라는 값을 넣어준다.
• 다음에는 "t"에 "e"를 합친 "te"를 자식 노드에 저장한다.
• 마지막으로 "tea"를 자식 노드에 추가한다.

즉, 저장한 글자 수 만큼 트리의 level이 증가한다고 볼 수 있다.

여기서 문자열을 전달하는 경로, 즉 트리의 간선은 이전 정점으로부터 새롭게 추가되는 문자 정보를 가지고 있다. 위의 사진과 같이 "tea"의 경우, "t" 정점으로 부터 뻗어나가는 간선에는 "e"라는 정보가 담겨있는 것이다.

그렇다면 Trie의 탐색은 어떻게 할까?

단어 탐색

• "ten"이라는 글자가 있는지 확인하려고 한다.
• 루트 노드의 자식 노드 중, "t"가 있는지 확인한다. 있다면 그 노드로 이동한다.
• 이후로도 차례대로 "e"와 그 자식 노드인 "n"을 찾는다.

이렇게 말로 간단하게 설명하면 이해하기 굉장히 쉽다. 사실 사진만 봐도 어느정도 로직을 이해할 수 있다.

그러나 이를 자바스크립트 코드로 구현하면, 꽤 코드가 어렵게 느껴질 수 있다.

따라서 나중에 봐도 이해하기 쉽도록 정리해놓으려고 한다.

JS로 Trie 구현하기

과제로 혼자 구현한 코드이기 때문에, 추후 얼마든지 수정될 수 있다.
아니, 100% 수정될 예정이다.

class Queue {
  constructor() {
      this.queue = []
      this.front = 0
      this.rear = 0
      this.size = 0
  }
  
  enqueue(value) {
      this.queue[this.rear++] = value
      this.size++
  }
  
  dequeue() {
      const value = this.queue[this.front]
      delete this.queue[this.front++]
      this.size--
      return value
  }
  
  isEmpty() {
      return this.front === this.rear
  }
}

class Node {
  constructor(value = "") {
    this.value = value
    this.children = new Map()
  }
}

class Trie {
  constructor() {
    this.root = new Node()
  }

  insert(string) {
    let currentNode = this.root

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(
          char,
          new Node(currentNode.value + char)
        )
      }

      currentNode = currentNode.children.get(char)
    }
  }

  has(string) {
    let currentNode = this.root

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return false
      }
      currentNode = currentNode.children.get(char)
    }

    return true
  }
}

미리 보는 전체 코드는 이렇다.
이제 기능별로 나누어 Trie가 어떻게 짜여있는지 자세하게 살펴보도록 하자! 😃

Queue 클래스

class Queue {
  constructor() {
      this.queue = []
      this.front = 0
      this.rear = 0
      this.size = 0
  }
  
  enqueue(value) {
      this.queue[this.rear++] = value
      this.size++
  }
  
  dequeue() {
      const value = this.queue[this.front]
      delete this.queue[this.front++]
      this.size--
      return value
  }
  
  isEmpty() {
      return this.front === this.rear
  }
}

먼저 큐 자료구조를 직접 구현해주었다.
js에는 기본적으로 내장 배열인 queue가 존재한다. 하지만 강의 내용에 있었기 때문에 그냥 똑같이 작성했다. 굳이? 인 사람들은 Queue 클래스를 따로 만들어주지 않아도 된다!

Node 클래스

class Node {
  constructor(value = "") {
    this.value = value
    this.children = new Map()
  }
}

Node 클래스는 한 글자의 문자를 저장할 정점을 뜻한다. 예를 들어 "cat"을 저장할 때 "c"라는 글자를 먼저 저장하고 싶을 때에는 하나의 노드를 생성하고, 그 노드의 value로 "c"를 저장한다. 그리고 이 노드의 children을 새로운 객체로 만들어준다. 이 객체에 저장되는 값은 뒤에서 설명한다.

Trie 클래스

class Trie {
  constructor() {
    this.root = new Node()
  }

  insert(string) {
    let currentNode = this.root

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(
          char,
          new Node(currentNode.value + char)
        )
      }

      currentNode = currentNode.children.get(char)
    }
  }

  has(string) {
    let currentNode = this.root

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return false
      }
      currentNode = currentNode.children.get(char)
    }

    return true
  }
}

Trie 클래스에서는 생성자 함수의 root와 문자를 추가하는 insert 함수, 해당 문자가 있는지 확인하는 has 함수가 구현되어 있다.

1. root
   가장 상단의 루트 노드는 비어있다. 따라서 this.root = new Node()는 root라는 값에 비어있는 노드를 할당한다는 뜻이다.
   또한 Node 클래스는 value와 children이라는 값을 갖고 있었다. root를 출력해보면 해당 값이 나온다.

   Node { value: '', children: Map(0) {}

2. insert 함수
   추가할 문자열의 앞글자부터 검사하며 새로운 노드를 추가하는 과정을 거쳐야 한다.
   처음에 currentNode는 비어있는 루트 노드를 저장한다. 이후, 이 노트의 자식 노드 중 추가한 문자열의 첫 번째 글자를 value로 갖는 노드가 존재하는지 검사한다. 만약 없다면 해당 노드를 새롭게 추가한다.
   만약 "c"라는 문자를 새로운 노드에 추가한다면 루트 노드를 출력했을 때( console.log(trie.root) ) 다음과 같은 값이 나온다.

   Node {
   	value: '',
   	children: Map(1) {
       'c' => Node { value: 'c', children: Map(0) {} }
     	}
   }

   여기서 "a"라는 문자도 추가하면 루트 노드 출력 결과가 아래와 같다.

   Node {
   	value: '',
   	children: Map(2) {
       'c' => Node { value: 'c', children: Map(0) {} },
       'a' => Node { value: 'a', children: Map(0) {} }
     	}
   }

   즉, 하나의 Node는 value와 children을 갖는데, children은 또 자식 node를 가리키는 것이라고 이해할 수 있다.
   
   
   

3. has 함수
   입력받은 문자열을 순회하며, 자식 노드를 갖고 있지 않다면 false를 반환한다. 순회가 끝나면 해당 문자가 이미 저장되었다는 뜻이므로 true를 반환한다.

   
   
   

자동완성 기능 구현

기존에 "hello", "haha", "health", "hero"를 저장해놓았다.
만약 "he"를 입력한다면, ["hello", "health", "hero"]와 같이 자동완성을 해주는 함수를 구현하려고 한다.

기존의 Trie 클래스에 find 함수와 autoComplete 함수를 새롭게 구현해 주었다.

find(string) {
  let currentNode = this.root

  for (const char of string) {
    if (!currentNode.children.has(char)) {
      return undefined
    }
    currentNode = currentNode.children.get(char)
  }

  return currentNode
}

autoComplete(prefix) {
  const prefixNode = this.find(prefix)
  if(!prefixNode || !prefixNode.children.size) {
    return "해당되는 단어가 없습니다."
  }

  const words = []
  const queue = new Queue()
  queue.enqueue(prefixNode)

  while(queue.size) {
    const currentNode = queue.dequeue()
    if (!currentNode.children.size) {
      words.push(currentNode.value)
      continue
    }

    for(const child of currentNode.children.values()) {
      queue.enqueue(child)
    }
  }
  return words
}

find 함수는 has와 거의 똑같지만 반환값이 입력한 문자열에 해당하는 노드이다.

autoComplete 함수에서는 Queue를 사용하여 해당 문자로 시작되는 단어들을 전부 words 배열에 추가해줬다.

❗ 하지만 여기서 예외 케이스가 발생했다.

"hero", "haha", "hello"를 입력하면 문제가 없다.

만약 여기에 "hell"이라는 값을 추가하면?
이미 "hello"에 대한 노드들이 존재하는데, "hell"이라는 단어가 추가되었다는 정보를 절대 알 수 없는 것이다.

const trie = new Trie()

trie.insert("hero")
trie.insert("haha")
trie.insert("hello")
trie.insert("hell")
console.log(trie.autoComplete("he"))

// 출력 값: ["hero", "hello"]

✅ 따라서 이를 해결하기 위해 Node 클래스 생성자 함수에 isWordExists라는 변수를 새롭게 추가해주었다.

class Node {
  constructor(value = "") {
    this.value = value
    this.children = new Map()
    this.isWordExists = false
  }
}

// ...
insert(string) {
  let currentNode = this.root

  for (const char of string) {
    if (!currentNode.children.has(char)) {
      currentNode.children.set(
        char,
        new Node(currentNode.value + char)
      )
    }

    currentNode = currentNode.children.get(char)
  }

  // 순회가 끝나면 해당 노드의 isWordExist 값을 true로 바꿔준다.
  currentNode.isWordExists = true
}

이 변수는 등록된 단어인지 판별하는 값이 저장되어 있다. 그리고 insert 함수에 맨 아래에 순회가 끝나면 현재 노드의 isWordExists 값을 true로 할당해주었다.

이렇게 되면 아까 "c"와 "a"를 추가한 뒤 루트 노드를 출력했을 때 요소 하나가 추가가 된다.

Node {
  value: '',
  children: Map(2) {
    'c' => Node { value: 'c', children: Map(0) {}, isWordExists: true },
    'a' => Node { value: 'a', children: Map(0) {}, isWordExists: true }
  },
  isWordExists: false
}

여기서 루트 노드의 children을 출력하면

Map(2) {
  'c' => Node { value: 'c', children: Map(0) {}, isWordExists: true },
  'a' => Node { value: 'a', children: Map(0) {}, isWordExists: true }
}

이렇게 등록한 "c"와 "a" 노드의 isWordExists 값이 true인 것을 확인할 수 있다.

이러면 autoComplete 함수도 수정해주어야 한다.

autoComplete(prefix) {
  // ...

  while(queue.size) {
    const currentNode = queue.dequeue()
    // 기존 코드: if (!currentNode.children.size) {
    if (currentNode.isWordExists) {
      words.push(currentNode.value)
    }

    for(const child of currentNode.children.values()) {
      queue.enqueue(child)
    }
  }
  return words
}

현재 노드의 자식 노드가 있는지가 아닌, 현재 노드가 단어로 등록이 되었는지를 확인 후 words 배열에 추가하게 된다.

const trie = new Trie()

trie.insert("hero")
trie.insert("haha")
trie.insert("hello")
trie.insert("hell")
console.log(trie.autoComplete("he"))

// 출력 값: ["hero", "hell", "hello"]

이제 정상적으로 "hell"이 출력되는 것을 확인할 수 있다.

+ 추가로 has 함수도 수정했다.

has(string) {
  return this.find(string) ? true : false
}

새로 추가한 find 함수를 활용하여 간결하게 구현했다.

완성 코드

class Queue {
  constructor() {
      this.queue = []
      this.front = 0
      this.rear = 0
      this.size = 0
  }
  
  enqueue(value) {
      this.queue[this.rear++] = value
      this.size++
  }
  
  dequeue() {
      const value = this.queue[this.front]
      delete this.queue[this.front++]
      this.size--
      return value
  }
  
  isEmpty() {
      return this.front === this.rear
  }
}

class Node {
  constructor(value = "") {
    this.value = value
    this.children = new Map()
    this.isWordExists = false
  }
}

class Trie {
  constructor() {
    this.root = new Node()
  }

  insert(string) {
    let currentNode = this.root

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(
          char,
          new Node(currentNode.value + char)
        )
      }

      currentNode = currentNode.children.get(char)
    }

    currentNode.isWordExists = true
  }

  find(string) {
    let currentNode = this.root

    for (const char of string) {
      if (!currentNode.children.has(char)) {
        return undefined
      }
      currentNode = currentNode.children.get(char)
    }

    return currentNode
  }

  has(string) {
    return this.find(string) ? true : false
  }

  autoComplete(prefix) {
    const prefixNode = this.find(prefix)
    if(!prefixNode || !prefixNode.children.size) {
      return "해당되는 단어가 없습니다."
    }

    const words = []
    const queue = new Queue()
    queue.enqueue(prefixNode)

    while(queue.size) {
      const currentNode = queue.dequeue()
      if (currentNode.isWordExists) {
        words.push(currentNode.value)
      }

      for(const child of currentNode.children.values()) {
        queue.enqueue(child)
      }
    }
    return words
  }
}

---

코드 리뷰 후 수정사항

(나중에 내용 추가할 예정)