1. 트라이 문자열은 두 변수를 비교하는데 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 그러므로 이진 검색 트리에서 문자열을 찾는데에 O(mlgn) 의 시간이 걸릴 수 있다. 이와 같은 문제점을 해결하기 위해 고안된 문자열의 특화 자료 구조가 바로 트라이(trie) 이다. 트라이는 문자열의 집합을 표현하는 트리 자료 구조로 검색 수행시 O(M)의 시간이 걸린다. - 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다. - 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결된다. - 트라이의 루트는 항상 길이 0 인 문자열에 대응된다. - 깊이가 깊어질 수록 대응되는 문자열의 길이는 1 씩 증가한다. 트라이에서 중요한..

1. 펜윅트리를 이용한 풀이 처음에 이 문제를 봤을때 펜윅트리를 어떻게 써야할 지 감을 못잡았다. 책에서는 수열의 입력값으로 이루어진 트리를 만들고 해당 입력값이 오게되면 그것을 포함하는 구간을 전부 +1을 해줘서 루트에 현재 수열의 길이를 저장하게 되고 입력값 까지의 부분합을 구하게 되면 현재 수열중에서 입력값보다 작은 것들의 개수를 알 수 있다. 이를 통해 자신보다 큰 원소의 개수를 알 수 있고, 앞으로 몇칸 이동 시켜야하는지 파악할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 5..

1. 상호 배타적 집합 상호 배타적 집합을 표현할 때 유니온-파인드(union-find) 자료구조를 쓴다. 이 자료구조는 독특한 트리이다. 전체 집합을 공통 원소가 없는 여러 개의 부분 집합으로 쪼개어 나누어진 원소들(상호배타적인 부분 집합들) 에 대한 정보를 저장하고, 조작하는 자료구조가 유니온-파인드 자료구조이다. 이 자료구조의 핵심 연산은 다음과 같다. - 초기화: n 개의 원소가 있을 때 자기자신으로만 이루어진 집합들. - 합치기(union): 두 원소 a, b가 있을때 이들이 속한 두 집합을 하나로 합침 - 찾기(find): 어떤 원소 a가 주어질때 이 원소가 속한 집합을 찾는다. 2. 배열을 사용하여 상호 배타적 집합 표현하기 1차원 배열 하나를 이용하여 표현한다 belongsTo[i] = i..

FAMILYTREE algospot.com :: FAMILYTREE 족보 탐험 문제 정보 문제 촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되 www.algospot.com 이 문제의 핵심은 '전위 탐색' 이다. 전위 탐색은 트리를 재구성하고, 부분 구간을 생성할 수 있게 해준다. 1. 생각. 이 문제를 풀기 위해서는 성벽 문제와 마찬가지로 두 사람의 두 노드간의 길이를 구하는 문제이므로 최소 공통 조상을 찾아야 할 거 같다. 최소 공통 조상을 찾으려면 일단 트리를 구현해야한다. 트리를 구현한뒤 depth를 구해 각 번호마다 따로 저장해놓는다. 그 후 2 * lgn 만에 두 노드를 찾은후 거슬..

1. 문제 표지판번호가 0 ~ n-1 인 표지판이 있는 등산로가 있다고한다. 표지판에는 해발고도가 적혀있고 배열 h에 번호마다 해발고도가 저장되어있다. a번 표지판에서 b번 표지판까지의 등산로의 난이도를 a~b의 최대 해발고도와 최소 해발고도의 차이라고 한다. a, b가 주어졌을때 난이도를 구하는 함수를 만드라는게 이 문제의 의도이다. 2. 구간 트리 초기화 pair 객체를 가지는 구간 트리를 만들어서 각 구간마다 최대 최소인 원소를 저장해야한다. 이는 바텀업 방식으로 재귀를 이용하여 리프부터 루트까지 각 노드를 채워야한다. 기저조건으로 구간의 길이가 1 일때(리프) 구간은 최대와 최소가 같은 pair을 반환한다. 재귀를 이용하여 왼쪽, 오른쪽 서브트리를 루트로 합친다. 합칠때 최대는 최대끼리 최소는 최..

(일반적인 구간트리와는 다른 자료구조, 책에서는 알고리즘 문제를 풀기위한 자료구조를 설명한다.) (일반적인 구간트리는 1차원 좌표상의 구간들을 지정하고 특정 위치를 포함하는 구간들을 찾는 자료구조임.) 1. 구간 트리(segment Tree) 구간 트리는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록한다. (일차원 배열의 특정 구간) ex) 구간의 최소치를 여러번 구하는 문제. 어떤 배열 A의 부분 구간의 최소치를 찾는데 보통 부분 구간을 순회하며 최소치를 찾는다, 이것은 O(N)의 시간이 걸린다. 반면 한번의 전처리를 통해 구간트리를 생성하면, 연산을 더 빠르게 할 수 있다. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다. 구..