좌표압축 검색 결과

해당 글 2건
큰 수를 어떻게 좌표 압축하면 좋을까요?

안녕하세요. 오늘은 큰 수를 어떻게 좌표 압축을 하는지 알아보도록 하겠습니다. 대소 비교하는 방법도 익힐 겸. 백준 17126을 보면, 일반적인 그냥 쿼리 문제인 것 같아 보입니다. key의 조건을 보기 전 까지는요. 여기서, 모든 key 값의 범위는 1이상 (10^99)-1 이하입니다. 여기서 좌표 압축을 한다는 것은, 들어오는 Key나, 중요한 수에 대해서 순서를 재정렬 하는 것을 의미하는데요. 그러려면, sort가 되어야 할 거에요. 정렬을 하기 위해서는 두 큰 수를 compare 해야 합니다. 이것을 어떻게 해야 할까요? 일단 long long 형이나, int형, 그리고 __int128로는 cover가 되지 않음은 자명합니다. 먼저 어떤 수 A가 B보다 작다면 무엇을 만족해야 하는지 생각해 봅시다..
구현 2020. 3. 4. 02:10
좌표 압축 알고리즘 : 범위가 클 때 어떻게 공간을 줄일까요?

ps를 하시다 보면, 좌표 압축이라는 이야기를 심심치 않게 들으실 수 있습니다. 간단하게 말해서, 데이터를 정렬해서, 다시 순서를 부여하는 것을 말합니다. 특히 쿼리 문제에서 많이 보이는데요. 구간이 10^10개, 10^18개가 있는데, 쿼리가 단지 10만개라면, 10^18개를 다 들고 있지 않고, 중요한 구간이나 숫자만 들고 있는 기법입니다. 그러면 압축이 될 거에요. 이런 문제를 생각해 봅시다. 자. 여기서, Lv랑 Rv, 그리고 k는 [0, 10^10]에 속하는 정수라고 해 봅시다. 그리고 n과 Q가, 구간 [1, 10^5]에 속하는 정수라고 해 봅시다. 그러면, k와 Lv, Rv가 [0, 10^10] 범위에 속하는데, 어떻게 하면 좋을까요? 오프라인 처리가 가능하다면, 그냥 k값하고, Lv, Rv..
자료알고/알고리즘 2020. 2. 22. 03:40