By Standing On The Shoulders Of Giants

개념

좌표자체를 배열의 idx로 활용하는 경우가 많다.

하지만 불가능한 경우가 있다.

- 음수좌표 --> 범위가 너무 넓음에 포함됨

- 범위가 너무 넓음

결국 좌표의 범위가 너무 넓어 배열에 다 담을 수 없을 때

주어진 좌표만을 사용하도록 하기 위한 방법이 좌표 압축이다.

좌표압축 알고리즘

1. 좌표 저장 - 입력순서(idx), 좌표(pos)

2. 좌표 정렬 - 좌표(pos) 기준, 좌표같을 땐 입력(idx) 기준

3. 좌표 압축

코드

void compression() {
	int before = arr[0].pos;
	int cnt = 0;
	answer[arr[0].idx] = 0;
 
	for (int i = 0; i < N; i++) {
		if (before != arr[i].pos) {
			before = arr[i].pos;
			cnt++;
		}
		answer[arr[i].idx] = cnt;
	}
}
int main() {
	scanf("%d", &N);
 
	//1. 좌표 저장(idx,pos)
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i].pos);
		arr[i].idx = i;
	}
	
	//2. 좌표 정렬
	mSort(0, N - 1);
	
	//3. 좌표 압축
	compression();
 
	for (int i = 0; i < N; i++)
		printf("%d ", answer[i]);
	return 0;
}

예제

www.acmicpc.net/problem/18870

1. 두개의 형태

재귀함수의 구조는 다음과 같이 두개의 형태를 띈다.

1) 재귀호출 후 동작

2) 동작 후 재귀호출

1) 호출 후 동작

 - bottom up

 - 마지막 -> 처음으로 동작

2) 동작 후 호출

 - top down

 - 처음 -> 마지막으로 동작

2. 예시_호출 후 동작 : MergeSort

작은 단위에서부터 시작하여 큰 단위로 끝난다.

3. 예시_동작 후 호출 : QuickSort

큰 단위에서 시작해서 작은단위로 끝난다.