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

Shorten Time Technique

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

 

LR Technique[왼쪽 오른쪽 순회 기술]

 값을 도출하기 전에 미리 왼쪽을 순회해서 얻은 값, 오른쪽을 순회해서 얻은 값을 구하고 이를 통해서 결과를 도출하여 시간 복잡도를 줄인다.

 

필요성 : 중복되는 계산을 줄일 수 있다. 보통 미리 만든 배열을 통해서 값을 구한다면 시간복잡도가 줄어든다.

 

효용성 : 시간 복잡도가 줄어든다. 물론 여기서도 반복되는 행위에 대한 시간 복잡도는 여전하지만, 반복하는 횟수와 입력된 변수 개수의 곱으로 나타나는 시간복잡도와는 달리 LR 테크닉을 사용하면 더하기로 나타나는 시간복잡도로 변하게 되어 좋다.

 

이걸 언제 써야할지.. 는.. 아직 와닿지 않는다. 문제를 더 풀어봐야할 것  같다. 지금은 기억만 해두자.

 

코드트리 문제

코드트리-마라톤 중간에 택시타기

https://www.codetree.ai/missions/8/problems/taking-a-taxi-in-the-middle-of-the-marathon?&utm_source=clipboard&utm_medium=text 

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

이 문제는 택시 거리를 이용한다. 일반적으로 좌표 간 거리를 구하는 공식과 달리 x축끼리의 거리, y축끼리의 거리를 더한 거리가 거리로 나타나는 택시거리를 이용한다.

 

 문제는 마라톤을 하고 있는데, 체크포인트를 지나가서 마라톤을 완주해야한다. 그런데 마지막 체크포인트를 제외하고(물론 시작점도) 하나의 체크포인트를 생략하고 가려고 한다. 이 때 최소거리를 출력하면 된다.

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int line_num;
    cin >>  line_num;

    vector<pair<int,int>> coor; //coordinate 좌표 넣는 벡터.
    coor.push_back(make_pair(0,0));
    //pair<int,int> coor[line_num];

    //체크포인트 좌표 받기.
    for(int checkpoint_num =1; checkpoint_num<=line_num;checkpoint_num++){
        int x,y;
        cin >> x >> y;
        coor.push_back(make_pair(x,y));
    }

    //인덱스 셀 때 1부터, 그렇게 하려고 +1 한 것이당.
    long L[line_num+1];
    long R[line_num+1];
    //거리가 int 형 범위를 넘어설 수 있다. 그래서 더 큰 long 사용하자.


    //여기는 기본 개념을 이용하였다.
    //기본 개념에서는 인접한 숫자간의 차이의 합을 구하는데
    //여기 문제에서는 인접한 좌표간의 차이의 합을 구하는 것.

    //따라서, 추가할 것은 x좌표,y좌표에의 차이의 합, 즉 택시 거리로 바꿔주면 된다.

    //==========================================================================//


    //L,R배열은 1번부터 N번까지 체크포인트의 택시거리의 합이 전부 구해져있다.
    //L에서 인덱스 1인 시작이므로 0의 값, 2부터는 체크포인트[1~2]거리, 3은 체크포인트[1~3]거리, 4는 체크포인트[1~4] ...
    //R은 L의 역방향으로 배열이 정렬되어 있다.

    L[1]=0;
    for(int index=2;index<=line_num;index++){
        L[index] = L[index-1] + (abs(coor[index].first - coor[index-1].first)+abs(coor[index].second - coor[index-1].second));
    }

    R[line_num] =0;
    
    for(int id = line_num - 1; id >= 1;id--){
        R[id] = R[id+1] + (abs(coor[id+1].first - coor[id].first)+abs(coor[id+1].second - coor[id].second));
    }
    //기본 개념 끝.

    //최소 거리 설정ㅡ 모든 거리를 다 더해 넣은 게 초기값.
    long min_d=0;
    for(int id= 1; id<=line_num;id++){
        min_d+=L[id];
        //cout << min_d<<'\n';
    }
    

    //체크포인트가 1~6번까지 있는데
    //체크포인트 4번을 건너뛴다고 가정하면,

    //체크포인트[1~3]를 구하고, 체크포인트 [5~6]을 먼저 구하자.
    //      L                         R
    //이건 위에서 만드는 배열을 통해서 값을 구할 수 있다.

    //이제, 체크포인트 3에서 5로 바로 가야하므로, 아래 for문의 abs가 포함된 수식이 
    //3번 체크포인트와 5번 체크포인트의 택시거리를 구하는 식이다.


    long taxi[line_num+1];
    for(int id=2;id<line_num;id++){
        taxi[id]=L[id-1]+R[id+1] + (abs(coor[id+1].first - coor[id-1].first)+abs(coor[id+1].second - coor[id-1].second));
        min_d=min(min_d, taxi[id]);
    }
    cout << min_d << '\n';

    return 0;
}

 여기서 먼저 체크포인트 간 거리를 배열에 모두 넣는다. 그것을 수행하는 것이 LR테크닉이다. 인접한 두 체크포인트 숫자의 차이의 합을 구한다.

 

i번 째의 체크포인트를 제외하고 거리를 생각한다고 해보자.

 

 L배열에는 첫 번째부터  i번째의 거리의 합이 구해져 있고, R배열에는 i번부터 마지막 체크포인트까지의 거리의 합이 구해져있다. 그러면 이 두 개를 더하고, 생략된 체크포인트 이전과 이후의 거리 합만 더해주면 그것이 [i번째 체크포인트를 생략한 거리]이다.

 

이렇게 LR테크닉을 이용할 수 있다. 나머지는 주석을 따라가면 풀 수 있다.

 

글꼬리

 LR테크닉을 이용해서 문제를 풀었을 때는 어떤 방식으로 사용할지 와 닿는다만 어떤 때에 사용할지는 아직 모르겠다. 일단 테크닉을 통해서 시간복잡도도 줄이고 코딩도 조금은 분할되어 보기 쉬워지는 느낌이다. 테크닉을 잘 알아두자.