어흥

문제링크: [Preorder] www.hackerrank.com/challenges/tree-preorder-traversal/problem?h_r=internal-search Tree: Preorder Traversal | HackerRank Print the preorder traversal of a binary tree. www.hackerrank.com [Inorder] www.hackerrank.com/challenges/tree-inorder-traversal/problem?h_r=internal-search Tree: Inorder Traversal | HackerRank Print the inorder traversal of a binary tree. www.hackerrank.com [P..

문제 링크: www.hackerrank.com/challenges/is-binary-search-tree/problem Is This a Binary Search Tree? | HackerRank Given the root of a binary tree, you have to tell if it's a binary search tree. www.hackerrank.com 1.주의할 점 - BST의 조건에 대해 정확히 알고 있어야한다. 특정 Node를 기준으로 왼쪽의 Subtree들의 값은 특정노드의 값보다 전부 작아야하고, 오른쪽의 Subtree들은 특정노드의 값보다 전부 커야한다 2. 구현 1) [실패했던 방법] - 특정 Node를 기준으로 왼쪽에 tree가 있다면, 왼쪽 자식의 값과 현재 값을 비교 ..

문제링크: www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 1. 주의할 점 - 트리나 트라이에 대해서 알고 있어야 한다 - 사전순으로 출력해야한다(정렬된 무엇인가를 사용) 2. 구현 - Node 구조체를 만들어서 해당 Node의 Map을 생성하고, insert()와 print()의 기능을 하는 함수를 생성한다 - Node구조체 형태인 Root 노드를 처음에 만든다 - Insert() 함수는 입력받은 길을 저장하고 있는 V 벡터와 현재 개미굴의 ..

문제 링크: https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) �� www.acmicpc.net 1. 주의할 점 - DFS +DP를 이용하여 메모아이징을 사용해야 한다 2. 구현 - 모든 간선들의 정보를 V[] 배열에 담는다 - 입력 받은 Root를 기준으로 DFS()를 수행하며 메모아이징을 이용해서 해결한다. 또한, Visit[] 배열을 사용하여 해당 Node의 부모를 세지 않도록 한다 #include #inc..

문제 링크: https://www.acmicpc.net/problem/6416 6416번: 트리인가? 문제 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 �� www.acmicpc.net 1. 주의할 점 - 매 TC마다 Case를 1씩 증가시킨다 - 매 TC마다 벡터와 배열들을 초기화한다 - Root가 2개 이상 있는지, 없는지, 부모가 2개 이상인지, Root에서 모든 Node까지 도달 가능하지 전부 확인한다 - 0 0 또한 빈 트리로, 트리라고 출력해야 한다 2. 구현 - 입력받는 모든 Node들을 Set에 넣으며, 간선의 정보는 V[부모]에 자식에 대한 정보를 넣..

문제 링크: https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다. www.acmicpc.net 1. 주의할 점 - Node 구조체를 만들 줄 알아야한다. 2. 구현 - Node 구조체를 만든 이후 Nodes 배열을 생성한다. - 각 Node를 생성해준다 - 입력받은 순서에 따라 Node를 연결해준다 #include using namespace std; struct node { n..

문제 링크: https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 매겨져 있다고 생각한다) 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되 www.acmicpc.net 1. 주의할 점 - 모든 Node에 대해 돌릴 경우 N^2 -> 시간초과 발생 - 시작 Node를 기준으로 Leaf 까지..

문제 링크: https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는 지울 노드의 번호가 주어진다. www.acmicpc.net 1. 주의할 점 - For문을 최대한 덜 사용하도록 한다. - 배단 Vector를 통해 자식의 정보를 저장한다 - Boolean 배열을 사용하여 해당 Node가 삭제되었는지 확인한다 2. 구현 - 큐를 사용하여 지우려는 Node를 큐에 삽입하고 해당 Node의 Erased 배열값을 True로 설정한다. - 큐에서 Pop을 통해 얻은 N..