개발일지

문제설명 입출력 예제 개념 부모 노드를 기준으로 트리가 어떻게 구성되어 있는지 파악하는 문제다. 문자열을 효율적으로 관리하는 트라이(trie) 자료 구조를 활용하거나, 트리를 구성해 DFS 탐색을 이용해 문제를 풀어도 되지만, 필자는 set의 자동 정렬 특성을 이용해 모든 문자열 경로를 알파벳 순서로 정렬하고, 이에 해당하는 구조를 출력하는 방식으로 문제를 해결하였다. 풀이(1) #include #include #include using namespace std; int main() { int N, n; cin >> N; set s; while (N--) { string tmp, str; cin >> n; while (n--) { cin >> tmp; str += ' ' + tmp; s.insert(st..

구현　위의 검색 / 삽입 / 삭제의 특성을 가지는 BST를 구현하는 시간을 가지도록 하자. #include using namespace std;struct Node{ int _data; Node* _left, * _right;};　트리에 사용될 노드 구조체 Node를 선언한다. class BST{ Node* _root;public: BST() : _root(nullptr) {}　이진 탐색 트리 클래스 BST를 선언하고, 기본 생성자를 통해 루트 노드를 nullptr로 초기화해 준다. class BST{ ... Node* Find_Implementation(Node* node, int value) { if (!node) // node가 존재하지 않는 경우 return NULL; if (node->_..

이진 검색 트리 (BST)개요　이진 검색 트리(Binary Search Tree - BST)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 이진트리의 일종으로서, 특정한 규칙을 통해 검색을 하는 자료구조다. 각 노드는 하나의 값을 가지며, 다음과 같은 특징이 있다.왼쪽 노드의 값 ≤ 부모 노드의 값 ≤ 오른쪽 노드의 값중복된 값을 갖는 노드가 존재하지 않음이진 탐색 트리의 모든 서브 트리도 이진 탐색 트리따라서 BST는 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있다. 이를 그림으로 나타내면 다음과 같다. 　  　이러한 BST는 이름에 걸맞게 탐색 속도가 빠르다. BST는 높이에 따라 시간 복잡도가 결정되며, 이를 O(높이)로 표현할..