Algorithm Math

[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 Tree

[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 Tree

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

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

Algorithm Tree

[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 Tree

[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 + 압축 그래프 위상정렬 기반입니다.

Algorithm DP

[Algorithm] cpp 백준 3319번: 전령들

트리의 각 도시에서 수도까지 메시지를 가장 빨리 전달하는 최소 시간을 구하는 문제입니다. 도시 i는 출발 준비 시간 S_i와 1km당 이동 시간 V_i를 가지며, 유일한 최단 경로를 따라 이동 중 중간 도시에서 다른 전령에게 넘길 수 있습니다. dp[u]를 루트까지의 거리 dist[u]를 이용해 dp[u] = S_u + V_u·dist[u] + min_{조상 x}(dp[x] − V_u·dist[x])로 정리하고, 조상 집합에 대한 직선 최소값 질의를 처리하기 위해 Li Chao Tree(선형함수 컨벡스 헐 트릭)를 트리 경로에 영속적으로 유지(퍼시스턴스)하여 각 정점에서 O(log C)에 답합니다. 64비트 정수 및 곱셈 시 128비트 캐스팅으로 오버플로를 방지합니다.

Algorithm Graph Flow

[Algorithm] cpp 백준 3611번: 팀의 난이도

팀의 난이도(같은 팀에서 일을 못하는 쌍/인원)를 최대화하는 문제는 최대밀도부분그래프와 동치입니다. r에 대해 |E(S)|-r|S|를 최대화하는 파라메트릭 최소절단을 구성하고 이분 탐색으로 r*를 찾은 뒤, 절단의 S측에서 최적 팀을 복원합니다. n≤100, m≤1000에서 안전합니다.

Algorithm Graph

[Algorithm] cpp 백준 4001번: 미노타우르스 미궁

좌·우수법(Left/Right-hand rule)으로 정의되는 두 개의 표준 경로를 계산하고, 2차원 누적합으로 직사각형 내부 경로/장애물 포함 여부를 O(1)에 판정합니다. 각 좌표별로 ‘막히는 최소 정사각형 크기’와 ‘설치 가능한 최대 정사각형 크기’를 각각 이분 탐색해 교집합이 존재하면 정답 후보로 갱신하여, 가장 작은 변의 길이와 위치를 찾습니다.

Algorithm Greedy Interval Scheduling

[Algorithm] cpp 백준 4012번: 컨벤션 센터 - 사전순 최소 해 선택

회의 구간을 최대 개수로 선택하면서 사전순(lexicographical)으로 가장 이른 해를 출력하는 문제. 시작 시각 기준 정렬, 선행 회의의 이진 점프(sparse table)로 f(l,r)를 O(log n)에 계산하고, 구간 경계 map을 유지해 포함 여부를 O(log n)에 증명·선택한다. 전체 O(n log n).