💕
후원
[알고리즘] 좌표 압축
치토스 선배 강의 듣고 씀. 좌표 압축 좌표의 범위가 막 ≤ 1,000,000,000으로 큰 경우가 있다. 이런 경우에 arr[1000000000] 같은 배열을 선언하면 당연히 터져버린다. [BOJ] 가로 블록 쌓기 문제 같은 경우 0 ≤ Wi + Di ≤ 2,000,000,000로 좌표 자체의 범위는 크지만, 들어오는 블록의 개수는 100,000개다. 즉 좌표로서 들어오는 수의 종류는 최대 200,000개 라는 뜻이다. 200,000개는 배열로 만들 수 있다. 만약 들어오는 좌표의 종류가 {1, 23434, 9495444, 124, 8, 249833876, 23434}이라면 이를 순서대로 정렬하고 {1, 8, 124, 23434, 23434, 9495444, 249833876}, 중복을 제거해 {1, ..
2020. 10. 9.