개인사

리뷰 https://www.acmicpc.net/problem/17435문제 분류만 보았을 땐 이게 왜 LCA지? 라는 느낌이 들었지만, 친구에게 설명을 듣고 나서 이해가 되었다. 전역 변수MAX_N : 주어지는 함수 내 원소의 최대 개수를 저장할 정수형 상수 변수LOG : 비트단위로 부모를 탐색할때 사용할 정수형 상수 변수m, q : 주어진 원소의 개수를 저장할 변수 m, 쿼리의 개수를 저장할 변수 qn, x : 함수를 반복할 회수를 저장할 변수 n, 함수의 초깃값에 넣을 원소의 번호 xpar : 각 원소의 2^n번째 부모 원소를 저장할 2차원 배열, MAX_N * LOG 크기로 저장한다. 함수1. preprocessvoid preprocess() par배열을 초기화 하기 위한 함수각 원소의 par배열..

리뷰 두 노드에서 출발해 LCA에 달할때 까지 도로 중 가장 짧은 거리와 가장 긴 거리를 구하는 문제https://www.acmicpc.net/problem/3176 문제 풀이도시의 최대 개수는 10만이므로 MAX_N을 10만 1로, LOG를 MAX_N을 LOG2를 취한 값 보다 크게 20으로 설정한다.도시의 개수 n과 쿼리의 개수 k를 전역 변수로 설정한다.부모 도시를 담을 배열par, 짧은 거리 및 긴 거리를 저장할 배열 mn, mx을 MAX_N * LOG 크기로 설정한다.깊이를 담을 배열dep, 유니온 파인드용 배열 nodes를 MAX_N크기로 설저어한다.인접 리스트 정보를 담을 구조체 Link를 만들어 주고 Link타입 벡터 links를 MAX_N크기로 설정한다.n값을 입력 받고 1~n 도시를 각..

리뷰 치열한 전투의 흔적이 보이십니까?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 함수를 통해 찾아준 뒤 ..