개인사

리뷰 치열한 전투의 흔적이 보이십니까?LCA의 기본기가 있다면 쉽게 풀 수 있을 거라 생각했는데, 문제가 친절하지 않아 고생한 문제https://www.acmicpc.net/problem/13511 문제 풀이input 함수에서 n값을 받고, 각 노드간의 간선 n - 1개를 입력 받는다.solution함수에서 dfs 함수와 pre_process 함수를 돌려주어 각 노드의 부모, 깊이, 비용값을 구해주었다.dfs 함수에서는 각 함수의 깊이 및 루트 노드로부터의 비용, 자신의 바로 위 부모를 구해 각 배열에 저장해줬다.pre_process 함수에서는 각 노드의 2^i 번째 상위 부모를 찾아 부모 배열을 마저 초기화 해주었다.query 함수에서 m값을 받고, 입력된 m개의 쿼리를 처리해 주었다.쿼리의 인덱스가 ..

리뷰 LCA 문제의 상위 호환버전, 노드의 개수가 2배로 많아졌고, 쿼리의 개수도 증가하였다.시간을 좀 아껴보려고 LOG의 크기를 줄여주었더니 OutofBounds 에러가 출력되었다, LOG값을 높혀주니 AChttps://www.acmicpc.net/problem/11438 문제 풀이n값을 입력 받고, n - 1개의 간선을 tree 벡터 배열에 양방향 간선으로 저장해 준다.루트 노드는 항상 1이기에 1부터 dfs 함수를 통해 모든 노드에 자기 자신의 깊이와 바로 윗 조상을 초기화 해준다.pre_process 함수를 통해 각 노드에 변수 LOG의 값 즉 2^20개의 부모 노드를 탐색하여 저장해 준다. (메모제이션)m개의 쿼리를 받고, 각 쿼리마다 두 노드의 최소 공통 조상을 lca 함수를 통해 찾아준 뒤 ..