개인사

리뷰 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배열..

리뷰 https://www.acmicpc.net/problem/15480LCA의 심화 문제, 루트가 매번 바뀔때마다의 처리하는 아이디어에 배우게 된 문제였다. 전역 변수MAX_N : 정점의 최대 개수를 저장할 정수형 상수 변수LOG : DP에서 2의 N승으로 빠르게 탐색하기 위해 사용할 정수형 상수 변수n, m : 문제에서 주어진 정점의 개수 n, 쿼리의 개수 mdepth : 각 노드의 초기 깊이를 저장할 정수형 배열, 크기는 MAX_N으로 초기화parents : 각 노드의 부모 정보를 저장해 둔 정수형 배열, 크기는 MAX_N * LOG로 초기화lst : 각 정점간의 간선을 인접리스트로 저장할 정수형 벡터, 크기는 MAX_N으로 초기화 함수1. dfsvoid dfs(int node, int par, i..

리뷰 두 노드에서 출발해 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 도시를 각..

리뷰 그래프의 정보가 주어지고 두 노드간의 거리를 구하는 문제, 루트 노드가 1이 고정이 아니여서 직접 구해주어야 한다.LCA는 개념만 잘 잡는다면 응용 문제에 적용하는 방법이 어렵지 않은 것 같다.https://www.acmicpc.net/problem/1761 문제 풀이main 함수에 init, ds, pre_process, query 네개의 함수를 순차적으로 실행시켜 문제를 풀었다.init 함수에서 n값을 받고 n - 1개의 간선 정보를 tree 벡터 배열에 저장한 뒤 Union 작업을 수행해 준다.1부터 n까지의 노드를 탐색 한 후 자기 자신을 value로 갖는 노드를 찾아 root로 저장한다.root 부터 dfs 함수를 통해 각 노드의 깊이와, 루트 노드로 부터의 거리, 자기 자신의 바로 윗 조..

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

리뷰  문제 풀이테스트 케이스를 입력 받고, 해당 테스트 케이스 만큼 while문을 돌려준다.각 테스트 케이스 마다 n, root, tree, parent정보를 초기화 해준다.유니온 파인드용 노드 배열을 노드의 1 ~ n 노드까지 자기 자신을 값으로 갖게끔 인덱스를 설정해 준다.이후 n - 1개의 간선을 입력 받고, tree벡터 배열에 양방향 간선으로 추가, b를 a의 자식으로 유니온 해준다.1부터 n까지 노드를 탐색해 자기 자신을 value로 갖고있는 노드를 찾고 root로 할당해 준다.dfs함수를를 root 부터 돌려 각 자신의 바로 위 부모를 구해준다.preprocess 함수를 통해 그 위의 부모들까지 초기화를 해준다.비교할 노드 두개를 입력 받고 lca 함수의 매개변수로 전달해준 뒤 리턴값을 출력..

리뷰새로운 알고리즘인 LCA를 배우게 되었다, 로직이 매우 복잡했지만 세그먼트 트리처럼 외워서 쓴다면 괜찮을 것 같다. 문제 풀이nodes를 최대 노드의 개수로, LOG를 최대 노드의 개수를 log2를 취한 수보다 크게 설정해 준다.tree벡터 배열에 인접 리스트를 저장하고, depth에 각 노드의 깊이, parent에 각 노드의 부모 정보를 저장한다.dfs 함수를 통해 인접리스트를 사용하여 자신의 바로 윗 부모와 depth를 알 수 있다.process 함수를 통해 모든 노드의 조상에 대해 탐색이 가능하다, 조상이 없을 경우 -1m개의 쿼리문을 받아와 u와 v의 최소 공통 부모를 lca 함수를 통해 구해준 후 출력해 준다. 참고 사항자세한 내용은 정답 코드의 주석 참고  정답 코드#include#incl..