LCA (최소공통조상) 알고리즘 완벽 가이드
LCA (Lowest Common Ancestor)
LCA(최소공통조상)는 트리에서 두 정점의 가장 가까운 공통 조상을 찾는 문제이다. 트리 관련 알고리즘에서 가장基础的인 개념 중 하나이다.
1. 브루트 포스 방식
가장 간단한 접근법은 직접 위로 올라가며 찾는 것이다. 먼저 각 정점의 깊이(depth)와 부모 정보(fa)를 전처리한다.
알고리즘:
두 정점 u, v 중 더 깊은 정점을 찾는다.
...
7월 17일 22:27에 게시됨
NOIP 2024 시뮬레이션 경연 문제 분석 및 구현 가이드
철도 2 (Railway 2)
트리 구조에서 모든 노드 쌍 사이의 거리 함수 $f(i,j)$의 총합을 구하는 문제입니다. 이 문제의 핵심은 특정 노드에서 출발할 때 트리의 지름(Diameter) 끝점 중 하나로 향하는 경로가 최적의 해를 포함한다는 점입니다.
트리의 지름을 구한 뒤, 두 끝점을 기준으로 각 노드까지의 거리를 계산하여 정렬합니다. 이를 통해 각 노드별 기여도를 계산하여 ...
7월 13일 22:29에 게시됨
트리 체인 분할을 활용한 경로 및 서브트리 쿼리 처리
트리 체인 분할 개요
트리 체인 분할(Heavy Path Decomposition)은 트리 구조에서 효율적인 쿼리 처리를 위한 고급 자료구조 기법이다. 이 기법은 다음 네 가지 핵심 연산을 지원한다:
두 노드 x에서 y까지의 최단 경로상의 모든 노드에 값을 더한다
두 노드 x에서 y까지의 최단 경로상의 모든 노드 값의 합을 구한다
노드 x를 루트로 하는 서브트리의 모든 노드에 값을 ...
7월 10일 17:56에 게시됨
AtCoder ABC368 풀이: A~F번 문제 분석
A - Cut
문제 요약
길이 n인 수열에서 마지막 k개 원소를 앞으로 이동시킨 결과를 출력한다.
핵심 아이디어
배열을 회전시키는 기초적인 구현 문제이다. n-k 인덱스부터 끝까지의 원소를 먼저 출력한 뒤, 나머지 원소를 순서대로 출력하면 된다.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nu ...
6월 30일 23:02에 게시됨
Linux tree 명령어 활용법: 디렉터리 구조 시각화하기
디렉터리 구조를 계층적으로 확인해야 할 때 tree 명령어는 매우 유용한 도구입니다. 파일 시스템의 폴더와 파일을 나무 형태로 표현하여 복잡한 중첩 구조를 한눈에 파악할 수 있게 해줍니다.
핵심 옵션 정리
옵션기능 설명
-a숨김 파일 포함 모든 항목 표시
-d디렉터리만 출력
-L 숫자탐색 깊이 제한
-I 패턴특정 패턴 제외
-P 패턴특정 패턴만 포함
-f전체 경로 ...
6월 19일 17:18에 게시됨
그래프, 트리,链表 자료구조 완벽 가이드
기본 개념 및 전제 지식
1. 유니온-파인드 (Disjoint Set Union)
유니온-파인드 자료구조는 서로소 집합을 관리하는 데 사용되는 효율적인 알고리즘입니다. 주로 최소 신장 트리, 사이클 检测, 집합 합치기 등의 문제에 활용됩니다.
핵심 연산:
find: 특정 원소의 집합 대표자(ROOT)를 찾습니다. 경로 압축 기법으로 성능을 최적화합니다.
merge: 두 집합을 하나의 집 ...
5월 21일 00:46에 게시됨