Algorithm Segment Tree

[Algorithm] C++ 백준 8177번: Ice Skates - 최대연속합 세그트리

사이즈 r인 사람은 [r, r+d]의 스케이트를 신을 수 있을 때, 매 이벤트마다 모든 사람에게 신발을 재분배할 수 있는지 판정합니다. p[i]-k 배열의 최대연속합이 d*k를 초과하는지 세그먼트 트리로 O(log N)에 확인하는 풀이를 정리합니다.

Algorithm Data Structures

[Algorithm] C++ 백준 8987번: 수족관 3 - 카르테시안 트리

수평 바닥을 구간 높이 배열로 모델링한 뒤, 최소 높이 기준으로 구간을 분할하는 카르테시안 트리를 구성해 각 노드 직사각형 넓이를 계산합니다. 분할로 얻는 이득을 우선순위 큐에 넣어 상위 K개를 합하면 최대 배수량을 얻습니다. 구현은 O(N)~O(N log N)으로 안정적이며, 64-bit 정수 오버플로와 구간 경계 처리, 입력 형식 차이 등을 면밀히 점검합니다.

Algorithm String

[Algorithm] C++ 백준 9248번: Suffix Array - 접미사 배열과 LCP O(n log n)

접미사 배열을 O(n log n) 더블링으로 구축하고, LCP 배열은 카사이 알고리즘으로 O(n)에 계산합니다. 안정 정렬·랭크 갱신·경계 처리와 엣지 케이스 점검까지 담은 실전 풀이.

Algorithm String

[Algorithm] C++ 백준 9250번: 문자열 집합 판별

아호-코라식 자동자로 집합 S 패턴을 통합하고, 질의 문자열을 선형 주행하며 실패 링크·out 전이로 부분 문자열 매칭을 즉시 감지합니다. 전이 초기화·루트 귀속·빠른 입출력을 점검해 1초·256MB를 안정 통과하는 O(총 길이) 풀이입니다.

Algorithm String

[Algorithm] C++/Python 백준 11479번: 서로 다른 부분 문자열의 개수

문자열 S의 서로 다른 부분 문자열 개수를 효율적으로 구합니다. 접미사 배열+LCP(카사이)로 n(n+1)/2−ΣLCP를 계산하거나 접미사 자동자(SAM)로 상태 길이 차 합을 이용해 O(n)에 해결합니다. 경계·중복 처리와 구현 포인트를 정리했습니다.

Algorithm Dynamic Programming

[Algorithm] C++/Python 백준 12735번: Boat

한강 북안 N개 학교가 [ai, bi] 범위의 보트를 낼 수 있고, 선택된 각 학교의 보트 수가 이전에 선택된 모든 더 작은 번호 학교의 보트 수보다 항상 큰 경우의 수를 구합니다. 좌표압축과 구간 DP, 모듈러 역원으로 O(N^3) 카운팅을 구현합니다.

Algorithm Geometry

[Algorithm] C++/Python 백준 12771번: Oil

수평 선분들로 모델링된 유전을 한 번의 직선 시추로 통과하며 만나는 선분 길이 합(유전 너비 합)을 최대로 만드는 문제입니다. 각 선분의 양 끝점을 기준으로 기울기 구간을 스위프하여 포함 가중치를 갱신하고, O(n^2 log n)으로 최대 추출량을 구합니다.

Algorithm Game-Theory

[Algorithm] C++/Python 백준 13034번: 다각형 게임 - Sprague–Grundy DP

볼록 다각형에서 선분을 서로 교차시키지 않고 기존 선분의 끝점과도 겹치지 않게 잇는 게임을 스프라그–그런디 정리로 모델링합니다. 한 번의 선택이 다각형을 두 부분으로 분할한다는 불변식에서 g[n]=mex{g[a]⊕g[n-2-a]}를 세우고, O(N^2) DP로 승패(1/2)를 판정합니다. 엣지/실수 포인트 점검 포함.

Algorithm Graph

[Algorithm] C++/Python 백준 13161번: 분단의 슬픔 - s-t 최소 컷

UCPC 2016 C ‘분단의 슬픔’을 s-t 최소 컷으로 푼 풀이. w[i,j]는 양방향 간선, 강제 A/B는 소스·싱크 무한 용량으로 고정. Dinic으로 최소 슬픔 합을 구하고 잔여 그래프에서 A/B를 복원한다. 모델링 근거와 컷 복원, 구현 포인트, 복잡도와 코너 케이스 점검까지 정리. C++·Python 코드 포함.

[Algorithm] C++/Python 백준 13309번: 트리 - 경로 질의와 간선 제거

트리에서 두 정점의 연결 여부를 빠르게 판별하고, 결과에 따라 부모-자식 간선을 제거하는 온라인 질의를 처리합니다. HLD와 Fenwick Tree로 경로를 O(log N)에 분해해 2e5도 안정적으로 통과합니다.