알고리즘(Algorithm)

세그먼트 트리는 배열의 연속된 구간의 합, 최댓값, 최솟값 등을 구하는데 O(logN)으로 처리할 수 있다. 특히 배열의 한 원소의 값이 변경됐을 때 O(logN)으로 업데이트가 가능하다. 백준 기준 골드 상위권 티어부터 자주 사용되는 알고리즘이다.하지만 i번째 수부터

N명의 사람이 M개의 일을 처리해야 한다. 각 사람은 최대 1개의 일만 할 수 있고, 각 일(job)도 최대 1명만 담당할 수 있다. 최대한 많은 일을 처리하려면 어떻게 해야 할까?사람과 일을 매칭할 때, 그 매칭 수가 최대가 되게 하면 된다. 이를 위해 사용하는 알고

네트워크 플로우 알고리즘(Network Flow Algorithm)은 그래프 이론에서 사용되며, 최대 유량(maximum flow)을 찾는 알고리즘이다. 유량(flow)은 한 노드에서 다른 노드로의 데이터 전송량을 의미한다.예를 들어, 기름을 전송하는 파이프(pipe)

![](https://velog.velcdn.com/images/gmtmoney2357/post/646bcbfe-7c27-48d1-a4b8-dbd6137e04

모스 알고리즘은 업데이트가 없는 구간 쿼리들을 빠르게 처리하는 알고리즘이다. 이때 쿼리는 구간의 합, 최댓값, 최솟값 등이 될 수 있다.기본 아이디어는 아주 간단하다. '앞선 쿼리로 인해 계산된 값을 최대한 활용하자'이다. 특히 쿼리의 순서를 자유롭게 바꿀 수 있는 환

구간 합(range sum)은 부분 합(partial sum)을 이용하여 아주 빠르게 계산할 수 있다.부분 합: psumpos = arr0 + arr1 + ... + arrposleft, right의 구간 합: psumright - psumleft-1펜윅 트리(Fenw

2-SAT(satisfiability) 문제는 n개의 bool 변수로 이루어진 2-CNF 식이 true가 되게 하는 경우가 있는지, 있다면 각 변수에는 어떤 값이 들어가야 하는지 정하는 문제이다. 이 문제에서 2-SAT이 무엇인지 잘 설명해주고 있다.f = (￢x1 ∨

여기서 포스팅을 확인하세요!문제 링크원래 특정 문제에 대한 포스팅은 지양하는 편이지만, 이 문제는 나를 너무 고생시킨 기념으로 포스팅한다.기본적인 아이디어는 "매개 변수 탐색"이다. 주어진 C번 만큼만 끊어서, 특정 숫자((min+max)/2)만 하품하는 경우를 만들