꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/6597 아래와 같은 두 성질을 이용하면 쉽게 풀 수 있는 문제였습니다.1. 전위 탐색을 했을 때 제일 앞에 있는 노드가 해당 서브트리의 노드입니다.2. 중위 탐색을 했을 때 루트를 기준으로 왼쪽에 나오는 노드들은 왼쪽 서브트리, 오른쪽에 나오는 노드들은 오른쪽 서브트리에 속한 노드들입니다. #include #include #include using namespace std; void postOrder(string preOrder, string inOrder) { //기저 사례 if (!preOrder.length()) return; //트리에 포함된 노드의 수 int num = preOrder.size(); const char ..

문제 링크입니다: https://www.acmicpc.net/problem/15805 전위 순회 탐색을 생각해보면 쉽게 풀 수 있는 문제였습니다.한번도 방문하지 않은 노드는 (해당 노드가 등장하기 전 노드)의 자식입니다. #include #include using namespace std; const int MAX = 200000 + 1; int A[MAX]; int parent[MAX]; set tree; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; for (int i = 0; i > A[i]; parent[A[0]] = -1; tree.insert(A[0]); for (int i = ..

문제 링크입니다: https://www.acmicpc.net/problem/2263 직접 트리를 그려본 다음에 유도를 해보는 것이 제일 적절한 해법인 것 같습니다. 후위 순회를 기준으로 생각해보면 맨 마지막에 위치한 노드가 해당 트리의 루트입니다.그리고 중위 순회를 기준으로 생각해보면 루트가 나오기 전까지는 왼쪽 부분트리이고 나온 후에는 오른쪽 부분트리입니다.따라서, 이 성질을 이용해서 재귀함수를 호출하면 AC를 받을 수 있습니다. #include using namespace std; const int MAX = 100000 + 1; int inOrder[MAX], postOrder[MAX]; int idx[MAX]; void preOrder(int inBegin, int inEnd, int postBe..

문제 링크입니다: https://www.acmicpc.net/problem/1991 자료구조 시간에 배운 트리 순회를 복습할 수 있는 문제였습니다. #include #include using namespace std; const int MAX = 26; vector tree[MAX]; //nodeNum, left? void preOrder(int node) { cout b >> c; //왼쪽 자식 if (b != '.') tree[a - 'A'].push_back({ b - 'A', true }); //오른쪽 자식 if (c != '.') tree[a - 'A'].push_back({ c - 'A', false }); } preOrder(0); cout

문제 링크입니다: https://algospot.com/judge/problem/read/TRAVERSAL 소스코드에 앞서서 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)의 Pseudo Code를 간단히 소개하겠습니다. 전위 순회if (currentNode){ Visit(currentNode); Preorder(currentNode->leftChild); Preorder(currentNode->rightChild); }중위 순회if (currentNode){ Inorder(currentNode->leftChild); Visit(currentNode); Inorder(currentNode->rightChild)..

문제 링크입니다: http://www.codewars.com/kata/fun-with-trees-is-perfect/train/cpp 개인적으로 별로 안 좋아하는 코드입니다.TreeNode를 구조체로 잡고 이진트리 클래스를 만들었다면 훨씬 간편하고 보기 좋은 코드로 작성할 수 있었겠지만 문제에서 저렇게 정의한 클래스를 가지고 문제를 풀라고 하니 어쩔 수 없었습니다. /*2^높이 - 1의 인덱스까지 모두 채워져있는 이진트리를 완전이진트리라고 한다.isPerfect 함수를 작성하시오*/#include #include using namespace std; int pow(int height){ int result = 1; for (int i = 0; i < height; i++) result *= 2; retu..