트리 (26) 썸네일형 리스트형 트리의 부모 찾기 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net visited 배열을 사용하며 dfs 돌리면 끝. dfs(1)로 시작한다. ans 배열에 트리 노드의 부모를 저장 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 #include #include using namespace std; vector an.. 트리의 기본 트리는 사이클이 없는 그래프이다! 1. Union Find 트리의 부모만 저장하는 방식 2. Heap, Segment Tree 완전 이진 트리의 경우에는 배열로 표현이 가능 부모의 노드가 x인 경우 자식의 노드는 2 * x, 2 * x + 1로 나타내면 된다. 프리오더 -> 자식의 값을 구할 때 부모의 값을 이 인오더 -> 이진트리에서만 가 의미 X 포스트오더 (가장 중요!!!) -> 부모의 값을 구할 때 자식의 값을 이용 왼쪽 -> 오른쪽 -> 부모 이전 1 2 3 4 다음