코딩성장스토리

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름은 가중치가 들어간 그래프(트리)를 탐색해서 가장 큰 값을 구하는 거다. 그러기 위해선 가장 위에 있는 루트 값을 알아내야 한다. 그리고 그 루트에서 가장 큰 값을 구하면 그게 가장 큰 값이 된다. 즉 루트를 알아내기위한 탐색 1번과 루트를 기준으로 가장 큰 값을 구하는 탐색 2번이면 구해진다. #include #include #include #include #inclu..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 이번에는 노드의 부모노드 번호를 구하는 문제이다. 나는 이 문제를 DFS로 풀었고 탐색을 진행하면서 각 노드에 해당하는 부모를 부모노드 배열에 넣었다. 그래서 한번의 탐색으로 각 노드의 부모를 저장한 배열을 구할 수 있다. #include #include #include #include using namespace std; #pragma warning(disable : 4996) vector d[100020]; //각 인덱스 별로 연결된 노드 배열 bool c..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이 문제는 트리 순회를 정석 문제이다. 전위순회, 중위순회,후위순회 를 구하는 문제이고 나는 배열 A[i][0]을 i의 왼쪽노드 A[i][1]을 i의 오른쪽 노드로 정하고 시작하였다. #include #include #include using namespace std; #pragma warning(disable : 4996) char a[26][2]; void preorder(char ..

트리 :사이클이 없는 그래프 정점의 개수 :v 간선의 개수: v-1 루트 있는 트리 1번이 루트다 → 부모가 없음 1은 2의 부모 ,2는 1의 자식 2는 4의 부모 ,4는 2의 자식 3의 자식 6,7 4,5,6,7 →단말 정점 깊이: 루트에서부터 거리 (ex)루트 1의 깊이를 0이라 하면 4의 깊이는 2) 이진 트리: 자식을 최대 2개만 가지고 있는 트리 '트리의 표현: 배열 a[i][0]:i의 왼쪽 노드 ,a[i][1]:i의 오른쪽 노드 로 구현 가능 트리의 순회(이진 트리) 1.프리오더 -전위 순회 -노드 방문 -왼족 자식 노드를 루트로 하는 서브트리 프리오더 -오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더 2.인오더 -중위 순회 -왼족 자식 노드를 루트로 하는 서브트리 인오더 -노드 방문 -오..