3년전에 대학 과제로 좌표 압축 기법을 활용하는 문제가 나왔었지만 이해를 못해서 풀지 못했습니다.
지금와서 보니 생각보다 간단했고, 정리하면서 포스팅합니다.
우선 좌표압축이란, 수의 범위가 크게 주어질 때 인덱스를 이용하여 범위를 줄이는 기법입니다.
코테에서 요구하는 기법은 아닐지라도 대회 준비를 하셨던 분이라면 보신 적이 있을 거라고 생각합니다.
그만큼 PS에서 많이 사용되는 기법이며, 한 번쯤 알아가는 것도 괜찮은 것 같습니다.
1차원 배열
https://www.acmicpc.net/problem/18870
18870번: 좌표 압축
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌
www.acmicpc.net
이 문제가 가장 기본적으로 좌표 압축을 체험해볼 수 있는 문제입니다.
1차원 좌표를 압축하는 것이 문제에서 요구하는 것인데, 좌표의 범위가 -10억 ~ 10억입니다.
이 범위를 한번씩 돌며 순위를 부여하는데 너무 많은 시간이 필요합니다.
이를 해결하기 위한 기법이 좌표 압축입니다.
좌표의 범위는 -10억 ~ 10억이지만 N의 범위는 1 ~ 100만인 것을 이용합니다.
로직의 진행 순서입니다.
- 우선 입력을 받을 때, 원래 배열 순서를 유지해야 하므로 인덱스도 함께 저장합니다.
- 배열을 좌표를 기준으로 오름차순 정렬합니다.
- 이전 값을 사용하기 위한 pre와 압축된 값을 위한 cnt 변수를 선언, 초기화합니다.
- N만큼 for문을 돌면서 pre와 list[i] 값을 비교합니다.
- pre == list[i]이면 이전에 등장했던 수가 있으므로 cnt를 유지합니다.
- pre != list[i]이면 다른 수가 등장했으므로 cnt를 1 증가합니다.
- pre를 현재 좌표값으로 갱신하고, list[i]에 cnt를 넣어줍니다.
- 압축된 배열을 원래 배열 순서로 돌리기 위해 1번에서 저장했던 인덱스를 기준으로 오름차순 정렬합니다.
이렇게 되면
2 4 -10 4 -9이었던 좌표가
2 3 0 3 1이렇게 변환되는 것을 볼 수 있습니다.
이 방법 외에 unique를 이용하는 방법도 있습니다.
두 개의 벡터를 사용하며, 하나는 원래 벡터, 하나는 정렬하여 중복을 제거한 벡터로 사용됩니다.
중복을 제거한 후 lower_bound를 적용하면 원래 벡터에서 값의 순서를 알 수 있습니다.
원래 벡터를 w, 중복을 제거한 벡터를 v라고 했을 때,
로직의 진행 순서로는
- 입력 받은 값을 벡터 2개에 같이 넣어줍니다.
- 벡터 v를 오름차순으로 정렬합니다.
- erase와 unique를 이용하여 정렬된 벡터 v에서 중복을 제거합니다.
- N만큼 for문을 돌면서 lower_bound를 이용하여 w[i] 값의 압축된 값을 가져옵니다.
간단해 보이지만 위의 문제에서는 첫 번째 방법이 메모리, 시간 부분에서 효율적인 것을 알 수 있습니다.
간단하게 소스도 첨부합니다.
첫 번째 방법
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;
typedef pair<int, int> pii;
pii list[MAX];
int N;
void func() {
sort(list, list + N);
int pre = 1e9 + 1;
int cnt = -1;
for (int i = 0; i < N; i++) {
if (pre != list[i].first) cnt++;
pre = list[i].first;
list[i].first = cnt;
}
sort(list, list + N, [](pii a, pii b) {
return a.second < b.second;
});
for (int i = 0; i < N; i++) {
cout << list[i].first << ' ';
}
cout << '\n';
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> list[i].first;
list[i].second = i;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
두 번째 방법
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 1000000
using namespace std;
vector<int> v, w;
int N;
void func() {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 0; i < N; i++) {
cout << lower_bound(v.begin(), v.end(), w[i]) - v.begin() << ' ';
}
cout << '\n';
}
void input() {
int x;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> x;
v.push_back(x);
w.push_back(x);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
2차원 배열
https://www.acmicpc.net/problem/10167
10167번: 금광
첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이
www.acmicpc.net
이 문제는 좌표 압축만을 요구하지는 않지만 2차원 배열 좌표압축을 해야하는 문제입니다.
세그먼트 트리처럼 구간 쿼리를 사용하는 문제에 좌표 압축을 적용할 수 있어 이 문제를 가져왔습니다.
전체 풀이는 추후 포스팅할 예정이고, 좌표 압축에 해당하는 부분만 진행하려고 합니다.
사실 2차원 배열 압축은 위 방법들을 그대로 사용하면 됩니다.
1차원 배열에 적용했던 것들을 두 번 적용하는 것입니다.
이 문제도 첫 번째 방법이 좀더 효율적으로 나왔습니다.
두 번째 방법이 더 간단할 수 있지만 저는 첫 번째 방법을 쓸 것 같습니다.
이 문제는 좌표 압축 코드만 첨부합니다.
첫 번째 방법
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
void func() {
sort(list + 1, list + 1 + N, [](Point a, Point b) {
return a.x < b.x;
});
int pre = 1e9 + 1;
int xCnt = 0;
for (int i = 1; i <= N; i++) {
if (pre != list[i].x) xCnt++;
pre = list[i].x;
list[i].x = xCnt;
}
sort(list + 1, list + 1 + N, [](Point a, Point b) {
return a.y < b.y;
});
pre = 1e9 + 1;
int yCnt = 0;
for (int i = 1; i <= N; i++) {
if (pre != list[i].y) yCnt++;
pre = list[i].y;
list[i].y = yCnt;
}
}
|
cs |
두 번째 방법
|
1
2
3
4
5
6
7
8
9
10
11
12
|
void func() {
sort(xtmp.begin(), xtmp.end());
xtmp.erase(unique(xtmp.begin(), xtmp.end()), xtmp.end());
sort(ytmp.begin(), ytmp.end());
ytmp.erase(unique(ytmp.begin(), ytmp.end()), ytmp.end());
for (int i = 1; i <= N; i++) {
list[i].x = lower_bound(xtmp.begin(), xtmp.end(), list[i].x) - xtmp.begin() + 1;
list[i].y = lower_bound(ytmp.begin(), ytmp.end(), list[i].y) - ytmp.begin() + 1;
}
}
|
cs |
'algorithm > Theory' 카테고리의 다른 글
| 정렬 알고리즘 (Sort Algorithm) [선택, 버블, 삽입, 병합, 퀵] (2) | 2021.04.15 |
|---|
