본문 바로가기

전체 글571

알고리즘 문제 해결 전략 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.
알고리즘 문제 해결 전략 2 06장 트리 (2) 21.5 문제 요새 성벽들의 정보가 주어질 때 임의의 두 지점 간을 이동하기 위해 최대 몇 번이나 성벽을 넘어야 하는지 계산하는 프로그램을 작성하시오. 21.6 풀이: 요새 성벽들은 서로 닿거나 겹치지 않는다는 조건에 주목하면 성이 계층적 구조로 구성되어 있음을 알 수 있음. 따라서 성벽들 간의 포함 관계를 트리로 나타내서 문제를 풀어낼 수 있음. 이렇게 트리를 구성하고 나면, 한 구역에서 인접한 다른 구역으로 가기 위해 성벽을 넘는 일은 이 트리에서 간선을 따라 다른 노드로 옮겨가는 것으로 대응됨. 따라서 두 지점을 왕래하기 위해 성벽을 가장 많이 넘어야 하는 경우를 찾는 문제는 트리에서 가장 멀리 떨어진 두 노드를 찾는 문제가 됨. 트리에서 가장 긴 경로 찾기 이와 같은 모델링 과정을 거치면 이 문제.. 2021. 7. 3.
알고리즘 문제 해결 전략 2 06장 트리 (1) void printPostOrder(const vector& preorder, const vector& inorder) { const int N = preorder.size(); if (preorder.empty()) return; const int root = preorder[0]; const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin(); const int R = N - 1 - L; printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L)); printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N)); cou.. 2021. 7. 1.

티스토리툴바