LCA(Lowest Common Ancestor)는 최소 공통 조상이라고도 불리며트리에서 두 노드 u와 v를 모두 자손으로 갖는 노드 중 가장 아래에 있는 노드를 구하는 기법입니다.기본적으로 아래의 과정을 진행하여야 합니다. 1. u보다 v가 더 깊이(depth)가 더 깊을 경우 v를 부모노드로 올린다.2. 이제 u와 v의 깊이가 같아졌을 경우 u와 v를 같이 부모노드로 올린다.3. 2번 과정을 u와 v가 같은 노드를 가리킬 때까지 진행한다. 하나하나 부모노드로 올려 진행하였을 때 최악의 경우에는 O(N)의 시간복잡도로 LCA를 구하게 되는데앞서 배운 DP와 비트마스크 기법을 이용하여정점의 2^k번째 부모를 부분문제로 저장하여 O(lgN)만에 구할 수 있습니다.이는 트리 상에서 두 정점의 거리를 빠르게 ..
구간트리(Segment Tree)는 저장된 자료들을 적당히 전처리하여특정 구간에 대한 질의를 빠르게 대답할 수 있도록 하게 하는 기법입니다.보통 원소의 값 변경이 자주 일어나며 구간 원소의 합, 곱, 최댓값, 최솟값을 반복적으로 구해야 할 때 사용합니다.구간에 대한 질의를 답할 때의 시간복잡도는 O(lgN), 원소 하나의 값이 변경 되었을 때의 시간복잡도는 O(lgN)이며길이가 K인 구간의 원소의 값이 변경 되었을 경우의 시간복잡도는 O(KlgN)입니다.이를 O(lgN)만에 하게 하기 위하여 레이지 프로퍼게이션(Lazy Propagation)기법을 사용합니다.또한 앞서 배운 비트마스크 기법을 응용하여 짧고 간단하게 구간 합을 구할 수 있는 팬윅트리(Fenwick Tree)를 이용하여 구간 합을 응용하여 ..
비트마스크(Bitmask)는 정수의 이진수 표현을 자료구조로 쓰는 기법입니다.집합의 크기가 작은 집합을 나타내기 위해 많이 사용되며정수형 변수 하나로 이들을 나타낼 수 있어 함수의 인자로 넘겨주거나배열의 인덱스로 사용하여 접근이 가능하기에 익숙해지면 유용한 기법입니다.완전탐색, DP를 사용하는 문제를 풀 때 원하는 자료를 간단하게 표현하기 위해,또는 추후 트리파트의 구간트리에서 배우게 될 팬윅트리에서도 이 기법을 응용하여 사용합니다.여러가지 테크닉이 존재하기에 많이 사용해보시는 것이 좋습니다. 기본 문제 11723번: 집합2098번: 외판원 순회1102번: 발전소