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).

Algorithm Dynamic Programming

[Algorithm] cpp 백준 5466번: 상인

IOI 2009 상인 문제. 집 S에서 출발·복귀하며 U/D 비용으로 강을 오르내리며 시장을 방문해 이익 합을 최대로 한다. 날짜별 비내림 방문 제약을 활용해 좌/우 이동 비용을 선형식으로 흡수한 최대 변환과 같은 날 내부 양방향 스위핑 DP를 결합, 좌표압축+펜윅 트리로 O(N log N) 최적 이익을 계산한다.

Algorithm Tree

[Algorithm] cpp 백준 5820번: 경주 - 길이 K 최소 간선 경로

트리에서 길이 K인 경로 중 사용 간선 수가 최소인 것을 찾는다. 센트로이드 분해로 각 서브트리 거리 목록을 수집해 보완 거리(K−d)와 즉시 매칭하고, 터치된 거리만 관리해 O(N log N) 내 해결한다. 가중치 합 가지치기와 64비트 누적으로 안전성을 확보한다.

Algorithm Dynamic Programming

[Algorithm] cpp 백준 6171번: 땅따먹기 - 묶음 할인 최소 비용 DP+CHT

여러 직사각형 땅을 묶어 살 때 비용은 (묶음 내 최대 W)*(묶음 내 최대 H)입니다. W 오름차순 정렬 후 같은 W는 최대 H로 병합하고, 뒤에서 앞으로 보며 지배된 직사각형을 제거해 H를 단조 감소로 만듭니다. 이후 dp[i]=min(dp[k]+W[i]*H[k+1])를 단조 Convex Hull Trick으로 O(n)에 계산하며, 정수 교차 비교와 __int128 중간 연산으로 오버플로를 방지합니다.

Algorithm Greedy

[Algorithm] cpp 백준 8131번: Ploughing - 슬라이딩 윈도우

2000×2000 격자에서 합 ≤ K인 바깥 행·열만 제거하며 제거 횟수를 최소화한다. 마지막 1×L 또는 L×1 스트립 길이 최대화로 환원하고, 2D 누적합+투포인터로 O((N+M)^2) 해결. 경계 우선 그리디 핵심.

Algorithm Segment Tree

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

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

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, 엣지·실수 포인트 점검.