Algorithm Data Structures

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

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

Algorithm String

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

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

Algorithm String

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

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

Algorithm String

[Algorithm] cpp-python 백준 11479번: 서로 다른 부분 문자열의 개수

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

Algorithm Dynamic Programming

[Algorithm] cpp-python 백준 12735번: Boat

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

Algorithm Geometry

[Algorithm] cpp-python 백준 12771번: Oil

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

Algorithm Game Theory

[Algorithm] cpp-python 백준 13034번: 다각형 게임 - Sprague–Grundy DP

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

Algorithm Graph

[Algorithm] cpp-python 백준 13161번: 분단의 슬픔 - s-t 최소 컷

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

Algorithm Tree

[Algorithm] cpp-python 백준 13309번: 트리 - 경로 질의와 간선 제거

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

Algorithm Dynamic Programming

[Algorithm] cpp-python 백준 14869번: 요리 강좌 - DP, 슬라이딩 윈도우 최적화

연속 수강 길이 S~E, 학원 변경 비용 T, 불허용 학원 제약을 동시에 만족하는 최소비용을 구합니다. prefix sum과 단조 큐로 블록 DP를 슬라이딩 윈도우 최적화해 O(NM)로 해결, 정당성과 엣지 케이스 점검까지 담았습니다.

Algorithm Greedy

[Algorithm] cpp-python 백준 15337번: 관광열차 좌석 배치 - s1/s2 계산

정책-1(승객 자유 좌석 선택)·정책-2(운영자 일괄 배정)에서 필요한 최소 좌석 s1·s2 계산. s2는 라인 스위핑으로 최대 동시 탑승, s1은 n−endPrefix[a]−startSuffix[b]의 최댓값. [a,b) 경계·누적/접미합·빠른 I/O, 엣지·실수 포인트 점검.

Algorithm String

[Algorithm] cpp-python 백준 15338번: String Puzzle - 루트 압축 점프

길이 n(≤1e9) 비공개 문자열에 위치 고정 힌트와 구간 복사 힌트가 주어진다. 각 구간을 왼쪽으로 d만큼 당기는 함수로 모델링하고 p에서 반복 적용해 유일한 루트를 찾는다. 루트→문자 맵으로 쿼리를 O(log b)로 결정한다.

Algorithm Greedy

[Algorithm] cpp-python 백준 15773번: Touch The Sky

고도 h≤L에서만 풍선을 불 수 있고 한 번 불 때마다 D만큼 상승한다. 최대 몇 개의 풍선을 순서대로 사용할 수 있는지 구한다. E=L+D 오름차순 정렬 + 최대 힙으로 누적 D를 관리하며, 누적이 현재 E를 초과하면 가장 큰 D를 제거한다. 교환 논법으로 그리디 정당화, O(N log N), 64비트 정수 주의.

Algorithm Tree

[Algorithm] cpp-python 백준 16404번: 주식회사 승범이네 - 서브트리 갱신·점 질의

회사 트리에서 직원 i와 그 하위 전체의 이익/손해를 일괄 반영하고 단일 직원의 잔액을 즉시 조회하는 문제입니다. 오일러 투어로 서브트리를 구간화하고 펜윅 트리 차분으로 구간 덧셈·점 질의를 O(log N)에 처리해 1초 제한을 안정적으로 통과합니다.

Algorithm Graph

[Algorithm] cpp-python 백준 16901번: XOR MST

XOR 가중치 완전그래프의 MST를 비트 최상위부터 그룹을 나누는 분할정복과 이분 트라이로 계산합니다. 각 레벨에서 교차 간선 비용을 2^b + 하위 최소 XOR로 구해 전체 비용을 누적합니다. 구현 포인트와 코너 케이스, C++·Python 코드와 정당성 근거까지 정리했습니다.

Algorithm Number Theory

[Algorithm] cpp-python 백준 16998번: Mod World

p, q, n이 주어질 때 (p·i mod q)의 합을 i=1..n까지 구하는 문제입니다. 유클리드 호제법 기반 floor_sum과 주기성(서로소 시 잔여 클래스 순열)을 이용해 O(log q)로 풀며, 정당성과 경계 사례를 함께 점검합니다.

Algorithm Greedy

[Algorithm] cpp-python 백준 17169번: Eat Economically - 그리디 O(N log N)

2N개의 메뉴에서 점심·저녁 가격이 다를 때 i쌍(점심 i, 저녁 i)을 중복 없이 골라 총 비용을 최소화하는 문제. 잔여 그래프 관찰을 바탕으로 매 단계 3가지 증분 케이스만 비교하는 O(N log N) 그리디로 모든 i의 정답을 한 번에 계산한다.

Algorithm Graph

[Algorithm] cpp-python 백준 17399번: 트리의 외심

세 정점의 외심은 세 정점까지의 거리가 같으면서 그 거리가 최소가 되는 정점입니다. LCA·깊이로 세 경로의 교점 S를 찾고, 두 작은 팔 길이의 동일성과 큰 팔과의 짝수 차이를 이용해 존재·위치를 판정합니다. BFS+Binary Lifting로 O((N+Q)logN)에 해결합니다.

Algorithm Tree

[Algorithm] cpp-python 백준 18123번: 평행우주

각 별자리는 s≤30의 트리로 주어집니다. 위상(동형)만을 비교하므로 번호를 무시하고 트리 중심에서 AHU 문자열 정규형을 만들어 대표값을 구한 뒤, 두 중심일 땐 사전순 최소를 택해 중복을 제거합니다. 서로 다른 정규형의 개수가 한 우주에 공존 가능한 별자리 최대 수가 됩니다. 전체 별 수 합 ≤1e6 조건에서 선형에 가깝게 처리되어 안전합니다.

Algorithm Graph

[Algorithm] cpp-python 백준 18485번 : Nine Judges

심사위원 선호 순위로 유도된 다수결 비교(토너먼트)에서 해밀토니안 경로를 구성해 상위 p개를 취해 ‘plausible set’을 찾는다. 분할-정복 머지와 다수결 비교로 O(n·k log k), 구현은 pos 테이블로 O(n·k) 메모리. 엣지/동률 없음(다수결 임계), 입력 정합성·인덱스·출력 형식 점검.