문제 링크 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 postorder(후위 순회, 왼쪽-오른쪽 -루트) - 항상 root가 마지막에 위치(*특징) - 트리의 특성상 root를 기준으로 왼쪽/오른쪽 서브트리가 나누어지게 때문에 postorder 통해 트리의 root 파악 가능 inodrer(중위 순회, 왼쪽-루트-오른쪽) - root를 기준으로 왼쪽/오른쪽 서브 트리가 나누어진다 - postorder로 구한 root 값으로 inorder의 왼쪽/오른쪽 서브 트..

문제링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제풀이 - 인접 리스트 사용해서 DFS 탐색 2번 수행 - 시간 복잡도 : O(V + E) 절차 1) 1번 루트 노드에서 가장 비용이 큰 리프(leaf)노드를 찾음 (= 지름에 해당하는 한점) 2) 찾은 리프 노드를 시작점으로 dfs 탐색을 한번 더 수행하여 구한 최대 cost가 트리의 지름이다 참고. 동일 문제 https://dev-ljw1126.tistory.co..

문제 링크 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 풀이 - 앞서 MST 문제 풀이하다가 '트리의 지름'에 대한 이론을 알게 되었고, 관련 문제 풀이함 '트리의 지름'에 대한 강의 영상을 찾아보니 초보 알고리즘이란다 (하하하.. 심플하긴하다) https://dev-ljw1126.tistory.com/369 [BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름) 문제 링크 http..

문제 링크 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제 풀이 - 첫째 줄 회사 직원 수 n, 최초의 칭찬 횟수 m (2 ≤ n, m ≤ 100,000) - 둘째 줄 직원 n명의 직속 상사(=부모 노드)가 주어짐, 최종적으로 1번이 사장(=Root)이다. - 다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000) 최대치 계산할 경우 - 직원 수(n) 1명에..

문제 링크 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 풀이 - 인접 리스트로 트리 정의 - 제거할 노드(REMOVE_NODE)를 인접 리스트 순회하면서 제거 - LEAF 노드 배열 값을 갱신하며 DFS 탐색 - 최종적으로 ROOT 노드의 있는 값을 출력하면 됨 - 시간 복잡도 : O(N) , (N

문제 링크 https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 문제 풀이 - (중요) 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라 함 - 입력 초기화할 때 이전 노드와 현 노드 차이가 1이 아닌 경우 부모 노드 인덱스(parentIdx)를 변경하여 PARENT 배열 정의 - PARENT 배열을 구한 후 선형 탐색 하여 O(N) 시간복잡도 가짐 TARGET 노드가 있을 때 TARGET ..

문제 링크 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 풀이 - 두 노드 간의 가장 가까운 공통 조상(Lowest Common Ancestor)을 찾음 - 각 노드의 부모 노드(PARENT)와 깊이(DEPTH) 를 구하고, 깊이의 차가 있을 경우 동일하게 맞춘 후 공통 조상 노드를 찾아 감 - 선형 탐색으로 풀이 하여 O(T * N) 시간복잡도 ( 2 ≤ N ≤ 10,000 ) LCA..

문제 링크 https://www.acmicpc.net/problem/20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N

문제 링크https://www.acmicpc.net/problem/15900 15900번: 나무 탈출평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게www.acmicpc.net문제 풀이- 노드 N (1 ~ 500,000) 이때 1번 노드가 정점 노드로 주어짐- 간선의 수 N - 1 - LEAF 노드의 DEPTH를 구하고 그 합이 홀수인 경우 Yes, 짝수인 경우 No로 답을 구하면 됨- 시간복잡도 : O(V + E) = O(500,000 + 499,999)  DEPTH 배열을 따로 구할 필요 없이 전역 변수에 LEAF 노드의..

문제 링크 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 풀이 - 정적 클래스를 정의하여 주어진 입력값을 이진 검색 트리(전위 순회) 방식으로 정의 - 이전에 풀었던 트리 순회와 동일하게 재귀 함수 사용하여 후위 순회 구할 수 있도록 함 - 노드의 최대 개수는 10^4 이고, 각 노드 별로 최대 2번 재귀를 호출할 때 O(2 * 10^4) 시간 복잡도 소요 참고 https://dev-ljw1126.tistory.com/248..

문제 링크 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 풀이 전위 순회(preodrer) : 부모 > 왼쪽 > 오른쪽 중위 순회(inorder) : 왼쪽 > 부모 > 오른쪽 후위 순회(postorder) : 왼쪽 > 오른쪽 > 부모 - 알파벳 26개 그리고 알파벳 노드별 자식 2개(왼쪽, 오른쪽) - 전위/중위/후위 순회로 인해 총 3번 로직 수행 - 한 노드당 최대 2번 재귀 호출을 수행하므로 O(26 * 2 * 3) 시간..