개발일지

문제설명 입출력 예제 개념 부모 노드를 기준으로 트리가 어떻게 구성되어 있는지 파악하는 문제다. 문자열을 효율적으로 관리하는 트라이(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(높이)로 표현할..

트리 순회개요　앞선 포스팅에선 트리에 원소를 삽입하는 방법에 대해 알아보았다. 이번 포스팅에선 트리의 원소를 순회하는 방법에 대해 알아보도록 하자. 여기서 순회란 모든 노드를 한 번씩 방문하는 것을 의미한다.본문　트리를 순회하는 방법은 크게 4가지가 존재한다.전위 순회(Preorder traversal): 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드, 마지막으로 현재 노드의 오른쪽 하위 노드를 재귀적으로 방문하는 방식.중위 순회(In-order traversal): 왼쪽 노드를 먼저 방문하고, 그다음에는 현재 노드, 마지막으로 오른쪽 노드를 방문하는 방식.후위 순회(Post-order traversal): 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문하는 방식.레벨 순서 순회(..

트리(Tree)  개요　지금까지 다룬 자료 구조는 순방향과 역방향을 지원하는 선형 자료 구조였다. 이러한 구조는 특정 데이터를 검색할 때 순서대로 자료를 찾아나가야 하는 문제점과, 데이터를 저장하기 위해 일정한 공간을 미리 할당해야 하는 등 제한적인 구조를 갖고 있어 복잡한 문제를 해결하는 데 어려움이 있다. 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다. 　계층적 문제(Hieararchy Problem)란 계층적 속성을 갖는 자료를 선형 구조로 표현하기 어렵다는 것을 의미한다. 다음과 같은 조직도를 표현한다고 해보자.  　이러한 조직을 표현하기 위해서, 기존에 배운 선형 자료 구조인 배열과 벡터, 리스트를 이용해 표현하기는 어려워 보인다. 　순환 종속성(Cyclic Dependency) 문제..