Algorithm BOJ Game-Theory Bitwise

[Algorithm] C++ 백준 16895번: 님 게임 3

전체 돌더미의 XOR(님합)이 0이면 선공은 필패다. 아니면 어떤 더미 pi를 pi^X로 줄여 님합을 0으로 만드는 모든 첫 수가 승리 수이며, 이를 O(N)으로 센다.

Algorithm BOJ Math Geometry Green's Theorem

[Algorithm] C++ 백준 17441번: 파리채 만들기

단순다각형 내부에서 두 점을 균일·독립으로 뽑을 때 E[|P-Q|^2]를 구한다. 이를 2(E[|P|^2]-|E[P]|^2)로 바꾸고 면적·무게중심·∫x^2,∫y^2를 변 합 공식으로 O(N)에 계산한다.

Algorithm BOJ Data Structure Fenwick Tree Order Statistics

[Algorithm] C++ 백준 1777번: 순열복원

Inversion sequence(각 i 뒤에 나오며 i보다 작은 수의 개수)로부터 Fenwick Tree(BIT)에서 k번째 빈 칸을 찾아 큰 수부터 배치해 순열을 복원한다. O(N log N)으로 N≤100000을 처리한다.

Algorithm BOJ Game-Theory Greedy

[Algorithm] C++ 백준 17965번: Absolute Game

각자 자신의 배열에서 하나만 남길 때까지 번갈아 삭제한다. 게임 값은 max_x min_y |x-y|로 환원되며, b를 정렬한 뒤 각 a의 최근접 거리 최댓값을 lower_bound로 계산한다.

Algorithm BOJ Math FFT Convolution Geometry

[Algorithm] C++ 백준 20176번: Needle

세 장벽(위·중·아래) 구멍 3점이 일직선이면 중간 x는 위·아래 x의 평균이다. 위/아래 좌표를 0/1 배열로 만든 뒤 FFT 컨볼루션으로 합=2xm 쌍을 세어 O(R log R)에 통로 개수를 구한다.

Algorithm BOJ Tree LCA

[Algorithm] C++ 백준 20506번: Kaisar - 생존

트리에서 모든 순서쌍 (x,y)의 LCA를 모아 정렬한 뒤 홀수/짝수 위치 합을 구한다. 각 정점이 LCA가 되는 쌍의 개수를 서브트리 크기 제곱으로 O(N)에 계산한다.

Algorithm BOJ Math Sorting

[Algorithm] C++ 백준 22878번: 간단한 문제

점 (p_i,q_i) 쌍에 대해 모든 i,j의 min(|p_i-p_j|,|q_i-q_j|) 합을 구한다. max(|dx|,|dy|)=(|dx+dy|+|dx-dy|)/2를 이용해 p,q,p+q,p-q를 정렬·누적합으로 처리한다.

Algorithm BOJ Math Implementation

[Algorithm] C++ 백준 25201번: 보드 뒤집기 게임

2×2 블록 뒤집기는 각 행·열에서 색이 바뀌는 칸 수의 홀짝을 보존한다. 현재/목표 빨간 칸의 대칭차를 만들고 행·열별 등장 횟수가 모두 짝수인지 확인하면 O(N+M)으로 YES/NO를 판정한다.

Algorithm BOJ DP Greedy Sorting

[Algorithm] C++ 백준 2586번: 소방차

펌프/소방차 좌표를 정렬한 뒤 depth 버킷으로 분해하고, 각 버킷에서 인접 매칭과 1개 제외 DP로 최소 호스 길이 합을 O((P+F) log (P+F))에 계산한다.

Algorithm BOJ Graph Functional Graph

[Algorithm] C++ 백준 2988번: 아보가드로

3×N 표에서 열을 삭제한 뒤 각 행을 정렬했을 때 열별 값이 일치하도록 만든다. 첫 행이 순열임을 이용해 값→값 함수 두 개를 만들고, 두 함수의 순환(cycle)만 남기는 폐포를 BFS로 구해 삭제 최소를 계산한다.