Featured image of post [Algorithm] C++ 백준 3611번: 팀의 난이도
Algorithm Graph Flow

[Algorithm] C++ 백준 3611번: 팀의 난이도

팀의 난이도(같은 팀에서 일을 못하는 쌍/인원)를 최대화하는 문제는 최대밀도부분그래프와 동치입니다. r에 대해 |E(S)|-r|S|를 최대화하는 파라메트릭 최소절단을 구성하고 이분 탐색으로 r*를 찾은 뒤, 절단의 S측에서 최적 팀을 복원합니다. n≤100, m≤1000에서 안전합니다.

Featured image of post [Algorithm] C++ 백준 4001번: 미노타우르스 미궁
Algorithm Graph

[Algorithm] C++ 백준 4001번: 미노타우르스 미궁

좌·우수법(Left/Right-hand rule)으로 정의되는 두 개의 표준 경로를 계산하고, 2차원 누적합으로 직사각형 내부 경로/장애물 포함 여부를 O(1)에 판정합니다. 각 좌표별로 ‘막히는 최소 정사각형 크기’와 ‘설치 가능한 최대 정사각형 크기’를 각각 이분 탐색해 교집합이 존재하면 정답 후보로 갱신하여, 가장 작은 변의 길이와 위치를 찾습니다.

Featured image of post [Algorithm] C++ 백준 5466번: 상인
Algorithm Dynamic Programming

[Algorithm] C++ 백준 5466번: 상인

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

Featured image of post [Algorithm] C++ 백준 5820번: 경주 - 길이 K 최소 간선 경로
Algorithm Tree

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

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

Featured image of post [Algorithm] C++ 백준 6171번: 땅따먹기 - 묶음 할인 최소 비용 DP+CHT
Algorithm Dynamic Programming

[Algorithm] C++ 백준 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 중간 연산으로 오버플로를 방지합니다.

Featured image of post [Algorithm] C++ 백준 8987번: 수족관 3 - 카르테시안 트리
Algorithm Data Structures

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

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