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)의 시간이 걸린다. 반면 한번의 전처리를 통해 구간트리를 생성하면, 연산을 더 빠르게 할 수 있다. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진 트리를 만드는 것이다. 구..

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..

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까지 임의로 원소를 만들어. 트리를 형성한다. 주어진 배열은 각 원소가 몇칸이나 앞으로 이동했는지 나타내는 배..

1. 검색 트리 검색 트리는 링크드 리스트나 큐처럼 자료들을 담는 컨테이너지만, 자료들을 일정한 순서에 따라 정렬한 상태로 저장해둔다. 이것은 입력이 주어진 순서에 따라 자료들을 배치하는 리스트나 큐와 다른 속성이다. 이런 속성은 원소의 추가 와 삭제만이 아니라 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 할 수 있다. 이진 검색트리는 특히 아주 널리 사용되기 때문에, 이들의 동작 원리와 장단점은 알아야한다. 대부분 이진 검색트리는 라이브러리에서 제공한다. 2. 이진 검색 트리 이진 트리(binary tree) 란 각 노드가 왼쪽과 오른쪽, 최대 두 개의 자식 노드만을 가질 수 있는 트리를 의미한다. 따라서, 이진 트리는 자식 노드들의 배열 대신 두 개의 포인터 left 와 right를 담는 ..