자료구조 트라이( 백준 5052 전화번호 목록)

트라이(Trie)

문자열에서의 검색을 빠르게 해주는 자료구조입니다.

우리가 검색을 할 때 자동으로 완성시켜주는 단어들을 보면 트라이가 사용된 예입니다.

 

정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간복잡도를 갖고

길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다.

 

우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다.

트라이의 형태

아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", "ATEV", "DE" ,"DC"} 가 존재할 때 트라이의 예입니다.

다음과 같은 모양으로 트리를 만들어서 연산을 문자열의 길이만큼하는 시간복잡도를 갖게하는 것입니다.

 

이에 따라 트리의 특징은 시간이 O(M)으로 줄여지지만 공간복잡도는 그만큼 늘어나게 됩니다.

 

그럼 파이썬으로 한번 구현해 보겠습니다.

트라이를 활용한 문제풀이

5052 전화번호 목록

www.acmicpc.net/problem/5052

1.접근

전화번호목록이 문자열로 표현이므로 트라이를 활용한다

2.풀이

문제에서 일관성이라는건 해석해보면 어떠한 문자열이 다른문자열의 부분집합이 되는지 안되는지 말하는 문제이다

따라서 모든 단어를 트라이에 넣은후에 bfs로 모든 트리를 탐색해 볼 때 딕셔너리의 크기가 2이상인 곳에 '*'가 포함되있으면 그 곳은 단어가 끝나는 부분이기도하고 단어가 이어지는 부분이기도 한 것이기 때문에 False임을 알 수 있고

bfs에 문제가 없으면 True를 출력한다.

3.코드

4.배운점

• 딕셔너리 자료형을 잘 다루지 못했었는데 좀 더 익숙해지는 계기가 된 것 같다.
• 문제를 풀 때는 꼭 객체를 만들지 않고 풀어도 될것같다.
• 마지막 '*'에 그 문자열을 넣으면 역추적이 필요하지않고 바로 출력할 수 있고 4358 생태학 문제 같은 경우는 문자열과 횟수까지 같이 저장하여 필요한정보를 '*'에 넣는 것이 중요하다
• 문제마다 특성상 꼭 트라이가 가장 빠른 것은 아니다

 

jason9319.tistory.com/129를 보고 공부하였습니다