Algorithm/K. Others (6) 썸네일형 리스트형 227. Case Work 두 번째로 케이스워크(Case Work)에 대해서 살펴보기로 한다. 케이스워크라는 단어는 PS를 오랫동안 했다면 별다른 어색함 없이 받아들이기 쉽지만, 자세히 생각해 보면 꽤 묘한 단어이다. 먼저 케이스(Case)는 직관적으로 번역할 수 있다. 여러 가지 경우를 말하는 것이다. 다음으로 워크(Work)의 간단한 번역 중 가장 나은 것은 '처리'라고 할 수 있다. 즉 케이스워크를 풀어서 설명하면 여러 가지 경우를 처리하는 것이 된다. 그러면 '여러 가지 경우'가 어느 정도를 의미하는지 생각해 보자. '여러 가지'는 추상적인 단어이기 때문에 이것을 모든 사람이 동일하게 받아들이도록 정의할 수는 없다. 대신 다수의 사람들이 동의할 만한 기준을 세울 수는 있다. 예를 들어 이런 문제가 케이스워크에 해당하는지 묻.. 226. Offline Query 이제부터는 익숙해져야 하는 $7$가지 주제를 차례로 소개하려고 한다. 이 주제들은 대회나 코딩 테스트를 가리지 않고 언제든지 등장할 수 있으며 어떤 유형의 문제와도 결합이 가능하다.그중에서 첫 번째로 살펴볼 유형은 오프라인 쿼리이다. 그러면 먼저 쿼리가 무엇인지부터 살펴보자. 알고리즘 문제에서 쿼리(Query)는 데이터에 행해지는 반복되는 연산을 의미한다. 이때 데이터는 그래프, 집합, 선형 등 특정한 형태를 가지며 여러 값이 아닌 정수나 실수 하나의 형태로도 존재할 수 있다. 또한 연산은 종류에 따라 추가(Create), 조회(Read), 수정(Update), 삭제(Delete) 등으로 구분할 수 있다. 넓은 의미에서 SQL의 쿼리와 유사한 측면도 있으나 실제 데이터베이스를 건드리는 것이 아니기 때문에.. 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가지 주제최적화를 이용한 탐색(특히 휴리스틱)에 관한 내용이 이 카테고리의 절반 정도를 차지하지만 먼저 다루는 내용들은 다른 카테고리에서 다루었던 다양한 자료 구조와 알고리즘 문제를 푸는 데 상당히 자주 등장하므로 알고 있어야 하고, 마지막에 다루는 주제들 역시 매트로이드를 제외하면 문제를 풀면서 접할 일이 많을 것이다. 특히 이 주제들에 상대적으로 취약한 사람들이 많은 편.. 이전 1 다음
