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만인 것을 이용합니다.

 

로직의 진행 순서입니다.

  1. 우선 입력을 받을 때, 원래 배열 순서를 유지해야 하므로 인덱스도 함께 저장합니다.
  2. 배열을 좌표를 기준으로 오름차순 정렬합니다.
  3. 이전 값을 사용하기 위한 pre와 압축된 값을 위한 cnt 변수를 선언, 초기화합니다.
  4. N만큼 for문을 돌면서 pre와 list[i] 값을 비교합니다.
  5. pre == list[i]이면 이전에 등장했던 수가 있으므로 cnt를 유지합니다.
  6. pre != list[i]이면 다른 수가 등장했으므로 cnt를 1 증가합니다.
  7. pre를 현재 좌표값으로 갱신하고, list[i]에 cnt를 넣어줍니다.
  8. 압축된 배열을 원래 배열 순서로 돌리기 위해 1번에서 저장했던 인덱스를 기준으로 오름차순 정렬합니다.

이렇게 되면

2 4 -10 4 -9

이었던 좌표가

2 3 0 3 1

이렇게 변환되는 것을 볼 수 있습니다.

 

 

이 방법 외에 unique를 이용하는 방법도 있습니다.

두 개의 벡터를 사용하며, 하나는 원래 벡터, 하나는 정렬하여 중복을 제거한 벡터로 사용됩니다.

중복을 제거한 후 lower_bound를 적용하면 원래 벡터에서 값의 순서를 알 수 있습니다.

 

원래 벡터를 w, 중복을 제거한 벡터를 v라고 했을 때,

로직의 진행 순서로는

  1. 입력 받은 값을 벡터 2개에 같이 넣어줍니다.
  2. 벡터 v를 오름차순으로 정렬합니다.
  3. erase와 unique를 이용하여 정렬된 벡터 v에서 중복을 제거합니다.
  4. 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

정렬 알고리즘은 N개의 숫자를 기준에 맞게 오름차순 or 내림차순으로 정렬하는 알고리즘입니다.

종류가 다양하게 있지만 이 글에서는 선택, 버블, 삽입, 병합, 퀵 정렬만 정리하려고 합니다.

그리고 오름차순 정렬만 정리하였습니다.

 

1. 선택 정렬 (Selection Sort)

선택 정렬은 현재 위치에 들어갈 수를 찾으면서 정렬하는 알고리즘입니다.

 

1. 선택한 인덱스부터 N까지 가장 작은 값을 찾습니다.

2. 가장 작은 값과 선택한 값을 서로 바꿉니다.

3. 이 과정을 N - 1번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
void selectionSort() {
    for (int i = 0; i < N - 1; i++) {
        int minidx = i;
        for (int j = i + 1; j < N; j++) {
            if (list[minidx] > list[j]) {
                minidx = j;
            }
        }
        int tmp = list[minidx];
        list[minidx] = list[i];
        list[i] = tmp;
    }
}
 cs

 

 

2. 버블 정렬 (Bubble Sort)

버블 정렬은 연속된 2개의 수를 비교하여 정렬하는 알고리즘입니다.

정렬 과정에서 가장 큰수를 맨뒤로 보내는 방식입니다.

 

1. 두 번째 인덱스부터 바로 이전의 인덱스와 값을 비교합니다. (list[idx], list[idx - 1])

2. list[idx - 1] > list[idx]이면 두 수를 바꿉니다.

3. 아니면 다음 인덱스를 확인합니다.

4. 이 과정을 N번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

 

선택 정렬은 앞에서부터 작은 수가 결정되는 방식이지만

버블 정렬은 뒤에서부터 큰 수가 결정되는 방식입니다.

1
2
3
4
5
6
7
8
9
10
11
void bubbleSort() {
    for (int i = 0; i < N; i++) {
        for (int j = 1; j < N - i; j++) {
            if (list[j - 1] > list[j]) {
                int tmp = list[j];
                list[j] = list[j - 1];
                list[j - 1] = tmp;
            }
        }
    }
}
 cs

 

 

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 현재 위치에서 이전의 값들을 비교하여 자신이 들어갈 위치를 찾아들어가는 정렬 알고리즘입니다.

 

1. 현재 인덱스에서 왼쪽으로 이동하면서 값을 비교합니다.

2. tmp보다 작은 수가 나올 때까지 수들을 한칸 옮겨줍니다.

3. tmp보다 작은 수가 나오면 그 다음 자리에 tmp를 넣어줍니다.

4. 이 과정을 N - 1번 반복합니다.

 

이 알고리즘의 시간복잡도는 최선 : O(N), 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertionSort() {
    for (int i = 1; i < N; i++) {
        int tmp = list[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (list[j] > tmp) {
                list[j + 1] = list[j];
            }
            else
                break;
        }
        list[j + 1] = tmp;
    }
}
 cs

 

 

4. 병합 정렬 (Merge Sort)

병합 정렬은 배열을 반씩 분할해가면서 정렬하는 알고리즘입니다.

시간적으로는 효율적이나 메모리를 배열의 2배 사용해야하는 단점이 있습니다.

 

1. 배열을 가장 작은크기까지 분할합니다.

2. 분할된 배열끼리 정렬합니다.

3. 분할된 배열을 다시 합쳐서 합친 배열을 다시 정렬합니다.

4. 이 과정을 반복합니다.

 

과정 예시)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}


[배열을 분할합니다.]
N = 8    {4, 5, 8, 2, 6, 1, 7, 3}
    

N = 4    {4, 5, 8, 2}    {6, 1, 7, 3}


N = 2    {4, 5}    {8, 2}    {6, 1}    {7, 3}


N = 1    {4}    {5}    {8}    {2}    {6}    {1}    {7}    {3}


[배열을 병합하는 과정에서 정렬합니다.]
N = 1    {4}    {5}    {8}    {2}    {6}    {1}    {7}    {3}


N = 2    {4, 5}    {2, 8}    {1, 6}    {3, 7}


N = 4    {2, 4, 5, 8}    {1, 3, 6, 7}


N = 8    {1, 2, 3, 4, 5, 6, 7, 8}

 

정렬로직 설명)
 
분할된 두 개의 배열에서 가장 작은 값들끼리 비교하여 작은 값을 새로운 배열에 넣습니다.
arr1: {2, 4, 5, 8}    arr2: {1, 3, 6, 7}    sorted: {}
arr1 or arr2의 숫자를 모두 고를때까지 반복합니다.


arr1: {2, 4, 5, 8}    arr2: {1, 3, 6, 7}    sorted: {}
arr1[i] = 2
arr2[j] = 1


arr1: {2, 4, 5, 8}    arr2: {3, 6, 7}    sorted: {1}
arr1[i] = 2
arr2[j] = 3


arr1: {4, 5, 8}    arr2: {3, 6, 7}    sorted: {1, 2}
arr1[i] = 4
arr2[j] = 3


arr1: {4, 5, 8}    arr2: {6, 7}    sorted: {1, 2, 3}
arr1[i] = 4
arr2[j] = 6


arr1: {5, 8}    arr2: {6, 7}    sorted: {1, 2, 3, 4}
arr1[i] = 5
arr2[j] = 6


arr1: {8}    arr2: {6, 7}    sorted: {1, 2, 3, 4, 5}
arr1[i] = 8
arr2[j] = 6


arr1: {8}    arr2: {7}    sorted: {1, 2, 3, 4, 5, 6}
arr1[i] = 8
arr2[j] = 7


arr1: {8}    arr2: {}    sorted: {1, 2, 3, 4, 5, 6, 7}
여기서 arr2의 숫자를 모두 골랐으니 arr1의 남은 숫자를 sorted의 뒤에 붙여주면 됩니다.


arr1: {}    arr2: {}    sorted: {1, 2, 3, 4, 5, 6, 7, 8}

 

이 알고리즘의 시간복잡도는 최선, 최악 : O(NlogN)이고, 공간복잡도는 O(N * 2)입니다.

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
void merge(int l, int m, int r) {
    int i = l;
    int j = m + 1;
    int k = l;
 
    while (i <= m && j <= r) {
        if (list[i] < list[j])
            sorted[k++] = list[i++];
        else
            sorted[k++] = list[j++];
    }
 
    if (i > m) {
        for (int t = j; t <= r; t++, k++) {
            sorted[k] = list[t];
        }
    } else {
        for (int t = i; t <= m; t++, k++) {
            sorted[k] = list[t];
        }
    }
 
    for (int t = l; t <= r; t++)
        list[t] = sorted[t];
}
 
void mergeSort(int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(l, m);
        mergeSort(m + 1, r);
        merge(l, m, r);
    }
}
 cs

 

 

 

5. 퀵 정렬 (Quick Sort)

배열에서 피봇을 선택해 피봇보다 작은 원소를 왼쪽에, 큰 원소를 오른쪽에 옮겨지고

피봇을 기준으로 피봇을 제외한 왼쪽, 오른쪽 원소들을 다시 정렬해나가는 알고리즘입니다.

 

과정 예시)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
피봇은 배열의 첫번째 요소로 지정합니다.


list[] = {4, 5, 8, 2, 6, 1, 7, 3}
pivot = 0
i = 1
j = 0


list[] = {4, 2, 8, 5, 6, 1, 7, 3}
pivot = 0
i = 3
j = 1


list[] = {4, 2, 1, 5, 6, 8, 7, 3}
pivot = 0
i = 5
j = 2


list[] = {4, 2, 1, 3, 6, 8, 7, 5}
pivot = 0
i = 7
j = 3


list[] = {3, 2, 1, 4(fix), 6, 8, 7, 5}


이후에 피봇 기준 왼쪽 오른쪽 배열{3, 2, 1}과    {6, 8, 7, 5}도 똑같은 로직을 반복합니다.

 

정렬로직 설명)
 
list[] = {4, 5, 8, 2, 6, 1, 7, 3}
pivot : 0
i = 1
j = 0


list[i]와 list[pivot]을 비교합니다.
list[i] < list[pivot]이면 j를 1증가하고, list[i]와 list[j]를 바꿉니다.
이를 i = 1부터 끝까지 반복합니다.


그럼 최종적으로
list[] = {4, 2, 1, 3, 6, 8, 7, 5} 라는 배열이 만들어집니다.
여기서 pivot은 여전히 0이고
j는 3입니다.


그럼 list[pivot]과 list[j]를 바꿉니다.
=> list[] = {3, 2, 1, 4(fix), 6, 8, 7, 5}
이제 4의 위치는 정해졌으며 이를 기준으로 왼쪽 배열과 오른쪽 배열도 같은 로직을 반복합니다.

 

이 알고리즘의 시간복잡도는 최선 : O(NlogN), 최악 : O(N^2)이고, 공간복잡도는 O(N)입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int partition(int pivot, int l, int r) {
    int j = pivot;
    for (int i = pivot + 1; i <= r; i++) {
        if (list[pivot] > list[i]) {
            swap(list[++j], list[i]);
        }
    }
    swap(list[pivot], list[j]);
    
    return j;
}
 
void quickSort(int l, int r) {
    if (l < r) {
        int pivot = partition(l, l, r);
        quickSort(l, pivot - 1);
        quickSort(pivot + 1, r);
    }
}
 cs

 

'algorithm > Theory' 카테고리의 다른 글

좌표 압축 (Coordinate Compression)  (2) 2022.08.24

+ Recent posts

티스토리툴바