English Vocabulary

[Vocabulary] Guarantee - 보장과 보증의 정확한 의미

영어 단어 'guarantee'의 정확한 의미와 활용법을 다룬다. '보장, 보증'의 개념부터 실생활과 비즈니스 상황에서의 다양한 용법, 관련 표현과 유의어를 통해 완벽하게 이해할 수 있다. Money-back guarantee, guarantee period 등 실용적인 표현과 함께 신뢰와 약속을 전달하는 영어 표현을 익힌다.

Algorithm Data Structures

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

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

Algorithm Geometry

[Algorithm] C++ 백준 10254번: 고속도로 - 회전하는 캘리퍼스

최대 20만 점에서 유클리드 최장거리 쌍을 찾습니다. 단조사슬로 볼록 껍질을 O(n log n)에 구하고, 회전하는 캘리퍼스로 지름을 O(h) 탐색합니다. 제곱거리·64비트·빠른 입출력 적용.

Algorithm String

[Algorithm] C++ 백준 10538번: 빅 픽쳐 - 2D 롤링 해시로 O(HW) 매칭

흑백 격자에서 작은 그림이 걸작 내에 나타나는 모든 위치를 계산합니다. 행/열 분리 2차원 롤링 해시와 이중 해싱으로 충돌을 낮추고 O(HW) 시간에 서브매트릭스 매칭을 수행하여 제한 조건을 안정적으로 만족합니다.

Algorithm Fenwick Tree

[Algorithm] C++ 백준 11012번: Egg - 2D 직사각형 쿼리 스위핑+BIT

n개의 점과 m개의 직사각형 [l,r]×[b,t]가 주어질 때, 각 직사각형 안의 점 개수를 모두 합한 값을 구한다. x를 기준으로 오프라인 스위핑을 수행하고, y는 좌표 압축 후 펜윅 트리(Fenwick Tree)로 누적 빈도를 관리한다. 쿼리는 (r,+1),(l-1,−1) 이벤트로 분해해 포함-배제를 구현하여 총합을 O((n+m) log n)에 계산한다. 64비트 누적, 경계(b=0) 처리, 중복 좌표 대응을 주의한다.

Algorithm Math

[Algorithm] C++ 백준 11385번: 씽크스몰 - NTT+CRT 다항식 곱셈

NTT 친화 소수 3개에서 다항식 곱셈을 수행하고 CRT로 계수를 복원해 모든 계수의 XOR을 계산합니다. N, M ≤ 1e6의 대용량 입력을 O(n log n) 시간과 선형 메모리로 안정 처리하며, 오버플로는 __int128로 방지합니다.

Algorithm Graph

[Algorithm] C++ 백준 11405번: 책 구매하기 - 최소 비용 최대 유량

수요·공급 합이 같은 이분 네트워크에서 총 배송비를 최소화한다. S→서점(B_i), 서점→사람(C_ij), 사람→T(A_j)로 모델링하고 잠재치+Dijkstra 기반 최소비용최대유량으로 계산한다. 잔여그래프·역간선 점검 포함.

Algorithm Graph

[Algorithm] C++ 백준 11407번: 책 구매하기 3

사람–서점 이분 그래프에 수요·공급·구매제한을 용량/비용으로 모델링하고, 잠재함수 기반 최단경로 반복(MCMF)로 최대 유량과 최소 비용을 동시에 달성합니다. 모델링, 정당성, 구현 포인트와 복잡도를 일목요연하게 정리했습니다.

Algorithm Graph

[Algorithm] C++ 백준 11408번: 열혈강호 5 - MCMF 최소비용 최대매칭

이 문제는 직원-일 이분 그래프에서 임금 비용을 최소화하며 가능한 한 많은 일을 배정하는 과제입니다. 최소 비용 최대 유량(MCMF)로 모델링하여 Dijkstra+잠재치(Johnson)로 음수 없는 보정 비용을 사용, 유량 1씩 확장하며 비용 합을 최소화합니다. 제약(N,M≤400, 임금≤10^4)에 맞춰 O(F·E·logV)로 안정적으로 통과합니다.

Algorithm Dynamic-Programming

[Algorithm] C++ 백준 1144번: 싼 비용 - Connection Profile DP

N,M ≤ 9 격자에서 상하좌우로 연결된 하나의 칸 집합을 골라 비용 합의 최솟값을 찾습니다. 연결 프로파일 DP로 상태를 라벨링·정규화해 압축하고, 고립 검사와 병합 전이로 올바름과 효율을 보장합니다. 시간·공간 복잡도, 구현 포인트, 코너 케이스까지 정리합니다.