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

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 코드와 정당성 근거까지 정리했습니다.