[코드트리] Intermediate Mid - Shorten Time Technique[Grid Compression]

Shorten Time Technique

문제 해결 방식의 시간복잡도를 줄이는 기술이다.

 

Grid Compression[좌표 압축]

입력으로 받거나 이미 주어진 수의 범위를 압축하는 것이다. (빈 공간이 없도록 압축)

 

 쉬운 예시로 총 1~ 20의 범위를 갖게 되는 수열 1, 3, 5 ,7 ,13, 20 이 주어져있다. 이것을 압축 시켜서 [1]-1, [2]-3, [3]-5, [4]-7, [5]-13, [6]-20 으로 변환 하여, 1,2,3,4,5,6 으로 압축시키고, 압축시킨 것에서 5번을 선택하면 13의 값을 반환하도록 한다.

---

필요성 : 예를 들어 원소가 갖는 범위가 1~1,000,000,000 이라고 하자. 다만, 배열에서 있는 것은 1, 2, 7 , 9 , 102, 10000000 이렇게 있다고 가정하자. 수의 범위만큼의 배열을 만드는 것은 너무 메모리를 크게 사용하며, 나중에 이 배열을 이용할 때, 모든 원소를 순회하고자 한다면 너무 긴 시간이 걸린다.

 

또한, 그래프를 생각해보자. 우리는 인접리스트나 인접행렬을 통해서 그래프를 확인하는데, 만약 수의 범위가 크지만 갖게 되는 수들이 촘촘하게 연속되어 있지 않고 듬성듬성하다면 압축하는 편이 메모리, 시간 복잡도 면에서 유용하다.

 

극한적으로 생각하면, 1~2,000,220 의 범위를 갖는 4개의 노드가 있다. 1과 4와 2,000,220의 노드에 대한 그래프를 만든다면, 우리의 인접 행렬과 인접리스트는 정말 크게 만들어질 것이다. 또한 노드 간 연결을 확인하려고 할 때 for문을 사용한다면 그 시간복잡도 또한 너무 클 것이다. 

 

그러니까 공간, 시간복잡도를 줄여주기에 필요하다.

 

효용성 : 아까 예시로 든 1과 4와 2,000,220의 노드를 생각해보자. 좌표 압축으로 맵을 만드는데 1번에는 1, 2번에는 4, 3번에 2,000,220의 값이 매핑되고, 1,2,3을 압축하여 인접 리스트나 인접 행렬을 만든다. 나중에 노드의 원래 값을 갖고 오라면 매핑을 통해서 바로 꺼내올 수 있다. 

 

---

코드트리 문제

점 개수 세기 3

https://www.codetree.ai/missions/8/problems/count-number-of-points-3?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이 문제는 입력받은 n개의 점이 입력으로 받게 될 범위 내에 총 몇 개가 들어있는지 파악하는 문제이다. 여기서 입력은 값이 n개 받게 되고, q개의 질문을 통해서 일반적으로 접근해서 값을 조사한다면 시간 복잡도는 O(q*n)이 될 것이다.

 

범위 내에 n개의 점이 얼마나 있는지 for문으로 확인한다면 이중 반복문(q번의 테스트케이스를 수행+n개의 점이 범위 내에 얼마나 있는 지 순회 for문 수행)으로 위와 같은 시간 복잡도가 도출된다.

 

하지만 여기서는 그렇게 하면 바로 시간초과가 걸리게 된다. 우리는 시간복잡도를 좌표 압축으로 줄여나가야 한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <utility>


using namespace std;


int main() {
    int N,K; //N개의 숫자 점, K개의 문제 개수
    int x,y; //양 끝 점을 저장할 x,y

    cin >> N;
    cin >> K;

    int count =0; //범위 내 점의 개수
    vector<int> points; // N개의 점의 좌표 저장하는 배열
    vector<pair<int,int>> v; //양 끝 점 범위를 저장하는 pair 셋을 저장하는 배열~

    for(int input_index=0; input_index<N;input_index++){
        int point;
        cin >> point;
        points.push_back(point);
    }

    //해쉬맵에다 다 옮겨 버리자.
    //여기서 질의에 대한 점에 해당하는 위치에 항상 점이 놓여있다고 했으니까 쉽다.
    //그렇지 않았다면 결국 시간 복잡도는 그대로 O(N*Q)였겠지.
    unordered_map<int, int> mapper;
    int cnt = 1;
    for(vector<int>::iterator it = points.begin(); it != points.end(); it++) {
        mapper[*it] = cnt;
        //cout << *it << " -> " << cnt << endl;

        cnt++;
    }

    pair<int,int> edges[K]; //양 끝 점 좌표 저장한 페어, (x,y)

    for(int i=0;i<K;i++){
        cin >> x;
        cin >> y;
        v.push_back(make_pair(x,y));
    }

    //질의에 대해서 양 끝 점 저장.
    //2중 반복문으로 하니 시간 복잡도가 O(N*Q)가 나와서 시간초과가 떠버린다. 숫자 개수 * 질의 개수가 10만*10만이라 그런갑다.

    
    //특수한 경우는 범위 숫자가 모두 동일할 경우 점 개수는 1개 if문

    //범위 숫자가 양 끝을 가리키고 있을 경우에는 점 개수는 N개 else-if문

    //else문
    //기본개념에서 알려준 것처럼 해쉬맵에 넣고, 해쉬 키, 밸류를 통해서 바로 인덱스 갖고 오고,
    //그 인덱스가 숫자 범위 내에 몇 개나 더 있는지 알려주는 간접 정보가 되니까
    //그 인덱스를 end에서 start 빼고 +1 해주자.

    for(int quest=0;quest<K;quest++){
        if(v[quest].first==v[quest].second){
            cout << 1 << '\n';
        }else if(v[quest].first==points[0] && v[quest].second==points[N-1]){
            cout << N << '\n';
        }else{
            int result;
            result = mapper[v[quest].second] - mapper[v[quest].first]+1;
            cout << result << '\n';
        }
    }
    
    return 0;
}

 문제의 가정 : 범위가 되는 수에 해당하는 위치에는 무조건 점이 있다.

즉, 우리가 입력받은 n개의 수에서 범위가 결정된다는 것이다. 그러므로 범위의 값이 새롭지 않으므로 좌표 압축을 하기 편하다.(범위의 값이 새로운 값이 아니므로 고려할 것이 줄어든다.)

 

우리가 입력받은 수 n개를 해시 맵으로 좌표압축을 실시한다. 

 

q개의 질문에서 들어오는 범위 값을 해시 맵에서 찾아서 인덱스를 반환하면 끝이다.

[오른쪽 범위의 값을 통해 갖고 온 인덱스]-[왼쪽 범위의 값을 통해 갖고 온 인덱스]+1 이 바로 우리가 찾는 범위 내 점의 개수이다.

 

(이해가 안 된다면 직접 그려보자. 배열을 만들고 특정 값과 또 다른 특정 값 사이에 있는 수가 얼마나 있는지 - 물론 그린 것은 배열이 아닌 맵이라고 생각하고 인덱스 접근 말고 키-밸류 접근이라고 생각하자.)

 

따라서 모든 범위를 순회하지 않아서 시간 복잡도는 O(q)가 걸리게 된다. 물론 해시 맵을 만들 때 O(n)도 있지만, O(q*n)보다는 작다.

 

글꼬리

좌표 압축은 개념은 직관적이지만 이걸 직접 문제에 적용하려니 어떤 부분으로 다가가야할 지 조금은 어렵다. 위의 문제도 그렇다. 문제의 가정이 없었다면 조금 어려웠을 것 같다. 물론 맵을 통해서 압축하는 것은 시간복잡도를 줄여주는 데 도움이 클 것 같다.