좌표압축
[백준/C++] 18870 좌표압축
문제 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 이번 문제는 좌표압축이 뭔지 배우는것부터 시작했다. 좌표압축의 개념은 아래 포스팅에서 정리했고, 좌표 압축 알고리즘 이란? 백준 18870번 좌표압축문제를 풀려고 하다가, 일단 좌표압축의 개념부터 알..
좌표 압축 알고리즘 이란?
백준 18870번 좌표압축문제를 풀려고 하다가, 일단 좌표압축의 개념부터 알아야 할 것 같아서 정리해본다. 좌표 압축 알고리즘이란? : 모든 구간이 아니라, 중요한 구간이나, 숫자만 들고있는 기법. → 순위가 중요한 알고리즘에서 입력값의 개수 < 입력값의 범위일때 사용한다. 값보다 값의 순위가 중요하기 때문에, 값을 임의의 값으로 변경하되 순위만 유지하여도 문제를 풀 수 있도록 만드는 것이다. 예시로는 카카오 코드 페스티벌 5번 캠핑 문제가 있는데, 이 경우 좌표 x,y의 범위는 0 ~ 2^31-1 이지만, 입력받는 좌표의 개수는 최대 5000개이다. 만약 입력의 좌표를 그대로 반영하여 문제를 푼다고 하면 배열의 크기가 2^31-1 개가 되어야하며, 2차원이기 때문에 탐색에 너무 많은 시간이 들게 된다...