Algorithms/tree13 알고리즘 문제 해결 전략 2 6장 트리 (9) 26.4 트라이를 이용한 다중 문자열 검색 트라이에 포함된 문자열들이 접두사를 공유할 경우, 이 접두사들은 같은 노드에 대응된다는 점을 이용해 탐색 공간을 줄이는 알고리즘을 설계할 수 있음. KMP 알고리즘은 전처리 과정에서 부분 매치 테이블을 계산하는데, 이것은 바늘 문자열의 각 접두사마다 이 접두사의 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산해 둔 것임. 대응에 실패했을 때 어디로 가서 검색을 계속해야 할지 알려준다는 의미에서 이와 같은 정보를 실패함수라고도 부름. 아호 코라식 알고리즘은 문자열 검색 알고리즘이라고 부름. 아호-코라식 알고리즘은 긴 문서에서 많은 문자열을 동시에 찾아야 하는 검색 엔진 등에서 특히 유용하게 사용됨. 실패 함수의 계산 HARD 2021. 7. 8. 알고리즘 문제 해결 전략 2 6장 트리 (9) 26. 트라이 26.1 도입 문자열 특화 자료 구조의 대표적인 것임. 트라이는 문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있음. 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리임. 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결됨. 트라이의 루트는 항상 길이 0인 문자열에 대응되며, 노드의 깊이가 깊어질 때마다 대응되는 문자열의 길이는 1씩 늘어남. 트라이의 한 노드를 표현하는 객체는 자손 노드들을 가리키는 포인터 목록과, 이 노드가 종료 노드인지를 나타내는 불린 값 변수로 구성됨. 알파벳 대문자로만 구성된 문자열을 저장하는 트라이의 각 노드는 각 노드가 .. 2021. 7. 8. 알고리즘 문제 해결 전략 2 6장 트리 (9) 25 상호 배타적 집합 25.1 도입 상호 배타적 집합 이렇게 공통 원소가 없는, 다시 말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온-파인드 자료 구조임. 배열로 상호 배타적 집합 표현하기 belognsTo[]. 찾기 연산이 O(1)이라는 점이 아주 좋음. 합치기 연산을 빠르게 하려면? 트리를 이용한 상호 배타적 집합의 표현 트리의 루트에 있는 원소를 각 집합의 대표. 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야 함. struct NaiveDisjointSet { vector parent; NaiveDisjointSet(int n):parent(n) { for (int i = 0; i < n; i++) parent[i] = i; } in.. 2021. 7. 5. 알고리즘 문제 해결 전략 2 6장 트리 (8) 24.6 펜윈 트리: 빠르고 간단한 구간 합 구간 중 필요한 부분만 남긴 결과를 보여줌. 남은 구간은 수는 정확하게 n개임. 물론 n개의 수에 대한 부분 합을 n개의 숫자에 저장하는 것이니 놀랍지는 않지만, 구간 트리에 비하면 꽤 큰 절약임. 어떤 부분 합을 구한든 O(lgn)개의 구간 합만 있으면 된다는 사실. 각 구간에 대해 오른쪽 끝 원소의 인덱스와 이들의 이진수 표현을 보여줌. 다른 부분 합에 대해서 일일이 확인해 보면 오른쪽 끝 위치의 이진수 표현에서 마지막 비트를 지우면 다음 구간을 쉽게 찾을 수 있음. 펜윅 트리에서 배열의 값을 변경하는 것은 해당 위치의 값에 숫자를 더하고 빼는 것을 구현함. 맨 오른쪽에 있는 1인 비트를 스스로에게 더해 주는 연산을 반복하면 해당 위치를 포함하는 구간들을 .. 2021. 7. 5. 알고리즘 문제 해결 전략 2 6장 트리 (7) 24.2 문제: 등산로 등산로의 난이도는 등산로를 가다 만나는 표지판 중 최대 해발 고도와 최저 해발 고도의 차이임. 24.3 풀이: 등산로 최소치를 구하는 RMQ 클래스를 재활용함. 24.4문제: 족보 탐험 어떤 가문의 족보가 시조부터 시작해 쭉 주어질 때, 두 사람의 촌수를 계산하는 프로그램. 24.5 풀이: 족보 탐험 트리의 최소 공통 조상 찾기 트리를 일렬로 펴기 트리에는 항사 n-1개의 연결이 있으므로, 2n-2번 움직이게 됨. 처음에 루트에서 시작하는 것도 경로에 포함되므로, 전체 경로의 길이는 2n-1이 됨. - u를 포함하는 서브트리에서 v를 포함하는 서브트리로 넘어가려면 LCA(u,v)를 거치지 않으면 안됨. - LCAu,v)에서 그 부모 노드로 이 경로가 올라가려면 그 전에 LCA(u,.. 2021. 7. 5. 알고리즘 문제 해결 전략 2 6장 트리 (6) 24 구간 트리 24.1 구간 트리: 구간에 대한 질문 대답하기 segment tree는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 함. 해당 배열을 전처리해 구간 트리를 생성하면 같은 연산을 빠르게 구현할 수 있음. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것임. 구간 트리의 표현 꽉 찬 이진 트리는 이진 검색 트리처럼 포인터로 연결된 객체로 표현하기보다 배열로 표현하는 것이 메모리를 더 절약할 수 있음. 구간 트리의 초기화 구간 트리의 각 노드에 대해 위치 등을 저장해 두지 않는 것을 유의함. 해당 노드를 찾아가는 과정에서 표현하는 구간을 동적으로 계산할 수 있기 때문에 따로 저장해 둘 필요가 없음. struct RMQ {.. 2021. 7. 5. 알고리즘 문제 해결 전략 2 6장 트리 (5) 22.7 문제: 삽입 정렬 뒤집기 삽입 정렬은 A가 정렬된 배열일 때, A[i]를 적절한 위치를 만날 때까지 왼쪽으로 한 칸씩 움직임. 예제에서 각 위치에 있는 값들이 움직인 칸수를 표현하면 {0, 1, 1, 2, 3}이 됨. 이때 원래 수열을 찾아내는 프로그램을 작성하시오. 22.8 풀이: 삽입 정렬 뒤집기 이 알고리즘을 구현하기 위해서는 후보들의 집합 중 k번째 원소가 무엇인지를 찾고, 삭제하는 작업을 빠르게 수행할 수 있어야 함. 이진 검색 트리를 사용하면 이런 일을 O(lgN) 시간에 할 수 있음. void solve() { Node* candidates = NULL; for (int i = 0; i < n; ++i) candidates = insert(candidates, new Node(i +.. 2021. 7. 5. 알고리즘 문제 해결 전략 2 6장 트리 (4) 22.6 균형 잡힌 이진 검색 트리 직접 구현하기:트립 문제는 AVL트리나 레드 블랙 트리 등 교과서에 실리는 대부분의 균형 잡힌 이진 검색 트리들은 구현이 매우 까다로움. 구현이 간단한 이진 검색 트리를 사용함. 대표적인 것은 트립(treap). 트립의 정의 트립은 입력이 특정 순서로 주어질 때 그 성능이 떨어진다는 이진 검색 트리의 단점을 해결하기 위해 고안된 일종의 랜덤화 된 이진 검색 트리임. 트리의 형태가 원소들의 추가 순서에 따라 결정되지 않고 난수에 의해 임의대로 결정됨. 이와 같은 속성을 유지하기 위해 트립은 새 노드를 추가될 때마다 해당 노드에 우선순위를 부여함. 트립은 항상 부모의 우선순위가 자식의 우선순위보다 높은 이진 검색 트리를 만듭니다. 트립의 조건을 다음 두 가지로 정리할 수 .. 2021. 7. 3. 알고리즘 문제 해결 전략 2 06장 트리 (3) 22. 이진 검색 트리 22.1 도입 자료들을 일정한 순서에 따라 정렬한 상태로 저장해 둠. 검색 트리는 이 점을 이용해 원소의 추가와 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 할 수 있음. 검색 트리 중 가장 흔하게 사용되는 것이 바로 이 장에서 소개할 이진 검색트리와 그 변종들임. 이진 검색 트리들은 아주 널리 사용됨. 22.2 이진 검색 트리의 정의와 조작 정의 이진 트리란 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미함. 이진 검색트리에서 원하는 값을 찾는 과정은 배열에서의 이진 탐색과 비슷함. 순회 이진 검색 트리를 중위 순회하면 크기 순서로 정렬된 원소의 목록을 얻을 수 있음. 자료의 검색 한 번 원소를 비교하는 것 만으로도 찾.. 2021. 7. 3. 이전 1 2 다음
