Algorithm Tree

[Algorithm] cpp 백준 11932번: 트리와 K번째 수 - PST+LCA

정점 값 좌표압축 뒤 루트→정점 경로마다 영속 세그먼트 트리를 누적 구축하고, LCA를 이용해 경로 빈도를 포함-배제로 합산해 K번째 수를 찾습니다. 세그먼트 트리에서 왼/오 자식으로 이진 하향 탐색해 순위 k를 복원하며, 전체 시간/공간은 O((N+M)logN)/O(NlogN) 수준입니다.

Algorithm Tree

[Algorithm] cpp 백준 11933번: 공장들

트리 위 두 회사 공장 집합 A, B 사이의 최소 거리를 구하는 문제입니다. LCA 전처리 후 질의마다 A∪B와 인접 LCA들로 버추얼 트리를 만들고, 두 번의 DP로 각 정점의 A까지/ B까지 최단거리를 구해 min(dA+dB)로 답합니다. O((|A|+|B|)logN)으로 6초 제한을 안정 통과합니다.

Algorithm Graph

[Algorithm] cpp 백준 1210번: 마피아 - 정점 분할 최소 컷

마피아의 이동을 막기 위해 톨게이트를 최소 비용으로 점거하는 문제를 정점 가중치 s-t 최소 컷으로 모델링합니다. 각 정점을 in/out으로 분할하고 내부 간선에 비용을 두어 최대 유량=최소 컷으로 풀이하며, 시작/도착 정점 점거 허용까지 반영합니다.

Algorithm Graph Dynamic Programming

[Algorithm] cpp 백준 12766번: 지사 배정 - D&C DP + 다익스트라

메시지를 HQ 경유로 순차 전달할 때 비용은 지사별 HQ 왕복거리 합에 (그룹 크기−1)을 곱한 합으로 환원된다. HQ 기준 다익스트라로 w를 구해 정렬·접두사합 후 분할정복 DP로 s구간 최적 분할하여 최소값을 구한다.

Algorithm Data Structures

[Algorithm] cpp 백준 12858번: Range GCD - 차분+세그트리

구간 덧셈과 구간 GCD 질의를 함께 처리합니다. 차분 배열과 세그먼트 트리로 d[l+1..r]의 GCD를 유지하고, 펜윅트리로 a[l]을 복원해 정답을 gcd(|a[l]|, G)로 구해 O(logN)에 해결합니다. 경계·절댓값·64-bit 주의.

Algorithm Geometry

[Algorithm] cpp 백준 12918번: 정리정돈

헝가리안 알고리즘으로 대칭 쌍 매칭을 최소화해 이동 거리 합의 최솟값을 구합니다. 비용을 √((xi+xj)^2+(yi−yj)^2)로 정의해 할당 최적화 후 2로 나누어 답을 얻습니다. 증명·엣지·복잡도·C++ 구현 포함

Algorithm Graph

[Algorithm] cpp 백준 12963번: 달리기

도로 i의 용량이 3^i인 무향 그래프에서 0→N-1로 도달 가능한 최대 인원을 구한다. 3의 거듭제곱 가중치의 유일성으로 최소 s-t 컷이 단일해가 되며, 간선을 인덱스 내림차순으로 확인하며 DSU로 s와 t를 잇는 간선만 더해 합을 구해 1e9+7로 출력한다.

Algorithm Dynamic Programming

[Algorithm] cpp 백준 13261번: 탈옥 - DP 분할정복 최적화

연속한 L칸을 G개의 구간으로 분할해 각 구간 비용을 (길이×구간합)으로 정의하고 총합을 최소화합니다. dp[g][r]=min(dp[g-1][k]+cost(k+1,r))를 이용해 분할정복 최적화로 O(G·L·logL)에 해결하며, 누적합으로 O(1) 구간비용·경계·64비트 오버플로를 꼼꼼히 점검합니다.

Algorithm Greedy

[Algorithm] cpp 백준 13323번: BOJ 수열 1 - Slope Trick

수열 B가 엄격히 증가하도록 하면서 |B_i−A_i|의 합을 최소화하는 문제. A_i−i로 변환해 비내림 수열 적합 문제로 줄이고, 최대 힙으로 중간값을 유지하는 slope trick을 적용해 O(N log N)로 해결한다. 32비트 범위, 경계·반례까지 점검한다.

Algorithm Geometry

[Algorithm] cpp 백준 13329번: Meteor Shower

각 다각형을 최소각·최대각 꼭짓점으로 압축한 선분으로 바꾼 뒤, 각도 스위핑과 ccw 기반 비교(set)를 이용해 현재 각도에서 최전면 선분만 표시합니다. 표시된 선분 수를 제외해 완전히 가려진 다각형 개수를 계산하는 풀이입니다.

Algorithm Tree

[Algorithm] cpp 백준 13510번: 트리와 쿼리 1

트리에서 간선 가중치 갱신과 경로 최댓값 질의를 처리하는 최적 풀이를 정리합니다. Heavy-Light Decomposition과 세그먼트 트리를 결합해 각 쿼리를 O(log N)에 해결하고, 구현 포인트·엣지 케이스·정당성·복잡도를 점검합니다.

Algorithm Data Structures

[Algorithm] cpp 백준 13537번: 수열과 쿼리 1 - 오프라인 BIT

값과 쿼리의 k를 내림차순으로 정렬해 A[i] > k인 위치만 Fenwick 트리에 활성화하고, 각 질의 [i,j,k]는 구간 합으로 k보다 큰 원소 개수를 구합니다. 전체 O((N+M)logN)로 해결하며, 1-기반 인덱스·경계·오버플로·빠른 입출력 등 실수 포인트를 점검합니다.

Algorithm Data Structures

[Algorithm] cpp 백준 13538번: XOR 쿼리 - 퍼시스턴트 트라이

비어있는 배열에 대한 삽입/삭제(되돌리기) 버전을 유지하는 퍼시스턴트 이진 트라이로, 구간 내 최대 XOR, x 이하 개수, k번째 수를 모두 O(log V)로 처리합니다. 50만 쿼리를 2초 내에 안정적으로 해결하는 구현/정당성/복잡도까지 정리했습니다.

Algorithm Data Structures

[Algorithm] cpp 백준 13544번: 수열과 쿼리 3 - Merge Sort Tree

정렬된 구간 리스트를 저장한 Merge Sort Tree로 구간 [i,j]에서 k보다 큰 원소 개수를 온라인으로 계산합니다. 각 노드에서 upper_bound로 개수만 더해 O(log^2N) 질의, O(NlogN) 빌드. XOR last_ans 변형을 안전히 처리하는 구현 포인트와 엣지 케이스까지 정리합니다.

Algorithm Data Structures

[Algorithm] cpp 백준 13545번: 수열과 쿼리 0

1과 -1로 이루어진 수열에서 구간 [i,j]마다 합이 0인 최장 연속 부분수열 길이를 구한다. 동일 누적합 쌍의 최대 거리를 구간 내에서 찾는 문제로 환원하고, Mo 알고리즘+좌표압축+deque와 버킷 카운팅으로 최대 길이를 O(1) 가깝게 갱신해 O((N+M)√N)로 해결한다.

Algorithm Sqrt Decomposition

[Algorithm] cpp 백준 13546번: 수열과 쿼리 4 - Mo+제곱근분할

구간 [L,R]에서 같은 값의 두 위치 간 최대 거리(max |x−y|, A[x]=A[y])를 묻는 질의를 Mo 알고리즘으로 처리합니다. 값별 위치 데크와 거리 빈도(√ 분할)를 유지해 추가/제거 O(1)로 갱신하고, 블록 카운팅으로 최대 거리를 즉시 찾습니다. 경계 이동 순서·인덱스 변환·거리 갱신 누락 실수를 방지하는 체크리스트까지 정리했습니다.

Algorithm Mo's Algorithm

[Algorithm] cpp 백준 13547번: 수열과 쿼리 5 - Mo 알고리즘

Mo 알고리즘으로 구간 [L,R]의 서로 다른 값 개수를 오프라인으로 처리합니다. 좌우 포인터 이동 시 빈도와 distinct를 유지하고, 좌표압축으로 메모리를 줄입니다. 정렬 O(Q log Q), 전체 O((N+Q)√N), 경계 이동 순서·0-index 변환·freq 0↔1 갱신 실수 방지까지 정리합니다.

Algorithm Graph

[Algorithm] cpp 백준 13569번: Rounding - 표 합계 보존 반올림

소수 첫째 자리로 기록된 표의 각 원소·행합·열합을 정수로 내림/올림하되, 행과 열의 합이 동시에 보존되도록 결정하는 문제입니다. 하한·상한 제약을 갖는 순환 유량으로 모델링해 정수 해를 보장하고, Dinic으로 구현합니다. 엣지 케이스, 정당성, 복잡도, 구현 포인트까지 간결히 정리했습니다.

Algorithm String

[Algorithm] cpp 백준 13576번: Prefix와 Suffix

문자열의 접두사이자 접미사인 모든 경계(보더)를 찾고, 각 길이가 부분 문자열로 등장하는 횟수를 구합니다. KMP 접두사함수(π)로 경계 사슬을 추출하고, π 누적 분포로 등장수를 계산하여 l 오름차순으로 출력합니다. O(n) 구현과 정당성·엣지케이스를 정리했습니다.

Algorithm Tree

[Algorithm] cpp 백준 13896번: Sky Tax

트리에서 수도(루트)가 동적으로 바뀔 때 도시 X가 처리해야 할 세금 도시 수를 빠르게 구한다. 오일러 투어로 서브트리 크기를 전처리하고, 이진 승진(LCA) 계통 정보를 사용해 X가 수도의 조상인지 판정하여 경우를 분기해 O((N+Q)logN)으로 답한다.