본문 바로가기

Algorithm

 (143)
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$에 속한 원소들은 무엇인가?'라는 질문에 대한 답을 제공할 수 있다고 보면 된다. 물론 두 개를 같이 쓰면 양방향 질의 처리가 가능하다. 어떤 집합에 속한 원소들이 무엇인지를 알아야 하기 때문에 집합이 합쳐질 때마다 집합 내의 원소들도 하나로 합쳐야 하는데, 여기서 항상 원소의 수가 더 적은 집합을 원소의 수가 많은 집합에 합치면 어느 정도의 속도를 보장한다는 것이 작은 집합에서 큰 집..
194. Optimization Intro 카테고리 J에서는 다양한 최적화(Optimization) 기법을 통한 문제 해결 방법과 이의 대표적 예시인 동적 계획법 최적화(DP Optimization)에 대해서 다룬다. 다루는 내용은 다음과 같다.개선된 분리 집합(Small to Large Technique)삼각형 안의 점 개수 세기(Counting Points in Triangle)동적 계획법 최적화(DP Optimization)오프라인 동적 연결성 판별(Offline Dynamic Connectivity)커넥션 프로파일 DP(Connection Profile DP)스위핑 회전(Rotating Sweep Line)개선된 최장 공통 부분수열(Hirschburg's Algorithm, Bitset LCS)대부분이 상당히 복잡한 내용을 포함하고 있으며..
186. Heavy-Light Decomposition 헤비-라이트 분할(Heavy-Light Decomposition, HLD)는 트리에서 경로와 관련된 다양한 쿼리를 처리하는 테크닉이다. 트리에서 다음과 같은 쿼리를 처리하는 문제를 생각해 보자.$1\ i\ c$: $i$번째 간선의 가중치를 $c$로 바꾼다.$2\ x\ y$: 정점 $x$와 $y$ 사이의 최단 경로가 포함하는 간선들의 가중치의 합을 출력한다.정점이 $n$개인 트리에서 두 정점 사의의 최단 경로는 최대 $(n - 1)$개의 간선을 포함하므로 경로상의 간선을 하나씩 보는 방법은 당연히 너무 느리다. 이 문제점을 해결하기 위해 HLD는 간선을 그룹으로 묶은 다음 그룹을 한 번에 처리할 수 있게 한다. 이때 경로가 너무 많은 그룹을 지나면 간선을 그룹으로 묶는 의미가 없어지므로 어떤 경로를 선택하..

티스토리툴바