개인사

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

리뷰쉽게 생각했다가 푸는데 한시간은 걸린 문제 생각지 못한 까다로운 조건이 많다. 이래서 설계를 하고 풀어야 하는데.. 문제 풀이n개의 줄에 노드간 상관 관계를 받아준다. -1이 주어졌을땐 해당 인덱스를 루트 인덱스로 따로 저장해 주자인접 리스트 형태가 완료 되었다면 삭제할 값을 받아오고 해당 인덱스의 벡터를 날려주자루트 인덱스부터 dfs를 시작한다. 이때 루트가 비어있다면 리턴을 해주자 (루트가 삭제된 케이스)현재 노드의 자식을 순회하고, 만약 삭제된 노드를 만났는데 현재 노드의 크기가 1일 경우 cnt를 1개 올린다.자식의 리스트가 비어있다면 cnt를 올리고 다음 요소를 순회한다.둘 다 해당되지 않으면 해당 인덱스를 dfs 해준다. dfs가 전부 종료되면 cnt를 출력해 준다. 참고 사항참고해야할 조..

개요그래프정점과 정점사이의 상관관계를 나타내는 자료구조 노드와 간선으로 이루어져 있다.1. 그래프의 방향그래프는 방향이 있는 그래프와 방향이 없는 그래프로 나뉘어 진다. (양방향과 단방향)2. 가중치각 노드간 간선에 가중치가 있을 수 있다. (거리 등) 3. 트리그래프의 한 종류로 LEVEL이 설정되어 있는 그래프이다. LEVEL 0에 ROOT 노드가 있으며, 하위 노드는 자식이 된다. 반대로 자식 입장에서 ROOT 노드는 부모 노드이며, 자식간의 관계는 형제 노드가 된다.트리의 특징방향 그래프만 존재루트 노드가 한개만 존재계층 형식으로 비순환 그래프4. 인접 행렬위 트리 노드를 인접 행렬로 표현하면 아래와 같이 표현할 수 있다.노드12345101001200110300000400000500000 출발지 ..