내가 구매한 상품을 구매한 사람들이 구매한 상품을 추천해주는 로직을 구현할 일이 생겼는데 그때 Trie 자료구조를 써보는게 어떻겠냐고 말씀해주신적이 있다 결국은 다른 방식으로 구현했지만 추후에 쓸 일이 있을지도 모르니깐 정리해놔야겠다

Trie(트라이) 자료구조란?

  • 탐색 트리의 일종
  • 보통 문자열에서 많이 씀

    시간 복잡도

  • 정수형 자료형 이진트리 사용시 => O(logN)
  • 문자열 최대 길이가 M일때 이진트리 사용시 => O(log)
  • Trie 자료구조 사용시 => O(M)

참고

[트라이 (컴퓨팅)](https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85) [자료구조]트라이(Trie)