Algorithm Game Theory

[Algorithm] cpp 백준 16877번: 핌버

핌버는 여러 돌 더미에서 한 턴에 한 더미를 골라 피보나치 수 만큼만 제거하는 님 게임 변형입니다. 피보나치 이동 집합으로 각 크기 x의 Grundy 수를 DP로 선계산하고, 모든 더미의 Grundy XOR로 승패를 판별합니다. 시간 O(U·F+N), 메모리 O(U).

Algorithm Data Structures

[Algorithm] cpp 백준 16903번: 수열과 쿼리 20 - XOR 트라이

배열 A(초기에 0 포함)에 대해 삽입·삭제·최대 XOR 질의를 처리합니다. 비트 기반 이진 트라이에 카운트를 유지해 중복과 삭제를 안전히 지원하고, 쿼리 시 각 비트에서 상반된 가지를 우선 선택해 최댓값을 구성합니다. 각 연산은 O(30)로 1초, 512MB 제한에 안전합니다.

Algorithm Segment Tree

[Algorithm] cpp 백준 16977번: 히스토그램에서 가장 큰 직사각형과 쿼리 - PBS+세그트리

히스토그램의 구간 [l,r]에서 너비 w가 고정일 때 최대 넓이는 길이 w 윈도우의 최솟값을 최대화하는 문제입니다. 높이 좌표압축과 임계값 단조성을 이용해 병렬 이분탐색을 수행하고, 세그먼트 트리(연속 1의 최댓값)로 검증하여 각 쿼리를 빠르게 해결합니다. 엣지 케이스와 실수 포인트까지 점검합니다.

Algorithm Number Theory

[Algorithm] cpp 백준 17104번: 골드바흐 파티션 2

FFT 컨볼루션으로 모든 짝수 N(2<N≤1e6)의 골드바흐 파티션 개수를 한 번에 전처리하고 각 쿼리를 O(1)에 답합니다. 에라토스테네스의 체, llround 반올림, p=q 대칭 보정, 0.5초/512MB 제약 대응 구현.

[Algorithm] cpp 백준 17134번: 르모앙의 추측

홀수 N을 홀수 소수 p와 짝수 세미소수 2q의 합으로 표현하는 가짓수를 구한다. 에라토스테네스의 체와 소수·2×소수 배열의 FFT 컨볼루션으로 전체 범위를 전처리하고 각 질의를 O(1)로 답한다.

Algorithm Data Structures

[Algorithm] cpp 백준 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별

구간 [L,R]에 1..R-L+1 등차수열을 더하는 쿼리를 처리합니다. 점 X에 더해지는 합은 Σ(X−L+1)=cnt·(X+1)−ΣL로 표현되므로, 두 개의 펜윅 트리(BIT)로 [L,R]에 +1, +L을 각각 범위 업데이트하고 점 질의로 합을 계산해 O((N+Q)logN)에 해결합니다.

[Algorithm] cpp 백준 17429번: 국제 메시 기구

트리 경로·서브트리에 더하기/곱하기(아핀) 갱신과 합 질의. HLD로 경로 분할, lazy 세그트리로 2^32 모듈러 유지하며 O(log^2 N) 처리. 구현 포인트와 엣지 케이스 체크까지 정리.

Algorithm Dynamic Programming

[Algorithm] cpp 백준 17526번: Star Trek

선형 행성 경로에서 환승 준비시간과 선박 속도를 고려해 1→n 최소 이동 시간을 구한다. dp[j]=min(dp[i]+p_i+s_i·(D[j]-D[i]))를 직선 최소 질의로 바꾸고 Li Chao Tree로 O(n log X)로 최적화한 정답과 증명·엣지케이스를 정리.

Algorithm Greedy

[Algorithm] cpp 백준 17613번: 점프 - 구간 최대 점프넘버

KOI 2019 고등부 2번 ‘점프’를 O(log N)으로 해결합니다. 1→2→4… 두 배 점프와 재시작 규칙을 이용해 모든 N을 메르센 구간으로 분해하고, [x,y]의 최댓값은 블록 분할과 재귀적 프리픽스 최대치로 계산합니다. 엣지 케이스와 정당성 근거까지 압축 정리.

[Algorithm] cpp 백준 1763번: 트리 색칠 - 비율 그리디

부모 선행 제약 아래 비용 C[i]·F[i]를 최소화하기 위해, 누적가중치/누적크기 비율이 최대인 정점을 고르고 가장 가까운 미방문 조상으로 병합하는 그리디를 적용합니다. 교차곱 비교와 경로 압축으로 정확·빠르게 구현합니다.

[Algorithm] cpp 백준 18227번: 성대나라의 물탱크

루트 C에서 시작하는 트리에서 "A 도시에 물 채우기"는 루트→A 경로의 각 정점 v에 깊이(v)+1 리터를 더합니다. 따라서 임의의 정점 v의 물의 양은 서브트리(v)에서 발생한 갱신 횟수 × (깊이(v)+1)로 환원됩니다. 오일러 투어로 트리를 평탄화하고 펜윅 트리(BIT)로 서브트리 구간의 갱신·질의를 처리해 O((N+Q)logN)에 해결합니다. 경계 입력과 64-bit 오버플로를 주의합니다.

Algorithm Geometry

[Algorithm] cpp 백준 2261번: 가장 가까운 두 점

평면 상 N개의 점에서 가장 가까운 두 점의 제곱거리를 구합니다. x좌표로 정렬해 분할정복으로 좌·우 구간을 해결하고, y정렬 병합과 좁은 스트립에서 dy 제약으로 후보만 비교해 O(N log N)에 도달합니다. 64비트 안전, 안정 병합, dy 기반 조기 중단 등 구현 디테일까지 점검합니다.

Algorithm Dynamic Programming

[Algorithm] cpp 백준 2419번: 사수아탕 - 구간 DP

시간당 1씩 감소하는 사탕 바구니를 0에서 출발해 최대 섭취량을 구한다. 위치 정렬 후 0을 포함한 구간을 좌우로 확장하는 O(n^3) 구간 DP로 도착시간 합을 최소화해 K*m−Σt를 극대화한다.

Algorithm Graph Tree

[Algorithm] cpp 백준 24272번: 루트 노드가 많은 트리일수록 좋은 트리이다

유일 경로 트리의 간선 방향을 제어하며 ‘모든 정점에 도달 가능한 루트’의 수를 유지하는 문제입니다. Euler tour로 서브트리를 구간화하고, child→parent 제약의 교집합과 parent→child 제약의 합집합을 각각 multiset과 세그먼트 트리로 관리하여 매 쿼리 O(log N)에 정답을 계산합니다. 엣지 케이스(교집합 공집합, 전역 인터벌, 무방향 전환)까지 안정적으로 처리합니다.

Algorithm Data Structures

[Algorithm] cpp 백준 2912번: 백설공주와 난쟁이 - 세그트리+후보검증

세그먼트 트리로 Boyer–Moore 다수결(majority) 후보를 구간 병합으로 구하고, 색상별 위치 배열에 대한 이분탐색으로 실제 빈도를 검증합니다. 전처리 O(N), 질의 O(log N)로 제한을 만족합니다.

Algorithm Dynamic Tree

[Algorithm] cpp 백준 2927번: 남극 탐험

LCT(링크-컷 트리)로 동적 연결과 경로 합을 처리하는 풀이. bridge로 다른 컴포넌트만 연결, penguins로 노드 값 갱신, excursion으로 경로 합 질의. Splay 기반 access/makeroot로 O(log N) 보장, 엣지 케이스 및 올바름 근거 포함.

Algorithm Geometry

[Algorithm] cpp 백준 31397번: 반 나누기 (Hard)

볼록다각형에서 둘레가 같은 두 조각을 만들기 위해 둘레 절반 간격의 두 점을 연결하고, 신발끈 누적합과 경계 호길이 파라미터화로 부분 넓이를 빠르게 계산하여 이분탐색으로 넓이 절반을 만족하는 절단점을 찾는 풀이.

[Algorithm] cpp 백준 31603번: 트리 퀴즈

정렬 키를 (x, LCA, y) 사전순으로 분해한다. 임계 라벨 t까지 F_x(t)=|{y: LCA(x,y)≤t}|를 오일러 투어 구간에 이벤트를 얹은 펜윅으로 일괄 집계하고, 이분으로 최소 L을 찾은 뒤 영속 세그먼트 트리에서 그룹 L 내 y의 k번째를 선택한다. 4초/1GB 제약 대응.

Algorithm Graph

[Algorithm] cpp 백준 3295번: 단방향 링크 네트워크 - 최대 매칭

단방향 링크 네트워크를 링과 선형 배열로 분해할 때의 최대 가치는 선택된 간선 수와 동일합니다. 각 정점의 진입·진출 차수를 최대 1로 제한하는 간선 선택 문제를 좌·우 파티션으로 분리한 이분 매칭으로 모델링하고, Hopcroft–Karp 알고리즘으로 O(√V·E)에 해결합니다. 구현 포인트와 코너 케이스까지 정리했습니다.

Algorithm Graph

[Algorithm] cpp 백준 3311번: Traffic - SCC 압축과 DAG 구간 전파

섬 내부 도로망은 선분 도로가 교차하지 않는 평면 그래프이므로, SCC 압축 DAG에서 각 컴포넌트가 도달할 수 있는 동쪽 경계 정점 집합은 y좌표 기준 연속 구간이 됩니다. 이를 이용해 동쪽 경계 정점(서쪽에서 실제로 도달 가능한 것만)을 y 오름차순으로 인덱싱하고, 자식 구간을 부모로 병합하는 역위상 전파로 각 서쪽 정점의 답(서쪽 정점에서 도달 가능한 동쪽 정점 수)을 O(n+m)에 계산합니다. 구현은 반복형 Kosaraju + 압축 그래프 위상정렬 기반입니다.