Tags

97 pages

Graph

[Algorithm] C++ 백준 11409번: 열혈강호 6

BOJ 11409 열혈강호 6 문제는 직원과 일을 이분 매칭한 뒤, 먼저 처리 가능한 일의 개수를 최대로 하고 그 상태에서 월급 총합을 최대로 만드는 최소 비용 최대 유량(Min Cost Max Flow) 유형입니다. 이 글에서는 문제 해석부터 그래프 모델링, 음수 비용 간선 구성, SPFA 기반 최소 비용 최대 유량 구현까지 전체 풀이 과정을 C++ 코드와 함께 자세히 정리합니다.
[Algorithm] C++ 백준 11409번: 열혈강호 6

[Algorithm] C++ 백준 20131번: 트리 만들기

N개의 정점으로 이루어진 트리에서 리프를 큰 번호부터 하나씩 제거하며 인접 정점을 기록해 얻은 수열이 주어졌을 때, 원래 트리를 역으로 복원하는 문제입니다. 차수와 우선순위 큐를 이용해 리프를 관리하고, 마지막 두 정점을 연결하는 방식으로 O(N log N)에 유일한 트리를 구성하거나, 불가능한 경우를 안전하게 검출하는 구현과 정당성을 정리합니다.
[Algorithm] C++ 백준 20131번: 트리 만들기

[Algorithm] C++/Python 백준 16993번: 연속합과 쿼리 (세그먼트 트리)

길이 N(≤100,000) 수열에 대해 구간 [i,j]의 최대 연속합을 O(log N)으로 질의하는 세그먼트 트리 풀이입니다. 각 노드에 합·최대 접두/접미합·구간 최대합을 저장하고 병합 규칙으로 정답을 계산합니다. 음수 전용 구간·단일 원소·전부 음수인 경우를 안전하게 처리하며, 시간·공간 복잡도와 실수 포인트를 정리했습니다.
[Algorithm] C++/Python 백준 16993번: 연속합과 쿼리 (세그먼트 트리)

[Algorithm] C++ 백준 10076번: 휴가 - 최적 풀이

IOI 2014 Holiday(휴가) 최적 풀이. 선형 도시에서 하루에 이동 또는 방문만 가능한 제약에서 방문 관광지 수를 최대화한다. 이동은 한 번의 방향 전환만 해도 충분하다는 관찰 아래 [l,r] 구간을 잡고 체류 가능일 g(l,r)을 계산한다. 분할정복+세그먼트 트리로 상위 k 합을 빠르게 질의하여 O(N log^2 N)로 해결한다. 경계·중복·음수 k 처리와 좌우 반전까지 구현 체크리스트 포함.
[Algorithm] C++ 백준 10076번: 휴가 - 최적 풀이