TV Show Travel Reality MBC

[TV Show] 태어난 김에 세계일주 시즌4 (2025) - 네팔 ‘차마고도’ 대장정

네팔 히말라야 ‘차마고도’ 루트에서 펼쳐진 기안84·이시언·빠니보틀·덱스의 여정. 루클라–남체바자르 셰르파 동행부터 안나푸르나 캠핑·오체투지·전통의상 가족사진·풀빌라 힐링까지 1~8화 전편 줄거리·하이라이트·메시지 총정리

Algorithm BOJ Computational Geometry

[Algorithm] C++ 백준 10746번 : Fencing the Herd

동적으로 소가 추가되는 좌표 집합에 대해 직선 울타리 Ax+By=C가 모든 소를 한쪽 반평면에 두는지 판별한다. 시간 세그먼트 트리+노드별 볼록껍질로 지지함수(min/max 내적)를 빠르게 구해 O(log^2 N)로 YES/NO를 처리한다.

[Algorithm] C++ 백준 12670번 : The Year of Code Jam (Large)

격자 달력에서 파란날 행복도 4−이웃수의 합을 최대화하는 문제를 이분 격자 그래프 컷으로 환원한다. B측 보조 변수 y=1−x 변환과 Potts [x!=y] 간선, 단항 재매개화, 고정일(#, .)을 s-t 컷으로 구성해 Dinic으로 최적값을 빠르게 구한다.

[Algorithm] C++ 백준 12736번 : Fireworks

백준 12736 Fireworks(APIO 2016)는 스위치-연결점-폭약으로 이루어진 트리에서 모든 폭약의 폭발 시각을 같게 만들기 위해 도화선 길이를 조정하는 최소 비용을 구하는 문제입니다. 볼록 함수(slope trick) 기반 트리 DP와 small-to-large 우선순위 큐 합병으로 O((N+M) log^2(N+M))에 해결합니다. 구현 핵심은 기울기 변화 지점을 우선순위 큐로 관리하고, 간선 통과 시 upperize 연산으로 기울기와 절편 변화를 반영하는 것입니다. 안전한 64-bit 정수 사용과 서브트리 크기 기준 정렬로 상수 시간을 줄여 AC를 얻습니다.

[Algorithm] C++ 백준 12898번 :Selling RNA Strands

백준 12898 Selling RNA Strands 문제를 접두사·접미사 조건을 각각 트라이 서브트리 구간으로 변환하고, 오일러 투어와 펜윅 트리(Fenwick/BIT)를 이용한 2D 직사각형 카운팅으로 M개의 질의를 빠르고 안정적으로 처리하는 C++ 풀이를 정리합니다. 대용량 입력을 위한 Fast I/O와 메모리 사용 최적화 포인트, 시간·공간 복잡도 분석까지 한 번에 확인할 수 있습니다.

[Algorithm] C++ 백준 13725번 - RNG

선형 점화식 A_i = ∑ A_{i-j}·C_j (mod 104857601)를 Bostan–Mori와 NTT로 O(k log k log N)에 계산합니다. 2^22·5^2+1 소수 모듈러에서 다항식 곱셈으로 A_N을 빠르고 안정적으로 구하는 C++ 정답과 구현 포인트를 정리합니다.

[Algorithm] C++ 백준 13727번 : 5차원 구사과 초콜릿

백준 13727 5차원 구사과 초콜릿은 2×2×2×2×n 격자를 1×1×1×1×2 도미노로 채우는 가짓수를 구하는 문제입니다. 비트마스크 DP로 초항을 만들고 Berlekamp–Massey로 선형 점화를 복원해 O(log n)으로 n번째 항을 구하는 C++ 풀이를 정리합니다.

[Algorithm] C++ 백준 14510번 : Blazing New Trails

특수/일반 노드 간 교차 간선을 정확히 w개 포함하는 최소 스패닝 트리. 라그랑주 가중치로 교차 간선에 x를 더해 크루스칼을 돌리고, 이분 탐색으로 w를 맞춘 뒤 비용'에서 x·w를 빼 원래 최소 비용을 복원한다. 정렬 1회, 탐색 중 두 포인터 병합으로 빠르게 처리.

[Algorithm] C++ 백준 14737번 Dev, Please Add This!

격자에서 공을 상하좌우로 굴려 벽이나 가장자리에 닿을 때까지 이동하는 퍼즐에서, 모든 별을 하나의 플레이 순서로 획득할 수 있는지 판정한다. 단순 커버리지가 아니라 이동 순서 제약이 존재하므로 셀 단위 이동을 단방향 그래프로 모델링하고, 강한 연결 요소(SCC)로 압축한 DAG에서 상호 비가역(서로 도달 불가)한 컴포넌트 쌍의 동시 방문을 금지하는 제약과 각 별이 있는 칸의 행/열 중 하나의 정지 컴포넌트를 반드시 방문해야 한다는 제약을 2-SAT으로 구성해 모순 여부로 YES/NO를 결정한다. Kosaraju로 SCC를 구하고 DAG 도달성은 비트셋 DP로 처리하여 50×50까지 빠르게 동작한다.

[Algorithm] C++ 백준 14960번 - Strongly Matchable

BOJ 14960 Strongly Matchable을 그래프 이론 관점에서 정리. Hall 정리 기반 조건을 ‘충돌 이분 그래프’로 환원하고, Kőnig 정리(α=|V|-ν)와 Hopcroft–Karp로 최대 독립집합 크기를 구해 강매칭성 여부를 판별하는 실전 C++ 풀이.

[Algorithm] C++ 백준 15292번 : Journey from Petersburg to Moscow

도로 네트워크에서 상트페테르부르크→모스크바 최단 경로의 ‘가장 비싼 간선 k개만 결제’ 비용을 최소화한다. 임계값 α에 대해 간선 비용을 max(0, w−α)로 변환해 다익스트라를 수행하고, k·α를 더한 값의 최소를 간선 가중치 집합(및 0)에서 탐색해 정답을 구한다.

[Algorithm] C++ 백준 15521번 : Revenge of the Broken Door

백준 15521은 하나의 간선이 공사 중일 때 최악의 총 이동 거리를 최소화하는 경로를 구하는 문제입니다. T에서 다익스트라로 SPT를 만들고 비트리 간선을 HLD+세그로 경로 최소 갱신, 이분 탐색+Dijkstra로 최적 값을 구합니다.

[Algorithm] C++ 백준 15737번 : 일반 그래프 매칭

Edmonds Blossom로 일반 그래프에서 최대 매칭을 구합니다. BFS 증가 경로 탐색과 블로섬 수축, LCA 기반 기저 갱신을 구현해 N≤500, M≈N(N−1)/2에서도 1초 내 통과하는 C++ 정답과 핵심 포인트를 정리합니다.

[Algorithm] C++ 백준 15768번 - Duathlon

APIO 2018 Duathlon(백준 15768) 문제를 Tarjan의 이중연결요소(BCC)와 Block-Cut Tree로 모델링하고, 보수계산으로 ‘불량’ 삼중쌍을 합산해 전체 경우에서 빼는 O(N+M) C++ 풀이를 정리합니다. 스택 기반 간선 추출, 서브트리 원소수 집계, 절단점-블록 기여 계산, 64비트 오버플로 주의, 샘플 검증과 빌드/실행 방법까지 포함.

Algorithm BOJ Computational Geometry UCPC 2018

[Algorithm] C++ 백준 15939번 쉬운 최단경로

UCPC 2018 B(BOJ 15939) 쉬운 최단경로 문제 풀이. 두 점의 위치(외부/내부)에 따라 3가지로 분기. 내부-내부는 선분 교차 대각선 수와 각자 외부로 나가는 비용 합 중 최솟값을 O(N)로 계산하고, 내부 판정은 O(log N)로 최적화한다.

[Algorithm] C++ 백준 16041번 : Double Clique

백준 16041 Double Clique를 스플릿 그래프 특성으로 환원해 정렬된 차수 누적 합 등식(sum_S−s(s−1)=2m−sum_S)으로 분할 크기 s를 찾고, 제거·추가·교환 경우의 수를 합산해 1e9+7로 정답을 출력하는 C++ 풀이.

Algorithm BOJ Tree DP

[Algorithm] C++ 백준 16191번 : Utilitarianism

트리에서 서로 인접하지 않는 k개의 간선을 골라 가중치 합을 최대로 만드는 문제. 라그랑주 최적화(λ)로 k-제약을 벌점으로 흡수하고, 노드별 상태 DP(A/B)로 F(λ)=max∑(w-λ)와 선택 간선 수를 O(n)에 계산, λ에 대한 단조성을 이용해 이분 탐색 후 F(λ)+λk의 최소값으로 정답을 복원한다.

[Algorithm] C++ 백준 1659번 : 수 (Hard)

백준 1659 수 (Hard): S∪T 병합 정렬 뒤 약한 연결(최근접 반대 타입)과 균형 구간 강한 매칭 비용(|∑S−∑T|)을 결합한 선형 DP로 최소 총비용을 구한다. 시간 O(n+m), 메모리 O(n+m)인 C++ 구현과 핵심 아이디어를 함께 정리한다.

[Algorithm] C++ 백준 17439번 : 꽃집

가격 오름차순 N개의 꽃을 최대 K개 구간으로 연속 분할하여 ∑(구간합×구간길이)을 최소화. 추가 비용 C를 이분탐색(Alien’s trick)하고 교점 1개 성질을 이용한 단조 큐 최적화로 O(N log N log X) 해법과 C++ 구현을 정리한다.

[Algorithm] C++ 백준 17442번 : 삼분 그래프

평면 그래프에 두 수직선 x=A, x=B를 그어 그래프를 삼분할할 때 조각 수를 구한다. 오일러 공식 ΔC=ΔV−ΔE+ΔF와 듀얼 그래프로 각 면의 x-범위를 구해 2D 질의로 ΔF(잘리는 면 수)를 세고, ΔE는 간선 교차수 누적으로 계산한다. 외부 면을 제외해 정확히 세며, 전체는 O((N+M)logN + Qlog^2N)로 처리하는 C++ 풀이.