트리

18장 그래프로 뭐든지 연결하기

페이스북 혹은 인스타 같은 소셜 네트워크에서 친구 관계는 상호적이다. 이를 구현하기 위해 2차원 배열을 사용한다면 특정 유저의 친구를 찾기 위해 목록 내 관계를 일일히 확인해야 하고, 이는 O(N)이 걸리는 매우 느린 방법이다. 이때 그래프라는 자료 구조를 사용하면 O(1) 시간 만에 찾을 수 있다. 18.1 그래프 그래프는 관계에 특화된 자료 구조로서 데이터가 서로 어떻게 연결되는지 쉽게 이해시켜 준다. 소셜 네트워크의 예시에선 한 사람은 한 노드로, 사람 간 친구 관계는 선으로 표현한다. 18.1.1 그래프 대 트리 트리도 그래프의 한 종류다. 두 자료 구조 모두 서로 연결되는 노드로 구성된다. 모든 트리는 그래프지만, 그래프가 모든 트리는 아니다. 트리로 규정되는 그래프는 사이클이 있을 수 없으며,..

17장 트라이(trie)해 보는 것도 나쁘지 않다

스마트폰의 자동 완성 기능이 어떻게 동작하는가? 단어들 모두를 배열에 저장했다면 O(N)으로 느릴 것이고, 해시 테이블은 단어를 통째로 해싱해서 키로 삼아야 하므로 사용할 수 없다. 정렬된 배열을 사용한다면 O(logN)로 빨라질 것이다. 하지만 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다. 트라이는 자동 완성이나 자동 수정 같은 중요한 기능을 지원한다. 17.1 트라이 트리의 한 종류인 트라이는 자동 완성 같은 텍스트 기반 기능에 이상적이다. 트라이는 추출을 뜻하는 retrieval에서 왔으니 트리로 발음해야 옳지만, 트리라는 발음이 모든 트리 기반 자료 구조에 보편적으로 쓰이므로 혼동을 막고자 트라이라고 발음한다. 17.1.1 트라이 노드 대부분의 트리처럼 ..

15장 이진 탐색 트리로 속도 향상

정렬 알고리즘은 아무리 빨라도 O(NlogN)시간이 걸린다. 따라서 데이터를 자주 정렬해야 하면 다시 정렬하는 일이 없게 애초에 데이터를 항상 정렬된 순서로 유지하는 편이 합리적이다. 정렬된 배열은 순서대로 데이터를 유지하는 간단하면서도 효과적인 도구다. 또한 특정 연산에 매우 빨라서 읽기에는 O(1), 이진 검색을 사용할 때는 O(logN)이 걸린다. 하지만 삽입과 삭제가 상대적으로 느리다. 최악의 시나리오일 경우 N단계가 걸리고, 평균적으로 N / 2 단계가 걸린다. 즉 O(N)이므로 단순한 삽입이나 삭제치고는 느리다. 전반벅으로 빠른 속도를 내는 자료 구조를 원한다면 해시 테이블이 좋은 선택지다. 해시 테이블은 검색, 삽입, 삭제가 O(1)이다. 연산이 빠르지만 순서를 유지하지 못하므로 알파벳순으로..