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. 우선순위 큐와 이진 힙 트리와 밀접하게 연관된 다른 자료 구조로 우선순위 큐가 있다. 이것은 순서대로 기다리고 있는 자료들을 저장하는 자료구조이다. 일반 큐와는 다른 점은 가장 먼저 입력된 자료가 가장 먼저 꺼내지는 것이 아니라, 우선순위가 가장 높은 자료가 가장 먼저 꺼내진다는 것이다. 만약 이것을 균형잡힌 트리를 사용하여 우선순위 큐를 구현하게되면 삽입 삭제 전부 lgn 시간에 수행할 수 있다. 또 이것은 힙(heap)으로도 구현할 수 있으며 이는 훨씬 단순한 구조이다. 힙은 가장 큰 원소, 가장 작은 원소를 찾는데 최적화된 형태의 이진 트리로,(최대힙 max heap 최소힙 min heap) 삽입연산과 가장 큰 원소를 삭제하는 연산 모두 O(lgn)시간에 수행가능하다. 우선순위와 자료의 쌍을 ..

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를 담는 ..

1. 트리 트리는 계층 관계를 갖는 객체들을 표현하기 위해 만들어진 자료 구조이다. 계층 관계표현 이외도 다른 구조보다 같은 연산을 더 빠르게 할 수 있다. (특히 탐색형 자료 구조) 탐색형 트리 자료구조의 유명한 이진 검색 트리는 모든 숫자에 최대 두개의 하위 숫자만 있으며 어떤 숫자에서든 왼쪽 가지를 따라 내려가면 더 작은 수를 오른쪽 가지를 따라 내려가면 더 큰 수를 만날 수 있다. 이와 같은 특별한 규칙에 의해 탐색을 lgn만에 할 수 있게 된다. 트리의 구성 요소 노드 node: 연결된 노드 간에는 상하위 관계가 있다. 간선 edge: 연결하는 선 상위 노드 parent 하위 노드 child 부모가 같은 노드 sibling 부모 노드와 그의 부모 노드들 ancestor 자식 노드와 그의 자식 노..

1. 트리 생성 이 문제는 외벽안의 성벽들을 트리로 나타낸다음 각 잎에서 잎까지의 경로가 가장 긴 거리를 구하는 문제이다. 따라서 일단 주어진 성벽들의 정보를 가지고 트리를 구성해야한다. 이 트리를 생성하는데 약 n*n*n 이 걸릴 것 같다. 1. 서로 비교하여 노드의 벡터에 포함되어있는것을 넣는다 -> 두개를 비교하니 n*(n-1)/2 2. 각 비교할때마다 부모노드에서 자식노드벡터를 제거해야한다 -> n(점점 작아진다 생각보다 빨리 실행될 것이다) 3. 넣은것들 또한 트리로 정리해야하므로 남은 것들을 재귀호출해야한다. -> n 2번은 총 n(n-1)/2 번 실행될것이고 , 1번 또한 n(n-1)/2 번 실행될것이니 대략 n^2만에 트리를 정리하여 서브 트리만 남겨놓는다. 서브트리를 재귀로 정리해야한다...