Algorithm Geometry

[Algorithm] cpp 백준 10254번: 고속도로 - 회전하는 캘리퍼스

최대 20만 점에서 유클리드 최장거리 쌍을 찾습니다. 단조사슬로 볼록 껍질을 O(n log n)에 구하고, 회전하는 캘리퍼스로 지름을 O(h) 탐색합니다. 제곱거리·64비트·빠른 입출력 적용.

Algorithm String

[Algorithm] cpp 백준 10538번: 빅 픽쳐 - 2D 롤링 해시로 O(HW) 매칭

흑백 격자에서 작은 그림이 걸작 내에 나타나는 모든 위치를 계산합니다. 행/열 분리 2차원 롤링 해시와 이중 해싱으로 충돌을 낮추고 O(HW) 시간에 서브매트릭스 매칭을 수행하여 제한 조건을 안정적으로 만족합니다.

Algorithm Fenwick Tree

[Algorithm] cpp 백준 11012번: Egg - 2D 직사각형 쿼리 스위핑+BIT

n개의 점과 m개의 직사각형 [l,r]×[b,t]가 주어질 때, 각 직사각형 안의 점 개수를 모두 합한 값을 구한다. x를 기준으로 오프라인 스위핑을 수행하고, y는 좌표 압축 후 펜윅 트리(Fenwick Tree)로 누적 빈도를 관리한다. 쿼리는 (r,+1),(l-1,−1) 이벤트로 분해해 포함-배제를 구현하여 총합을 O((n+m) log n)에 계산한다. 64비트 누적, 경계(b=0) 처리, 중복 좌표 대응을 주의한다.

Algorithm Math

[Algorithm] cpp 백준 11385번: 씽크스몰 - NTT+CRT 다항식 곱셈

NTT 친화 소수 3개에서 다항식 곱셈을 수행하고 CRT로 계수를 복원해 모든 계수의 XOR을 계산합니다. N, M ≤ 1e6의 대용량 입력을 O(n log n) 시간과 선형 메모리로 안정 처리하며, 오버플로는 __int128로 방지합니다.

Algorithm Graph

[Algorithm] cpp 백준 11405번: 책 구매하기 - 최소 비용 최대 유량

수요·공급 합이 같은 이분 네트워크에서 총 배송비를 최소화한다. S→서점(B_i), 서점→사람(C_ij), 사람→T(A_j)로 모델링하고 잠재치+Dijkstra 기반 최소비용최대유량으로 계산한다. 잔여그래프·역간선 점검 포함.

Algorithm Graph

[Algorithm] cpp 백준 11407번: 책 구매하기 3

사람–서점 이분 그래프에 수요·공급·구매제한을 용량/비용으로 모델링하고, 잠재함수 기반 최단경로 반복(MCMF)로 최대 유량과 최소 비용을 동시에 달성합니다. 모델링, 정당성, 구현 포인트와 복잡도를 일목요연하게 정리했습니다.

Algorithm Graph

[Algorithm] cpp 백준 11408번: 열혈강호 5 - MCMF 최소비용 최대매칭

이 문제는 직원-일 이분 그래프에서 임금 비용을 최소화하며 가능한 한 많은 일을 배정하는 과제입니다. 최소 비용 최대 유량(MCMF)로 모델링하여 Dijkstra+잠재치(Johnson)로 음수 없는 보정 비용을 사용, 유량 1씩 확장하며 비용 합을 최소화합니다. 제약(N,M≤400, 임금≤10^4)에 맞춰 O(F·E·logV)로 안정적으로 통과합니다.

Algorithm Dynamic Programming

[Algorithm] cpp 백준 1144번: 싼 비용 - Connection Profile DP

N,M ≤ 9 격자에서 상하좌우로 연결된 하나의 칸 집합을 골라 비용 합의 최솟값을 찾습니다. 연결 프로파일 DP로 상태를 라벨링·정규화해 압축하고, 고립 검사와 병합 전이로 올바름과 효율을 보장합니다. 시간·공간 복잡도, 구현 포인트, 코너 케이스까지 정리합니다.

Algorithm Game Theory

[Algorithm] cpp 백준 11717번: Wall Making Game

H×W 격자에서 점을 하나 고르면 그 행·열 전체가 벽이 되어 보드가 네 개의 직사각형 서브게임으로 분할됩니다. 표시 칸(X)은 선택 불가이지만 벽으로 변할 수 있습니다. 스프라그-그런디 정리로 각 서브직사각형의 그런디 수를 XOR해 승자를 판단하며, 메모이제이션을 적용한 사각형 분해 DP로 최적 풀이를 구현합니다.

Algorithm Tree DP

[Algorithm] cpp 백준 11808번: 마리오와 사악한 키노피오

루트에서 시작·종료하며 루트 제외 K개 성을 주어진 순서로 방문할 때, 키노피오가 최악의 선택을 하면 총 이동 시간의 최댓값을 구한다. 2·∑w·min(s,K+1−s)를 트리 DP와 배낭 합치기로 계산하고 왕복·루트 제외를 반영한다.

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)를 이용해 현재 각도에서 최전면 선분만 표시합니다. 표시된 선분 수를 제외해 완전히 가려진 다각형 개수를 계산하는 풀이입니다.