Algorithm Data Structures

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

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

Algorithm Segment Tree

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

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

Algorithm String

[Algorithm] cpp 백준 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] cpp 백준 15974번: 공룡 발자국

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

Algorithm Dynamic Programming

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

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

Algorithm Graph

[Algorithm] cpp 백준 16074번: Mountaineers - Minimax MST·LCA

격자 지도에서 출발→도착까지 필요한 최소 ‘최고 고도’(minimax 경로)를 구합니다. Kruskal+유니온파인드로 MST를 구성하고 LCA 이진 리프팅으로 경로 최대 가중치를 O(logV)로 질의합니다. 올바름 근거·코너 케이스 점검을 포함해 제출 안정성을 높입니다.

Algorithm Data Structures

[Algorithm] cpp 백준 16124번: 나는 행복합니다 - 자릿수 치환 세그먼트 트리

최대 1e6자리 비밀번호에서 [i,j] 구간의 특정 숫자(from)를 다른 숫자(to)로 치환하고, 부분 문자열을 998244353으로 나눈 값을 출력합니다. 각 노드에 자릿값 가중 합을 숫자별로 분해해 저장하고, 0..9→0..9 치환을 지연 전파로 합성하는 Lazy 세그먼트 트리로 쿼리를 O(10·logN)에 처리합니다.

Algorithm Tree

[Algorithm] cpp 백준 16181번: Coloring Roads (도로 색칠하기)

트리에서 루트까지 경로를 특정 색으로 덮어씌우고, 정확히 m개의 도로가 칠해진 색의 개수를 즉시 질의하는 문제를 HLD와 구간 대입(lazy) 세그먼트 트리로 해결합니다. 균일 구간만 색 전파하여 per-color 카운트와 히스토그램을 O(log^2 N)에 유지합니다.

Algorithm Graph

[Algorithm] cpp 백준 16367번: TV Show Game - 2-SAT 풀이

TV Show Game은 참가자마다 제출한 세 개의 (램프, 색) 예측 중 최소 두 개가 참이 되도록 램프 색을 조정할 수 있는지 판정하는 문제입니다. (a∨b)∧(a∨c)∧(b∨c) 제약을 2‑SAT로 모델링해 암시 그래프와 SCC로 가능 여부를 확인하고 해를 O(k+n)에 구성합니다.

Algorithm Graph

[Algorithm] cpp 백준 16583번: Boomerangs - DFS 간선 페어링

정점 기준으로 미소모 간선을 둘씩 묶어 부메랑 <u,v,w>를 최대화하는 문제. 비재귀 DFS로 즉시 페어링하고 1개는 부모 간선과 결합해 전역 최적 보장. O(N+M), 다중 컴포넌트·트리/사이클 안전.

Algorithm Data Structures

[Algorithm] cpp 백준 16670번: King Kog의 접견실 - 세그먼트 트리

기사들의 방문(도착 시각 t, 소요 d)이 실시간으로 추가/취소되는 상태에서 공주가 시각 t에 도착했을 때의 대기 시간을 즉시 구합니다. 누적 처리량 P(t)와 선형 시간 t를 결합한 백로그 공식 W(t) = (P(t) - t) - min_{u≤t}(P(u) - u) 를 활용하고, 좌표 압축 + 지연 전파 세그먼트 트리로 접수/취소는 suffix 가산, 질의는 점/구간 최소를 O(log N)에 처리해 q ≤ 3e5를 안정적으로 통과합니다.

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 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]의 최댓값은 블록 분할과 재귀적 프리픽스 최대치로 계산합니다. 엣지 케이스와 정당성 근거까지 압축 정리.