Featured image of post [Vocabulary] Guarantee - 보장과 보증의 정확한 의미

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

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

Featured image of post [Algorithm] C++ 백준 12876번: 반평면 땅따먹기 2

[Algorithm] C++ 백준 12876번: 반평면 땅따먹기 2

직선 (a, b)을 동적으로 추가/삭제하고 질의 x마다 ax+b의 최댓값을 구하는 문제를 세그먼트 트리(시간 구간) 오프라인 + 롤백 가능한 Li Chao Tree로 해결한다. 공집합 시 EMPTY 처리, 64비트 안전, O(N log N log X) 복잡도로 30만 연산을 통과한다.

Featured image of post [Algorithm] cpp 백준 10076번: 휴가 - 최적 풀이

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

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

Featured image of post [Algorithm] cpp 백준 11012번: Egg - 2D 직사각형 쿼리 스위핑+BIT

[Algorithm] cpp 백준 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) 처리, 중복 좌표 대응을 주의한다.

Featured image of post [Algorithm] cpp 백준 11407번: 책 구매하기 3

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

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

Featured image of post [Algorithm] cpp 백준 11408번: 열혈강호 5 - MCMF 최소비용 최대매칭

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

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

Featured image of post [Algorithm] cpp 백준 11717번: Wall Making Game

[Algorithm] cpp 백준 11717번: Wall Making Game

H×W 격자에서 점을 하나 고르면 그 행·열 전체가 벽이 되어 보드가 네 개의 직사각형 서브게임으로 분할됩니다. 표시 칸(X)은 선택 불가이지만 벽으로 변할 수 있습니다. 스프라그-그런디 정리로 각 서브직사각형의 그런디 수를 XOR해 승자를 판단하며, 메모이제이션을 적용한 사각형 분해 DP로 최적 풀이를 구현합니다.

Featured image of post [Algorithm] cpp 백준 11932번: 트리와 K번째 수 - PST+LCA

[Algorithm] cpp 백준 11932번: 트리와 K번째 수 - PST+LCA

정점 값 좌표압축 뒤 루트→정점 경로마다 영속 세그먼트 트리를 누적 구축하고, LCA를 이용해 경로 빈도를 포함-배제로 합산해 K번째 수를 찾습니다. 세그먼트 트리에서 왼/오 자식으로 이진 하향 탐색해 순위 k를 복원하며, 전체 시간/공간은 O((N+M)logN)/O(NlogN) 수준입니다.

Featured image of post [Algorithm] cpp 백준 11933번: 공장들

[Algorithm] cpp 백준 11933번: 공장들

트리 위 두 회사 공장 집합 A, B 사이의 최소 거리를 구하는 문제입니다. LCA 전처리 후 질의마다 A∪B와 인접 LCA들로 버추얼 트리를 만들고, 두 번의 DP로 각 정점의 A까지/ B까지 최단거리를 구해 min(dA+dB)로 답합니다. O((|A|+|B|)logN)으로 6초 제한을 안정 통과합니다.

Featured image of post [Algorithm] cpp 백준 1210번: 마피아 - 정점 분할 최소 컷

[Algorithm] cpp 백준 1210번: 마피아 - 정점 분할 최소 컷

마피아의 이동을 막기 위해 톨게이트를 최소 비용으로 점거하는 문제를 정점 가중치 s-t 최소 컷으로 모델링합니다. 각 정점을 in/out으로 분할하고 내부 간선에 비용을 두어 최대 유량=최소 컷으로 풀이하며, 시작/도착 정점 점거 허용까지 반영합니다.