크래프톤 정글 6기 TIL - Review | 트라이( Trie )

정글 공부 키워드를 복습하며.. 모른척 했던 주제에 맞서 보려고 한다.. 그것은

트라이.. 2주차 째 Optional 이라 되어있지만 등장하는 걸 보아선..미루면 안된다..

 

유튭 강의를 하나 슥 볼랬는데 바킹독님 마지막 강의가 트라이였다.

내 최애 남잔데, 그의 최애 알고리즘이 트라이라 그래서 호감도 급 상승..

렛츠 기릿..

 

진심으로 바킹독님..넘 멋지다..

---

트라이( Trie )

문자를 효율적으로 처리하기 위한 트리 자료구조

 

✅ 장점 : 단어의 저장 개수와 무관하게 삽입,탐색, 삭제가 O(|S|)의 시간 복잡도를 가진다.
✅ 단점 : 메모리를 많이 차지한다. 트리의 정점의 index를 기록해야해서 int의 4바이트* |S| 만큼 메모리를 더 사용한다.

다른 자료구조와 비교!
이진 검색 트리 : 삽입, 탐색, 삭제가 O(logN) 이지만, 문자열을 검색할 경우 단어의 길이 S 만큼 대조를 해야하기 때문에,
최악의 경우 O( S *  logN ) 이 걸린다.

해시 : 삽입, 탐색, 삭제가 O(1) 이지만, 문자열을 검색할 경우 O( |S| )이 걸리고, 해시 충돌에 따라 성능이 저하 될 수 있다.

 

다른 자료구조와 비교했을 때 확실히 트라이가 시간이 빨라보이지만,

실제로 구현해보면 일반적인 문자열의 삽입, 탐색, 삭제를 수행하는 상황에서

트라이보다 해시나 이진 검색트리가 메모리, 시간 측에서 모두 효율적이다.

 

📍 트라이 삽입 로직

노란색 : 현재 노드( 정점 )

초록색 : 문자열 끝을 알려주는 트리거

 

현재 노드의 자식으로 단어를 추가해주면서

정점이 갱신된다.

 

마지막 글자는 트리거를 갱신해 주면서, 탐색 할 때 글자의 끝임을 알려준다.

 

📍  트라이 검색 로직

정점을 이동하며 글자를 비교한다.

트리거를 통해 단어의 끝임을 알고,

해당 단어가 존재함을 알 수 있다.

 

📍  트라이 삭제 로직

트리의 구조를 변경하면 안되는 트라이 특성상

삭제 작업을 할 때, 정점을 직접적으로 삭제할 수 없다.

따라서 트리거를 지움으로 써 단어가 존재함을 간접적으로 삭제한다.

따라서 불필요한 단어가 트리에 남아 있을 수 있으므로, 

⭐메모리 측면에서 비효율적일 수 있다.

 

💡 트라이는 삭제가 많은 작업에서는 굉장히 높은 공간 복잡도를 가질 수 있음을 알 수 있다.

 

✏ 트라이 구현

앞서서 말했 듯, 정점의 자식을 관리하는 배열들은

정점의 인덱스로 관리되기 때문에 int 자료형을 사용한다.

 

따라서 단순히 char 배열이라면 문자의 수 N 만큼의 1 * 1 * 단어 개수 byte의 메모리가 사용되겠지만

int 자료형을 사용하기 때문에 4 * 4byte * 단어 개수 의 메모리가 사용된다.

( 26개의 문자를 사용한다면 그 4배인, 104 * 단어 개수  byte배 만큼 사용된다. )

 

메모리 절약 방법

출처 : https://blog.encrypted.gg/1059( BaaaaaaaarkingDog Trie 블로그 글 )

 

출처 : https://blog.encrypted.gg/1059( BaaaaaaaarkingDog Trie 블로그 글 )

가정한 시간, 공간 복잡도와 

실제 시간과 메모리 사용정도는 확연히 다름을 볼 수 있다.

 

일단 정적배열은 당연히 시간은 적게 걸리지만 메모리가 많이 사용되었고,

동적 배열과 연결리스트는 정점 리스트를 검색 할 때 O(1)이 아닌 O(26) 만큼 시간이 걸리기 떄문에 기하급수적으로 오래 걸리는 것을 볼 수 있다.

 

이진 검색트리는 메모리는 정적 배열과 비슷하지만 시간은 정적 배열보다 훨씬 느린 것을 볼 수 있다.

 

반면, 해시는 충격적인 결과가...나왔는데. 이는 아무래도 단어를 저장하는데 각각의 문자는 중복됨이 많으니 아마 해시 충돌의 발생률이 높아져서 시간이 오래 걸린 것 같다는 생각이 든다.

공간 복잡도도,, 뭐 애초에 이걸 해시로 구현하는데 웃김..( 쓰기 귀찮아서 이렇게 쓰는건 아님 )