좌표 압축 (1) 썸네일형 리스트형 좌표 압축 - 원소의 밀도를 높이자 스위핑이나 탐색을 하면서 어떤 범위를 전부 확인해야 한다고 해보자. 그런데 그 범위가 -100억 ~ 100억 이라면? 단순 선형 탐색도 시간 초과를 피하기 어려울 것이다. 다만 범위에 속한 원소의 개수가 충분히 작다면 각 원소의 좌표들을 원소의 개수만큼의 범위로 압축한다면 빠르게 탐색을 할 수 있다. 이렇게 좌표의 범위를 압축하여 원소 집합의 밀도를 높이는 기법을 좌표 압축이라고 부른다. 이 게시글에서는 C++의 STL로 간단하게 압축하는 방법을 알아본다. 방법은 아주 간단하다. 원소를 벡터로 모두 수집한 다음 std::erase와 std::unique를 이용하여 중복 원소를 모두 제거하면 index와 원소가 일대일 대응하게 되어 좌표 압축을 할 수 있다. std::unique를 사용하기 위해 벡터는 정.. 이전 1 다음