📚 문제 https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 🔍 아이디어 만약 현재 노드가 유사 중위 순회의 끝이라면 유사 순위를 종료한다는 부분을 잘못 이해해서 여러 번 틀렸던 문제였습니다. 이 구문은 현재 노드가 중위 순회가 끝났다면 다시 올라가지 않아도 된다는 것을 의미합니다. 즉 왼쪽으로 가는 경우는 반드시 루트로 다시 올라와야 하지만 오른쪽의 경우는 중위순회가 끝난 상태라면 다시 올라오지 않아도 됩니다. (중위 순회 : 왼쪽 자식 -> ..
📚 문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 🔍 아이디어 공통 조상을 찾는 문제입니다. 각 노드의 깊이를 먼저 BFS, DFS를 이용하여 계산합니다. (이때 부모 노드도 함께 지정해줍니다, parents 배열) 이후에 a,b 노드의 공통 조상을 찾는 경우 a의 깊이, b의 깊이를 비교하여 두 노드의 깊이가 동일할 때까지 부모로 이동하며 올라옵니다 두 노드의 깊이가 같아졌으면 두 노드를 함께 부모로 노드로 올리는것을 반복합니다...
📚 문제 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 🔍 아이디어 mst를 활용하여 풀이하였습니다. *(다른 분들과 풀이가 달라 맞는 풀이인지 확신이 들지 않습니다. 참고 부탁드립니다) 가장 힘이 드는경우는 가장 많은 경사로(같은 길이 나오지 않기때문)를 이용하는 경우라고 생각하였습니다 따라서 먼저 경사로를 이용하는 경우의 모든 경로를 연결합니다. 이때 연결된 경사로의 개수의 제곱이 점수가 됩니다. 가장 ..
