Algorithm (142) 썸네일형 리스트형 213. IMOS Method 펜윅 트리를 설명하면서 연습문제로 수열과 쿼리 21을 소개했다. 그리고 문제 해설에 구간 업데이트 + 점 쿼리를 점 업데이트 + 구간 쿼리로 변형할 수 있다고 했는데, 이 아이디어를 정형화한 IMOS법(IMOS Method)에 대해서 알아보기로 한다. IMOS법은 구간을 시작점과 끝점으로 분리하여 구간 처리를 점 처리로 대체하는 트릭으로, 구간이 여러 개 주어지고 특정 시점을 포함하는 구간의 수를 빠르게 구할 수 있는 방법이다. 수식을 써서 표현하면 다음과 같이 나타낼 수 있다.구간 $n$개가 존재하며, $i$번째 구간을 $[l_i, r_i]$로 나타낼 수 있다. $(l_i \le r_i)$$k$를 포함하는 구간의 수를 구하는 쿼리가 주어진다.여기서는 $l_i$와 $r_i$가 모두 $1$ 이상 $2n$ .. 210. Two Pointers 다음과 같은 문제를 생각해 보자. BOJ 3273. SumX (Silver III) $n$개의 서로 다른 정수가 주어질 때, 여기서 서로 다른 두 수를 골라서 합이 $x$가 되게 만드는 경우의 수를 구하시오.이 문제의 경우 입력되는 정수의 범위가 크지 않아서 크기가 $10^6$인 배열을 선언해서 각 수가 등장했는지 체크하는 식의 방법으로 풀 수 있다. 하지만 입력되는 정수의 범위가 $10^{18}$ 정도까지 커졌다고 가정해 보자. 일단 set 등을 사용해서 각 수마다 $x$에서 그 수를 뺀 값이 set에 존재하는지 확인하는 방식으로 해결이 가능하다. 하지만 set은 속도가 그렇게 빠르지 않고, 각 수마다 set에서 값을 찾는 시간복잡도가 $O(\lg n)$이다. 이번 글에서는 이 방법을 대체할 수 있는 .. 209. Coordinate Compression 좌표 압축(Coordinate Compression)은 범위가 큰 값들을 처리하기 위해 값들을 치환하여 범위를 줄이는 기법이다. 이 방법을 적용하기 위해서는 상대적인 값, 즉 대소 관계만 중요해야 하며 절대적인 값은 중요하지 않아야 한다. 그러면 좌표 압축을 어떻게 하는지 알아보자. 방법은 간단한데, 가장 작은 값들을 $1$, 그 다음으로 작은 값들을 $2$, 이런 식으로 치환하는 것이다. 상황에 따라서 가장 작은 값들을 $0$으로 치환하는 것도 가능하다. 웬만한 문제에서는 입력되는 수의 개수가 많아야 $10^5 \sim 10^6$ 단위이고 $10^7$개 이상의 수를 입력받는 문제는 거의 없으므로 가장 작은 값을 $1$로 치환했을 때 가장 큰 값은 대부분의 경우 $10^6$ 이하, 아무리 커도 $10^7.. 208. Others Intro 카테고리 K에서는 그동안 다루지 않았던 여러 범용적인 주제들을 다룬다. 다루는 내용은 다음과 같다.좌표 압축(Coordinate Compression)포인터와 스위핑(Pointers & Sweeping)최적화를 이용한 탐색(Optimized Search)매트로이드(Matroid)오프라인 쿼리(Offline Query)익숙해져야 하는 5가지 주제최적화를 이용한 탐색(특히 휴리스틱)에 관한 내용이 이 카테고리의 절반 정도를 차지하지만 먼저 다루는 내용들은 다른 카테고리에서 다루었던 다양한 자료 구조와 알고리즘 문제를 푸는 데 상당히 자주 등장하므로 알고 있어야 하고, 마지막에 다루는 주제들 역시 매트로이드를 제외하면 문제를 풀면서 접할 일이 많을 것이다. 특히 이 주제들에 상대적으로 취약한 사람들이 많은 편.. 196. Counting Points in Triangle 이번에는 삼각형 안의 점 개수를 빠르게 세는 테크닉(Counting Points in Triangle)에 대해서 다룬다. 이 테크닉에 붙은 이름은 아직까지는 없는 것으로 알고 있다. 따라서 이 글의 제목도 공식적으로 굳어진 명칭이 아니다. 다음과 같은 문제를 생각해 보자.$2$차원 좌표평면에 속한 점 $n$개가 주어진다. 어떤 세 점도 일직선상에 있지 않다. 이제 여기서 세 개의 점을 골라서 삼각형을 만들면 그 삼각형은 다른 점들을 포함할 수도 있다. 이때 점을 $0, 1, \ldots, n - 3$개 포함하는 삼각형의 개수를 모두 구하여라.점 $n$개로 만들 수 있는 서로 다른 삼각형의 수는 $\frac{n(n - 1)(n - 2)}{6} = \frac{1}{6}n^3 - \frac{1}{2}n^2 +.. 195. Small to Large Technique 첫 번째로 알아볼 최적화 기법은 작은 집합에서 큰 집합으로 합치는 테크닉(Small to Large Technique)으로, 분리 집합을 조금 더 발전시킨 것으로 이해할 수 있다. 즉, 기존의 분리 집합이 '원소 $x$가 속한 집합은 무엇인가?'라는 질문에 대한 답을 제공할 수 있다면 이 스몰 투 라지 기법은 '집합 $S$에 속한 원소들은 무엇인가?'라는 질문에 대한 답을 제공할 수 있다고 보면 된다. 물론 두 개를 같이 쓰면 양방향 질의 처리가 가능하다. 어떤 집합에 속한 원소들이 무엇인지를 알아야 하기 때문에 집합이 합쳐질 때마다 집합 내의 원소들도 하나로 합쳐야 하는데, 여기서 항상 원소의 수가 더 적은 집합을 원소의 수가 많은 집합에 합치면 어느 정도의 속도를 보장한다는 것이 작은 집합에서 큰 집.. 186. Heavy-Light Decomposition 헤비-라이트 분할(Heavy-Light Decomposition, HLD)는 트리에서 경로와 관련된 다양한 쿼리를 처리하는 테크닉이다. 트리에서 다음과 같은 쿼리를 처리하는 문제를 생각해 보자.$1\ i\ c$: $i$번째 간선의 가중치를 $c$로 바꾼다.$2\ x\ y$: 정점 $x$와 $y$ 사이의 최단 경로가 포함하는 간선들의 가중치의 합을 출력한다.정점이 $n$개인 트리에서 두 정점 사의의 최단 경로는 최대 $(n - 1)$개의 간선을 포함하므로 경로상의 간선을 하나씩 보는 방법은 당연히 너무 느리다. 이 문제점을 해결하기 위해 HLD는 간선을 그룹으로 묶은 다음 그룹을 한 번에 처리할 수 있게 한다. 이때 경로가 너무 많은 그룹을 지나면 간선을 그룹으로 묶는 의미가 없어지므로 어떤 경로를 선택하.. 184. Continuous Sum Segment Tree DP로 해결할 수 있는 문제 중 수열에서 최대 연속합을 구하는 문제가 있다. 이전에 소개한 적이 없으므로 여기서 소개를 하자면 다음과 같다. 아래 문제를 보자. BOJ 1912. 연속합 (Silver II) $n$개의 수가 주어지고 그것을 각각 $a_1, a_2, \ldots, a_n$이라고 했을 때 두 인덱스 $i$와 $j$를 잘 정해서 $a_i + a_{i + 1} + \ldots + a_{j - 1} + a_j$가 최대가 되도록 해야 한다. 세 번째 예제에서 볼 수 있듯이 모든 수가 음수인 경우에도 최소 하나의 수를 골라야 한다. 이 문제를 DP로 풀기 위해 식을 세워 보자. $j$가 $1$인 경우부터 $n$인 경우까지 각각에 대해 해당 조건에서의 최대 연속합 $m_j$를 구하고 거기서 가장 큰 .. 이전 1 2 3 4 ··· 18 다음
