목록분류 전체보기 (57)
charminseok
좌표 압축
좌표 압축은 입력값의 범위가 매우 크지만 입력 개수가 작을 때 사용하면 매우 효율적이다. 2017 카카오 코드 예선 캠핑 문제(https://www.welcomekakao.com/learn/courses/30/lessons/1833)에서도 좌표 압축이 사용되는데, 이 문제에서 입력값의 범위는 0부터 2^31-1로 매우 크지만 입력 가능한 개수는 5000개로 제한되어 있다. 그렇기 때문에 서로 다른 값들을 순서대로 인덱스를 구해 효과적으로 탐색을 할 수 있다. 예를 들어, 입력으로 좌표 (0,0), (123,0), (0,123), (1856185,100), (10,123)이 있다고 가정해보자. x값은 0, 123, 0, 1856185, 10에서 중복을 없애고 순서대로 0, 10, 123, 1856185로 ..
알고리즘
2019. 9. 6. 23:02