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 백준 13547번: 수열과 쿼리 5 - Mo 알고리즘
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 갱신 실수 방지까지 정리합니다.

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개 최소 합을 얻는다. 구현·복잡도·실수 포인트까지 정리.

Featured image of post [Algorithm] cpp 백준 1420번: 학교 가지마!
Algorithm Graph

[Algorithm] cpp 백준 1420번: 학교 가지마!

격자에서 K→H 경로를 막기 위해 최소 몇 칸을 벽으로 바꿀지 구한다. 각 칸을 in/out으로 분할해 정점 컷을 최대유량으로 환원하고 '.'=1·K/H=INF·인접=INF로 모델링한다. Dinic으로 계산하며 K-H가 인접하면 -1을 출력한다.

Featured image of post [Algorithm] cpp 백준 14636번: Money for Nothing - Monge DnC
Algorithm Divide and Conquer

[Algorithm] cpp 백준 14636번: Money for Nothing - Monge DnC

생산자/소비자 후보를 정렬·중복 제거해 비지배 전처리로 파레토 경계를 만들고, 원점 변환된 점집합의 Monge 구조를 이용해 분할정복 최적화로 (e−d)*(q−p) 최대 이익을 계산합니다. 계약 불가 케이스는 0 처리, i128로 오버플로를 방지하며 엣지 케이스 점검을 포함합니다.

Featured image of post [Algorithm] cpp 백준 14870번: 조개 줍기
Algorithm DP

[Algorithm] cpp 백준 14870번: 조개 줍기

N×N 격자에서 각 칸의 조개 최대 개수가 주어질 때, 위/왼쪽으로만 이동하는 경로 최대합 DP를 모든 시작 칸에 대해 합산하고, 단위(±1) 갱신마다 영향 범위를 ‘계단’으로 추적해 행별 Fenwick(범위가산·점질의)으로 O(N^2 log N) 시간에 합을 갱신하는 풀이를 정리합니다. 올바름 근거와 엣지 케이스 점검까지 포함했습니다.