난이도 : 골드 2 문제 이진 탐색 트리 복원하기 문제 바로가기 1부터 N까지의 모든 정수를 한 번씩 포함하고 있는 수열 A1, A2, ..., AN이 있다. 값이 A1인 노드를 루트로 하는 트리에 A2, A3, ..., AN 을 순서대로 삽입하려 한다. N-1개의 노드를 삽입할 때마다 루트에서 그 노드에 도달하기 위해 거쳐야 하는 간선의 수, 즉 노드의 깊이가 주어질 때 A1, A2, ..., AN을 구하는 프로그램을 작성하시오. 풀이 값 받으면서 2N(n-1)children.size() > 0) { // 왼쪽 자식 존재 Inorder(head->children[0]); } result[head->index] = idx++; if (head->children.size() > 1) { // 오른쪽 자식 ..

BST BST(Binary Search Tree)는 트리의 한 종류이자 이진탐색을 위한 방법 중 하나이다. 과정 BST를 이용한 탐색에서는 다음과 같은 과정을 거친다. 이진 탐색 트리 만들기 (생성) 루트 노드에서 내려가면서 원하는 요소 찾기 (탐색) 삭제 및 삽입 하기 (삭제 / 삽입) 예시 먼저 이진 탐색 트리를 만들어보자. 이진 탐색 트리는 부모 노드를 기준으로 왼쪽 서브트리에는 더 작은 값의 노드가 오른쪽 서브트리에는 더 큰 값의 노드가 있어야한다. 따라서 요소를 하나씩 삽입하면서 알맞은 위치를 찾아주면 된다. 결과적으로 나온 이진 탐색 트리를 중위 순회하면 정렬된 리스트가 된다. 그 다음에는 루트 노드에서 내려가면서 원하는 요소를 찾고 삭제해보자. 원하는 요소는 6이다. 왼쪽 그림에서 오른쪽 그..

힙 용도 구현 종류 연산 정렬 힙 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. partial-ordering (부분 정렬)을 만족하는 left-complete binary tree (좌측 완전 이진 트리) 이다. 부분 정렬을 만족한다는 말은 '부모 노드와 자식노드' 간에는 특정 대소관계 성립하지만, '형제노드'간에는 해당 대소관계가 성립하지 않는다는 뜻이다. 이진 탐색 트리에서는 중복된 값을 허용하지 않지만 힙 트리에서는 허용한다. 용도 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. 배열과 연결리스트를 이용하면 삽입과 삭제 연산 중 하나가 O(n)일 수 밖에 없다. 하지만 힙을 이용하면 가장 큰 값이나 가장 작은 값을 둘 다 O(logn)만에 빠..