15일차 강의 (31 ~ 33강) (완강)

트라이 (31강)

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

+ 단어 S를 삽입/탐색/삭제할 때 O(|S|)

- 문자열을 그냥 배열에 저장하는 것 보다 최대 '4*글자의 종류'배 만큼 더 사용

(예를 들어 각 단어가 알파벳 대문자로만 구성되어 있을 경우 104배)

 

이론적인 시간복잡도와는 별개로 실제로는 트라이가 해시, 이진 검색 트리에 비해 훨씬 느림.

일반적인 상황에서는 해시나 이진 검색 트리를 사용하는게 좋으나 트라이의 성질을 사용해야 하는 문제가 여럿 존재

 

 

대표적인 활용 사례 : 자동완성기능 (접두사, 접미사 관련)

 

부록A - 문자열 기초 (32강)

문자열을 가지고 복잡한 연산을 해야한다면 그냥 파이썬을 쓰자

 

C++에는 split과 같이 구분자를 기준으로 문자열을 나눠주는 함수가 없음

 

주의사항

s = s + 'a' 시간복잡도 O(n^2)

→ s + 'a' 라는 새 객체를 만든 후 이를 다시 s에 대입하기 때문

s += 'a' 시간복잡도 O(n) 

→ += 연산자를 이용하면 시간복잡도가 더해지는 길이에만 영향을 받음 

 

T.find(P, pos) : 문자열 T에서 pos 이후로 단어 P가 등장하는 최초 위치를 반환, pos 이후로는 P가 등장하지 않을 경우 string::npos를 반환

 

부록B - 동적 배열 (33강)

-