알고리즘 문제해결전략(100)
-
[트리] [시도x] FAMILYTREE 족보 탐험
FAMILYTREE algospot.com :: FAMILYTREE 족보 탐험 문제 정보 문제 촌수는 혈연관계의 멀고 가까움을 의미하는 숫자로, 고려 말에 들어와 조선 시대에 정착된 것으로 알려져 있습니다. 촌수를 세는 계촌법은 부모와 자식간이 1촌이 되 www.algospot.com 이 문제의 핵심은 '전위 탐색' 이다. 전위 탐색은 트리를 재구성하고, 부분 구간을 생성할 수 있게 해준다. 1. 생각. 이 문제를 풀기 위해서는 성벽 문제와 마찬가지로 두 사람의 두 노드간의 길이를 구하는 문제이므로 최소 공통 조상을 찾아야 할 거 같다. 최소 공통 조상을 찾으려면 일단 트리를 구현해야한다. 트리를 구현한뒤 depth를 구해 각 번호마다 따로 저장해놓는다. 그 후 2 * lgn 만에 두 노드를 찾은후 거슬..
2021.02.08 -
[트리] MORDOR 등산로
1. 문제 표지판번호가 0 ~ n-1 인 표지판이 있는 등산로가 있다고한다. 표지판에는 해발고도가 적혀있고 배열 h에 번호마다 해발고도가 저장되어있다. a번 표지판에서 b번 표지판까지의 등산로의 난이도를 a~b의 최대 해발고도와 최소 해발고도의 차이라고 한다. a, b가 주어졌을때 난이도를 구하는 함수를 만드라는게 이 문제의 의도이다. 2. 구간 트리 초기화 pair 객체를 가지는 구간 트리를 만들어서 각 구간마다 최대 최소인 원소를 저장해야한다. 이는 바텀업 방식으로 재귀를 이용하여 리프부터 루트까지 각 노드를 채워야한다. 기저조건으로 구간의 길이가 1 일때(리프) 구간은 최대와 최소가 같은 pair을 반환한다. 재귀를 이용하여 왼쪽, 오른쪽 서브트리를 루트로 합친다. 합칠때 최대는 최대끼리 최소는 최..
2021.02.07 -
[트리] Tree 6: Segment Tree구간 트리 , RMQ, 펜윅 트리(이진 인덱스 트리)
(일반적인 구간트리와는 다른 자료구조, 책에서는 알고리즘 문제를 풀기위한 자료구조를 설명한다.) (일반적인 구간트리는 1차원 좌표상의 구간들을 지정하고 특정 위치를 포함하는 구간들을 찾는 자료구조임.) 1. 구간 트리(segment Tree) 구간 트리는 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록한다. (일차원 배열의 특정 구간) ex) 구간의 최소치를 여러번 구하는 문제. 어떤 배열 A의 부분 구간의 최소치를 찾는데 보통 부분 구간을 순회하며 최소치를 찾는다, 이것은 O(N)의 시간이 걸린다. 반면 한번의 전처리를 통해 구간트리를 생성하면, 연산을 더 빠르게 할 수 있다. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다. 구..
2021.02.07 -
[트리] RUNNINGMEDIAN 변화하는 중간값
1. 균형잡힌 이진 검색트리를 이용한 풀이 트립 을 구현하여 수열이 추가될때마다 이진 검색트리를 유지 시키고, k번째 수열을 찾는 kth함수를 구현하여 중간값을 찾는다. 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 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103..
2021.02.07 -
[트리] Tree 5: 우선순위 큐와 이진 힙
1. 우선순위 큐와 이진 힙 트리와 밀접하게 연관된 다른 자료 구조로 우선순위 큐가 있다. 이것은 순서대로 기다리고 있는 자료들을 저장하는 자료구조이다. 일반 큐와는 다른 점은 가장 먼저 입력된 자료가 가장 먼저 꺼내지는 것이 아니라, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다는 것이다. 만약 이것을 균형잡힌 트리를 사용하여 우선순위 큐를 구현하게되면 삽입 삭제 전부 lgn 시간에 수행할 수 있다. 또 이것은 힙(heap)으로도 구현할 수 있으며 이는 훨씬 단순한 구조이다. 힙은 가장 큰 원소, 가장 작은 원소를 찾는데 최적화된 형태의 이진 트리로,(최대힙 max heap 최소힙 min heap) 삽입연산과 가장 큰 원소를 삭제하는 연산 모두 O(lgn)시간에 수행가능하다. 우선순위와 자료의 쌍을 ..
2021.02.06 -
[트리] [x]INSERTION 삽입 정렬 뒤집기
1. 삽입정렬 11:38 삽입 정렬은 정렬된 부분 배열을 유지하며 이 배열에 새 원소를 삽입해나간다. void insertionSort(vector& A) { for(int i = 0; i 0 && A[j-1] > A[j]) { swap(A[j-1], A[j]); --j; } } } 삽입 정렬이 0~i-1 이 정렬된 배열을 가질때 i를 적절한 위치까지 한칸씩 옮긴다. 길이 N인 수열을 삽입 정렬했을 때 각 원소가 몇칸이나 앞으로 이동했는지 를 알고 있을 때 원래 수열을 찾아내야하는게 이 문제의 내용이다. 2. 트리 일단 1~n까지 임의로 원소를 만들어. 트리를 형성한다. 주어진 배열은 각 원소가 몇칸이나 앞으로 이동했는지 나타내는 배..
2021.02.06