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

[Algorithm] C++ 백준 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] C++ 백준 13329번: Meteor Shower
Algorithm Geometry

[Algorithm] C++ 백준 13329번: Meteor Shower

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

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

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

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

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

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

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

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

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

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

Featured image of post [Algorithm] C++ 백준 13547번: 수열과 쿼리 5 - Mo 알고리즘
Algorithm Mo's Algorithm

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

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