Algorithm Dynamic-Programming

[Algorithm] C++ 백준 14177번: 티떱랜드 - 어색함 최소화 DP(DnC)

N명을 K개 연속 구간으로 나눠 구간 내 사람쌍 어색함 합을 최소화. 2D 누적합으로 cost(l,r) O(1) 계산, dp[g][i]=min(dp[g-1][j]+cost) 전이를 분할정복 최적화로 O(KN log N) 해결.

Algorithm Graph

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

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

Algorithm Brute Force

[Algorithm] C++ 백준 14560번: Communism - 합차 제한 MITM

세 사람에게 N≤30개의 일을 배분할 때 아드와 래리 보수 합의 차이가 D를 넘지 않도록 하는 가짓수를 구한다. 전수탐색 대신 절반 분할, 남은 절대합 기반 가지치기, 정렬·이분탐색으로 O(3^(N/2))에 해결.

Algorithm Divide and Conquer

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

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

Algorithm DP

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

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

Algorithm Data Structures

[Algorithm] C++ 백준 14897번: 서로 다른 수와 쿼리 1

배열에서 구간 [l, r]의 서로 다른 값 개수를 빠르게 구하는 문제입니다. r 오름차순 오프라인 처리와 각 값의 마지막 등장 위치만 활성화하는 펜윅 트리 기법으로 쿼리를 O(log N)에 해결하고, 좌표 압축으로 값 범위를 정규화합니다.

Algorithm Segment Tree

[Algorithm] C++ 백준 14898번: 서로 다른 수와 쿼리 2

좌표압축과 영속 세그먼트 트리로 각 r 버전을 구성해 [l,r] 서로 다른 원소 수를 O(log N)에 답합니다. 온라인 입력은 누적 정답으로 처리하여 5초·1024MB 제한을 안정적으로 통과합니다.

Algorithm String

[Algorithm] C++ 백준 14959번: Slot Machines - KMP로 최소 주기 O(n)

관측 수열 T[1..n]이 시점 k 이후 주기 p로 반복될 때, k+p 최소(동률 시 p 최소)인 (k,p)를 구한다. 역수열에 KMP 접두사함수를 적용해 접미사 최소 주기 p=L-pi를 O(n)에 계산하고 최적 해를 도출한다.

Algorithm Geometry

[Algorithm] C++ 백준 15974번: 공룡 발자국

발뒤꿈치 기준 각도 정렬과 ccw로 기하 제약을 선형화한 뒤, DP(발가락/골 상태 전이)를 슬라이딩 윈도우로 최적화하여 O(N^2 log N)에 최대 발가락 수의 발자국을 찾고, 역추적으로 꼭짓점 좌표를 출력하는 풀이입니다.

Algorithm Dynamic-Programming

[Algorithm] C++ 백준 15977번: 조화로운 행렬 - 3D LIS/CDQ

KOI 2018 ‘조화로운 행렬’ 풀이. 열-부분행렬의 등수행렬이 모든 행에서 동일해지는 최대 열 길이를 구한다. M=2는 1행 정렬 순서에서 2행 등수의 LIS, M=3은 CDQ 분할정복+펜윅 트리로 3차원 LIS를 계산한다. 증명과 엣지 케이스, 구현 포인트를 함께 정리했다.