Featured image of post [Algorithm] cpp 백준 12918번: 정리정돈
Algorithm Geometry

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

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

Featured image of post [Algorithm] cpp 백준 12963번: 달리기
Algorithm Graph

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

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

Featured image of post [Algorithm] cpp 백준 13323번: BOJ 수열 1 - Slope Trick
Algorithm Greedy

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

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

Featured image of post [Algorithm] cpp 백준 13329번: Meteor Shower
Algorithm Geometry

[Algorithm] cpp 백준 13329번: Meteor Shower

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

Featured image of post [Algorithm] cpp 백준 13510번: 트리와 쿼리 1
Algorithm Tree

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

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

Featured image of post [Algorithm] cpp 백준 13545번: 수열과 쿼리 0
Algorithm Data Structures

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

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

Featured image of post [Algorithm] cpp 백준 13546번: 수열과 쿼리 4 - Mo+제곱근분할
Algorithm Sqrt Decomposition

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

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

Featured image of post [Algorithm] cpp 백준 13569번: Rounding - 표 합계 보존 반올림
Algorithm Graph

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

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

Featured image of post [Algorithm] cpp 백준 13576번: Prefix와 Suffix
Algorithm String

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

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

Featured image of post [Algorithm] cpp 백준 13896번: Sky Tax
Algorithm Tree

[Algorithm] cpp 백준 13896번: Sky Tax

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

Featured image of post [Algorithm] cpp 백준 13974번: 파일 합치기 2
Algorithm Dynamic Programming

[Algorithm] cpp 백준 13974번: 파일 합치기 2

연속한 파일만 합칠 수 있을 때 최소 비용을 구하는 구간 DP 문제입니다. dp[i][j]=min(dp[i][k]+dp[k+1][j])+sum(i..j)에 크누스 최적화를 적용해 O(N^2)로 해결합니다. 누적합으로 구간합을 O(1)로 계산하며 64비트 정수, 메모리 사용에 유의합니다.

Featured image of post [Algorithm] cpp 백준 14001번 : Mole Tunnels
Algorithm Graph/Tree

[Algorithm] cpp 백준 14001번 : Mole Tunnels

NEERC 2016 ‘Mole Tunnels’(BOJ 14001) 문제를 트리 위 최소 비용 흐름을 직접 쓰지 않고 잔여 네트워크를 모사해 O(m log n)으로 해결하는 방법을 정리합니다. 경로 비용 갱신, DP 구성, 구현 팁과 전체 코드 포함.

Featured image of post [Algorithm] cpp 백준 14166번: 로봇 소 무리 (Robotic Cow Herd)
Algorithm Greedy

[Algorithm] cpp 백준 14166번: 로봇 소 무리 (Robotic Cow Herd)

K개의 로봇을 서로 다른 구성으로 최저 비용에 제작하는 문제. 각 위치 최소값 합을 기반으로 추가비용 배열을 구성해 임계 추가비용을 이분탐색하고, fracturing search(가지치기 열거)로 개수를 세어 K개 최소 합을 얻는다. 구현·복잡도·실수 포인트까지 정리.