[TIL🔥]Day4(8/5)

Introduction

오늘도 사실 강의는 많이 듣지 못했지만, 그래도 이진 트리 구현도 해보고 그걸 이용해서 전위, 중위, 후위 순회도 재귀 함수 이용해서 구현해보았다.
그래도 조금씩 성장하는 것을 느낀다. 그리고 팀원들이 많이 도와줘서 너무 고맙다...🙌

오늘 새롭게 배운 것

오늘도 계속해서 자료구조 & 알고리즘을 배워나갔다.

1. 트리(Tree)
2. 힙(Heap)
3. 트라이(Trie)
4. 정렬(Sort)

사실 고백하자면, 다른 것들은 대부분 파이썬으로 접해봤지만 트라이는 처음 접해봤다... 나자신 반성해라...

그래서 오늘은 트라이에 대해 알아보려고 한다.

📚 트라이(Trie)

트라이(Trie)란?

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

트라이(Trie)의 특징

• 검색어 자동 완성, 사전 찾기 등에 활용
• 단순 비교보다 효율적으로 찾기가 가능
• L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼의 시간 복잡도를 가진다
• 하지만, 각 정점이 자식에 대한 링크를 전부 가지고 있어 저장 공간을 많이 차지한다

트라이(Trie)의 구조

• 루트는 비어있다
• 각 간선은 추가될 문자를 키로 가진다
• 각 정점은 이전의 정점의 값 + 간선의 키를 값으로 가진다
• 해시 테이블과 연결 리스트를 이용하여 구현 가능

Comment

오늘은 트라이에 대해 배우고 이를 해시 테이블로 구현해보았다.
내일은 트라이를 이용해 자동 완성 기능을 한번 구현해보고자한다.
아직 걱정만 앞서긴하지만, 그래도 계속 시도하다보면 꼭 성공할 수 있을 것이다.
항상 실패를 두려워하지 않는 자세를 갖자! 💪