Algorithm/K. Others (3) 썸네일형 리스트형 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 다음
