Done is better than perfect

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다. 앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. | 여섯 번째 순서는 힙이다. heap이란 완전 이진트리의 일종으로 부모 노드와 자식 노드 간에 항상 대소 관계가 성립하는 자료구조이다. 부모의 노드가 자식 노드보다 크다면 Max Heap, 작다면 Min Heap이라고 한다. 이때 부모 노드와 자식 노드 간에 관계만 존재할 뿐 형제 노드 사이에는 아무런 관계가 없다. 위에서 말한 대소관계 이외에도 따로 우선순위를 위한 정의가 가능하며, 그러한 자료구조를 우선순위 큐라고도 한다. 힙은 보통 힙정렬 알고리즘, 우선순위 큐의 구현 등에 사용된다. 항상 최솟값 혹은 최..

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다. 앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. | 다섯 번째 순서는 트리이다. 트리는 계층적으로 구성되어 있고 서로 연결되어있는 데이터에 적합한 계층적 자료구조이다. 이 구조는 링크드 리스트 와는 다른 자료구조이지만, 링크된 요소끼리는 선형 순서로 링크드 리스트라고도 볼 수 있다. 트리는 오래전부터 다양한 형태로 계속 연구되어 발전되어 왔고, 활용되었으며 또 특정 상황 및 애플리케이션에 맞는 제약사항을 가지게 되었다. 트리의 형태로는 대부분이 알고 있는 이진 탐색 트리부터 B 트리, 레드 블랙 트리, AVL 트리 등이 있다. 이진 탐색 트리는 말 그대로 데이..

Question Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. 이진 탐색 트리와 정수 k가 주어졌을 때, 모든 노드 중 k번째로 작은 값을 리턴하는 함수를 작성하라. 제약사항 The number of nodes in the tree is n. 1 right); } int kthSmallest(TreeNode* root, int k) { vector node_val_vec; AddAllElement(node_val_vec, root); return node_val_vec[k-1]; } }; Time..

Question You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition: 완전 이진트리가 주어진다면 같은 레벨의 노드를 모두 오른쪽으로 연결하는 함수를 작성하라. struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be s..

Question Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. 이진 탐색 트리의 preorder 순서와 inorder순서로 탐색한 결과인 두 배열이 주어질 때, 원래의 이진트리를 출력하라. 제약사항 1

Question 주어진 Binary Tree를 inorder (중위 순회) 방식으로 탐색하는 문제이다. 자료구조의 Binary Tree의 탐색 부분을 공부할 때 접하게 되는 기본적인 순회 방법 중 하나로 , 재귀적인 방법을 사용하면 간단하게 풀 수 있다. 하지만 문제에서는 iterative방식으로 해결해 볼 것 을 권장하고 있다. 제약사항 노드의 개수는 최소 0개 최대 100개이다 각 노드의 값은 최소 -100 ~ 최대 100이다 Solution 가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)) 트리 노드의 개수를 n이라 했을 때 적어도 한번씩은 다 방문해야 하므로 시간 복잡도는 O(n)이다 고려사항 빈 노드가 주어질 때 Solution1 (Recursive) 가장 기본적인..