<div id="readability-page-1" class="page"><div><ol>
<li>트라이 자료구조란?<br>
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자룍조</li>
</ol>
<p>실무 사용 예시 : 검색어 자동완성</p>
<p>2-1 트라이의 특징</p>
<ul>
<li>검색어 자동완성, 사전 찾기 등에 으용</li>
<li>문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.</li>
<li>L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.</li>
<li>대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용</li>
</ul>
<p>2-2 트라이 구조</p>
<ul>
<li>루트는 비어있다.</li>
<li>각 간선(링크)은 추가될 문자를 키로 가진다.</li>
<li>각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.</li>
<li>해시 테이블과 연결 리스트를 이용하여 구현 가능</li>
</ul>
<ol start="3">
<li>
<p>코테<br>
핵심 키워드 : 문자, 학습, 자동완성<br>
대표문제 : 자동완성</p>
<p><img src="https://velog.velcdn.com/images/2taesung/post/df49ef29-916c-4a2c-bd22-9ace5f9ae6dc/image.png"></p>
</li>
</ol>
<pre><code>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);
    }
  }
}

const trie = new Trie();</code></pre></div></div>

2taesung.log

Taesung Lee

트라이 자료구조란?
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자룍조
실무 사용 예시 : 검색어 자동완성
2-1 트라이의 특징
검색어 자동완성, 사전 찾기 등에 으용
문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.
L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 걸린다.
대신 각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용
2-2 트라이 구조
루트는 비어있다.
각 간선(링크)은 추가될 문자를 키로 가진다.
각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
해시 테이블과 연결 리스트를 이용하여 구현 가능
코테
 핵심 키워드 : 문자, 학습, 자동완성
 대표문제 : 자동완성
 
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);
    }
  }
}
const trie = new Trie();

트라이

댓글