알고리즘 문제 접근 과정 3

이번 포스트에서도 ‘알고리즘 문제 접근 방법 1, 2’에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다.

최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다.

보석 - Taejon Asia Regional 2001 B번

관찰

금강석의 수를 최대화하기 위해서는, 팔 수 있는 모든 땅을 다 한 번씩 파 몇 개를 얻을 수 있는지 기록한 다음에, 그 중 가장 많이 캘 수 있었던 금강석의 수를 알아내면 됩니다.

가장 쉬운 방법으로는 실제로 파볼 수 있는 모든 영역을 지정하여, 그 안에 속한 금강석의 수를 세는 방법입니다. 지도는 총 $N * M$개의 격자가 있기 때문에, 우리가 확인해야하는 영역은 최대 $(N - K + 1) * (M - K + 1)$ 만큼의 땅을 파는 경우의 수들이 있고, 이 때의 영역마다 $T$개의 금강석에 대해 각각 이 영역에 포함되는지를 판단해주면 됩니다.

하지만 이 경우는, $K$가 1일 경우에 총 $N * M$번 땅을 파야하고, 우리는 $T$개의 금강석을 모두 보기 때문에 최악에 $O(NMT)$가 걸리는 방법이 됩니다. 지도의 크기가 충분히 작다면 이를 이용해서 해결할 수 있지만, 우리는 좀 더 나은 방법을 통해 더 빠르게 해결해야합니다.

우리는 앞서 다뤘던 내용을 통해 모든 경우를 해보면서, 더 빠르게 해결할 수 있습니다. 한 번 주어진 금강석들의 위치는 우리가 어디에 있는 땅을 파도 변하지 않습니다. 이 성질을 이용해서, 특정 영역에 속해있는 금강석의 수를 쉽게 구할 수 있을까요?

이전에 배웠던 ‘이차원 구간합’을 계산할 수 있는 표를 미리 작성한다면, 우리는 특정 구간에 있는 금강석의 수를 쉽게 구할 수 있습니다.

$A[i, j] = (i, j)에 있는 금강석의 수$

라고 정의할 경우, 우리는 $T$개의 금강석이 각각 $x_{i}, y_{i}$ 좌표를 가질 때, $A[x_{i}, y_{i}]$를 1 증가시키는 것으로 $A$ 배열을 모두 채워줄 수 있습니다.

이제 구간합을 구하기 위해 다음과 같이 $S[i, j]$를 정의해봅시다.

$S[i, j] = (0, 0)부터 (i, j) 사이에 있는 금강석의 수)$

이 때, 우리가 $i$를 0부터 $1$씩 증가해가고, 같은 $i$에 대해 $j$를 0에서부터 증가시킨다면

$S[i, j] = S[i - 1, j] + S[i, j - 1] - S[i - 1, j - 1] + A[i, j]$

를 통해 $S$ 배열을 모두 채워줄 수 있습니다.

이렇게 모든 $S$ 배열을 채워주게 된다면, 우리는 $(a, b)부터 (c, d) 사이에 있는 금강석의 수$는

$S[c, d] - S[c, b - 1] - S[a - 1, d] + S[a - 1, b - 1]$

이 곧 금강석의 수가 됨을 이용하여 $O(1)$에 구해줄 수가 있습니다. 이를 통해 특정 정사각형이 결정되면, 금강석의 수는 바로 구해줄 수가 있어, 시간복잡도는 정사각형을 결정하고, $S$배열을 채우는데 드는 시간인 $O(NM)$으로 줄어들게 됩니다.

하지만 아직까지도 지도는 굉장히 클 수가 있습니다. 우리는 이 시간복잡도도 더 빠르게 만드는 방법을 찾아야합니다.

풀이

우리에게 문제가 되는 부분은, 지도상에 있는 금강석의 수는 적을 수 있는 반면에, 지도 자체는 굉장히 클 수 있다는 점입니다. 그렇기에 우리가 땅을 파는 과정에서, 꼭 살펴보지 않아도 되는 쓸모없는 땅들(이미 이보다 더 많은 금강석을 포함하는 땅을 찾은 경우)을 너무 많이 확인하게 됩니다. 하지만 우리는 어떤 땅들이 쓸모없는 땅인지를 알아내기가 쉽지 않습니다. 그렇기에, 우리는 우리가 알 수 있는 특별한 경우에 포함되는 일부 땅들을 살펴보는 것으로, 더 빠르게 해결하는 방법을 생각해봐야 합니다.

다음과 같은 땅을 팠을 때를 생각해 봅시다.

우리는 위 정사각형이 지도에서 가장 최대가 되는 사각형이라는 사실을 알고 있습니다만, 현재 우리가 빨간색 땅을 파서 5개의 금강석을 캘 수 있다는 사실을 아는 상태에서, 나머지 격자에는 금강석이 어디에 존재하는지 모른다고 가정해봅시다.

이 때, 우리는 정사각형을 옮겨서 ‘확실히 현재 영역보다 더 좋은 결과를 내는 정사각형’을 만들 수 있을까요? 정사각형을 살펴보면, 윗변과 왼쪽, 오른쪽 변은 모두 금강석을 포함하고 있기 때문에 이를 이동시키면 항상 1개의 금강석을 손해보게 됩니다. 이 때, 옮긴 위치에 금강석이 없다면 우리는 더 안좋은 방향으로 이동시킨 꼴이 됩니다.

파란색과 초록색 정사각형 모두 하나의 금강석을 잃어 포함한 금강석이 4개로 줄어듭니다.

하지만 아랫변은 하나의 금강석도 포함시키고 있지 않습니다. 그러면 이 붉은 정사각형을 위로 1칸 옮겨보도록 하겠습니다.

초록색 범위의 금강석 5개는 모두 포함하면서, 아무것도 없는 붉은색 빗금영역은 제외하고, 금강석이 더 있을 수 있는 파란색 빗금영역이 추가됩니다.

옮긴 정사각형은 아직도 5개의 금강석을 포함하고 있지만, 추가로 위로 1칸만큼의 직사각형을 더 포함하게 되었습니다. 만약 여기에 1개 이상의 금강석이 존재한다면, 이는 현재 우리가 구한 답보다 더 좋은 답이 될 것입니다.

이를 통해 알 수 있는 점은, 우리가 가진 정사각형의 특정 변이 아무 금강석도 포함하고 있지 않다면, 그 반대 방향으로 이동시켰을 때 더 좋은 답을 얻을 수 있다는 것입니다. 우리는 이를 이용해, 우리가 확인할 모든 정사각형을 ‘왼쪽 변 윗 변이 모두 금강석에 닿아있는 정사각형’ 만 확인하게 된다면 우리가 구하고자 하는 답을 똑같이 구할 수 있습니다. (왼쪽, 혹은 윗변이 금강석과 닿아있지 않을 경우, 각각 반댓 방향으로 칸을 옮기면 더 좋은 답이 됩니다.) 그렇다면, 어떻게 금강석과 닿아있는 정사각형을 모두 구할 수 있을까요?

금강석은 각각 $x, y$좌표를 하나씩 가지고 있고, 금강석은 총 $T$개가 있습니다. 즉, 이 $T$개의 좌표에 속하지 않는 점들은 각각 아래, 혹은 오른쪽으로 이동하여 하나 이상의 금강석에 닿게 만들 수 있습니다. 정사각형의 왼쪽 위 좌표를 $T$개의 금강석이 가질 수 있는 좌표들로 만들게 된다면, $x$좌표가 $T$개, $y$좌표가 $T$개 있으므로 총 $T^2$개의 정사각형들만 확인하면 된다는 것을 알 수 있습니다.

결국, $T^2$개의 정사각형에 대해 $T$개의 금강석 중 몇 개가 포함되는지 확인하는 것으로 문제를 해결할 수 있고, 총 시간복잡도는 $O(T^3)$으로 충분히 빠른 시간에 해결할 수 있게 됩니다.

추가 풀이

우리에게 주어진 격자의 크기는 굉장히 크지만, 실제로는 $T$개의 금강석이 존재하는 $x, y$ 좌표를 제외하고는 사용할 필요가 없다는 점을 알 수 있었습니다. 이 때, $T * T$ 격자를 만들어주고, 각각의 금강석이 존재하는 좌표에다가 금강석의 갯수가 1개 증가했다는 것을 반영하여 누적합을 계산한다면 어떻게 될까요?

우리가 실제로 확인해야하는 정사각형은 총 $T^2$개만 존재하므로, 각각의 정사각형들에 대해서 모든 금강석을 확인하는 것이 아닌, 특정 영역의 누적합을 구하는 방법을 사용하여 $O(1)$에 해당 영역의 금강석을 알아낼 수 있게 됩니다.

허나 관찰에서 다루었던 것과 격자가 달라졌기 때문에, 누적합을 적용할 때에 직사각형의 $x$축 좌표들과 $y$축 좌표들이 바로 알아낼 수는 없다는 문제가 생깁니다. 이를 해결하기 위해서 two pointer 방법을 사용하여, 직사각형 x축 변으로 사용할 수 있는 구간들과 직사각형의 $y$축 변으로 사용할 수 있는 구간들을 구해놓는 방식으로 전처리를 해주거나 누적합을 구하는 과정에서 수행해줄 필요가 있습니다.

해당 부분에 대해 한 번 생각해보시고 $O(T^2)$으로 해결하는 코드도 구현해보는 것을 추천합니다.

Escaping - Seoul Nationalwide Internet Competition 2020 F번

관찰

우리에게 시간을 고려할 필요가 없다고 생각해봅시다. 매 순간마다, 도둑과 경찰은 각각 1칸씩 동서남북으로 이동이 가능합니다. 즉, 현재 격자에서부터 매 순간 한 칸씩 좌표를 옮겨 움직일 수 있습니다.

만약 도둑의 위치가 $(0, 0)$이고 우리가 이동을 목표로 하는 위치가 $(x, y)$라면, 우리는 $x + y$의 최단 경로로 해당 좌표로 이동할 수 있습니다. 만약 경찰들이 $x + y$ 이하의 시간으로 해당 좌표로 이동하지 못한다면, 우리는 그 좌표로 이동할 동안에는 도둑이 경찰한테 잡히지 않음을 알 수 있습니다.

만약 그 사이에 도둑이 경찰에게 잡힌다면, 중간의 어떤 좌표에서 경찰이 도둑보다 더 이르거나 동시에 도착하는 지점이 존재합니다. 그렇다면 그 지점에서부터 해당 좌표까지 도둑보다 더 빠르거나 같게 이동하는 것이 무조건 존재하므로, 이런 경우는 존재하지 않아 도둑이 경찰에게 잡히지 않습니다.

이를 통해, 우리는 충분히 먼 위치(무한히 먼 위치)를 선정하고, 해당 좌표로 이동하는 동안에 도둑이 다른 경찰들에 의해 잡히지 않는다면, 그보다 더 먼 위치로 계속 이동하면서 도둑이 경찰에게 잡히지 않을 수 있다는 것을 알 수 있습니다. 그러므로, 모든 좌표들 중 경찰이 절대 잡지 못하는 굉장히 먼 좌표를 찾을 수만 있다면, 이를 이용하여 문제를 해결할 수 있습니다.

풀이

앞선 방법으로는 우리가 특별한 위치로 도둑이 이동할 때에, 충분히 멀다고 하는 위치까지 이동한 후에도 도둑이 경찰에 의해 잡히지 않을 때, 도둑이 절대 경찰에게 잡히지 않는다고 이야기 할 수 있었습니다. 허나 여기에는 2가지 맹점이 존재합니다.

어디까지 갔을 때, ‘충분히 멀다’ 라고 말할 수 있는지 불분명합니다. 우리는 무한히 이동한 이후에도 경찰들이 도둑을 잡지 못하는 상황이 와야하는데, 실제로 답을 구하기에 충분한 위치까지 시뮬레이션을 통해 알아내고 이를 정당화하기는 쉽지 않습니다.
‘충분히 멀다’ 라 말할 수 있는 위치가 있다고 해도, 그 위치를 찾아내기까지 너무 오랜 시간이 걸립니다. 멀어지면 멀어질수록, 우리는 답을 구하기 위해 더 많은 위치들을 확인해야합니다.

이러한 두 가지, 시간과 공간에서의 제약으로 인한 문제로, 앞선 방법으로 쉽게 답을 구하기는 어렵다는 것을 알 수 있습니다. 그렇다면, 우리는 어떤 방법을 이용해서 문제를 해결할 수 있을까요?

이를 해결하기 위해서, 원래 도둑이 이동하던 상하좌우로 이동할 때에 생기는 변화에 대해 생각해봅시다.

만약 도둑이 위로 한 칸 이동하게 된다면 어떤 일이 벌어질까요?

어떤 경찰이 도둑보다 위쪽에 존재했다면($y$좌표가 더 컸다면), 도둑과 경찰 사이의 거리는 1 줄어들게 됩니다. 이 때, 경찰은 도둑이 이동한 이후 한 번 더 이동하여 도둑과 경찰 사이의 거리를 1 더 줄이거나, 혹은 가만히 있을 수 있습니다.
어떤 경찰이 도둑보다 아래에 있거나 같은 $y$축 선상에 존재했다면, 도둑과 경찰 사이의 거리는 1 늘어나게 됩니다. 이 때, 경찰은 위로 한칸 다시 이동하여 경찰과 도둑 사이의 거리를 원점으로 만들 수 있습니다.

즉, 경찰이 도둑이 어떤 방향으로 이동할 때에 거리가 줄어들게 된다면, 추가로 거리를 1 더 줄일 수 있고, 거리가 1 늘어나게 된다면 같은 방향으로 이동하여 거리를 원점으로 만들 수 있습니다. 이를 위로 이동하는 것 외에, 모든 방향으로 생각해도, 항상 같은 결과가 나온다는 것을 알 수 있습니다.

결국, 우리는 도둑이 어떤 방향으로 이동할 때, 항상 경찰과의 거리가 줄어들거나 혹은 같은 상태를 유지할 수 있다는 것을 알 수 있습니다. 이를 통해 무한히 이동 가능한지 여부를 어떻게 알 수 있을까요?

우리가 어떤 방향으로 이동할 때, 경찰과의 거리가 줄어든다면, 해당 방향으로 이동한다면 결국 언젠가 잡히게 될까요?

사실 그렇지는 않습니다. 아래의 예시를 보겠습니다.

도둑이 $(0, 0)$ 위치에 있고, 경찰이 $(2, 1)$ 위치에 있다고 해봅시다. 이 때, 우리는 위쪽으로 이동할 경우, 경찰이 왼쪽으로 이동하여 각각 $(0, 1)$과 $(1, 1)$ 위치에 있게 되어 2만큼 가까워짐을 알 수 있습니다. 허나, 이 상태부터는 더 이상 위쪽으로 이동하여 경찰이 도둑을 잡을 수 있는 방법이 없어지게 됩니다.

즉, 도둑이 위쪽으로 이동하고 있을 때, 경찰이 도둑을 잡을 수 있으려면, 경찰과 도둑 사이의 $y$축 좌표의 차$(y_{경찰} - y_{도둑})$가 $x$축 거리보다 항상 더 크거나 같아야만 합니다.

즉, 만약 어떤 경찰이 도둑과의 $y$축 차가 $x$축 거리보다 더 크거나 같다면, 도둑은 위쪽으로 이동할 때에 결국엔 해당 경찰에게 잡힐 수 밖에 없으므로, 도둑은 항상 다른 방향으로 이동해야합니다. 이 때, 다른 방향으로 이동하더라도, 앞선 발견에 의해 해당 경찰과의 거리는 절대로 줄어들지 않습니다.

즉, 우리는 위 조건이 만족하는 경찰이 하나라도 있다면 해당 방향으로의 이동은 결국 잡히는 결과로 이어질 수 밖에 없음을 알 수 있으며, 해당 조건을 만족하는 경찰이 없으면 항상 탈출이 가능합니다.

이를 다른 방향에도 적용하면 어떻게 될까요?

다른 방향들 중 적어도 하나에, 위 조건을 만족하는 경찰이 없다면, 우리는 해당 방향으로 달려서 항상 탈출이 가능함을 알 수 있습니다.

허나 모든 방향에서 조건을 만족하는 경찰이 있다면, 우리는 어떤 방향으로의 이동을 반복해도 결국 경찰과의 거리가 줄어들다가 결국 잡히는 결과로 이어질 수 밖에 없습니다. 우리가 위쪽 방향으로의 이동을 할 때, 왼쪽, 오른쪽, 아래에서 조건을 만족하는 경찰들은 항상 처음과 같은 거리를 유지할 수 있어 변함이 없으며, 위쪽 경찰은 가까워지면서 더 위로 이동하면 결국 잡히게 되기 때문입니다. 다른 방향의 경찰들과의 실질적 거리차이가 없다는 점을 통해, 우리는 이동하던 중간에 다른 방향으로 이동을 바꾸어도 늘 같은 결과를 얻게 됩니다.

결국, 우리는 모든 경찰들에 대해서 동서남북으로 이동하였을 때, 탈출이 가능한지 여부만 거리를 이용해 체크해줄 수 있으며, 한 방향이라도 탈출이 가능하면 탈출 가능, 그렇지 않으면 탈출 불가임을 알 수 있습니다.

네 방향에 대해 $N$명의 경찰을 모두 고려하면 되므로, 총 $O(N)$에 문제를 해결할 수 있습니다.

코드

보석

#include <bits/stdc++.h>
using namespace std;

struct data{ int x, y; } arr[110];

int n, m, t, K, resx, resy, res;
int x[110], y[110];

int main(){
    int i, j, k, now, nowx, nowy;
    scanf("%d %d %d %d",&n, &m, &t, &K);
    for(i = 0; i < t; i++){
		scanf("%d %d", &arr[i].x, &arr[i].y);
		x[i] = arr[i].x;
		y[i] = arr[i].y;
	}
    sort(x, x + t); sort(y, y + t);
    for(i = 0; i < t; i++){
        for(j = 0; j < t; j++){
            nowx = min(n - K, x[i]); nowy = max(K, y[j]); now=0;
            for(k = 0; k < t; k++){
                if(arr[k].x >= nowx && arr[k].x <= nowx + K && arr[k].y <= nowy && arr[k].y >= nowy - K) now++;
            }
            if(now >= res) resx = nowx, resy = nowy, res = now;
        }
    }
    printf("%d %d\n%d", resx, resy, res);
    return 0;
}

보석 - 추가 풀이

#include <bits/stdc++.h>
using namespace std;

struct data{ int x, y; } arr[110];

int n, m, t, K, Xn, Yn, resx, resy, res;
int x[110] = {-1}, y[110] = {-1}, sarr[110][110];

int main(){
    int i, j, k, now, nowx, nowy, nx, ny, bx = 1, by;
    scanf("%d %d %d %d",&n, &m, &t, &K);
    for(i = 0; i < t; i++){
		scanf("%d %d", &arr[i].x, &arr[i].y);
		x[i + 1] = arr[i].x;
		y[i + 1] = arr[i].y;
	}
    sort(x, x + t + 1); sort(y, y + t + 1);
    Xn = unique(x, x + t + 1) - x;
    Yn = unique(y, y + t + 1) - y;
    for(i = 0; i < t; i++){
    	nx = lower_bound(x, x + Xn, arr[i].x) - x;
    	ny = lower_bound(y, y + Yn, arr[i].y) - y;
    	sarr[nx][ny]++;
    }
    for(i = 1; i < Xn; i++){
    	for(j = 1; j < Yn; j++){
    		sarr[i][j] += sarr[i - 1][j] + sarr[i][j - 1] - sarr[i - 1][j - 1];
    	}
    }
    for(i = 1; i < Xn; i++){
    	while(bx < Xn && x[bx] - x[i] <= K) bx++; by = 1;
    	for(j = 1; j < Yn; j++){
    		while(by < Yn && y[by] - y[j] <= K) by++;
    		now = sarr[bx - 1][by - 1] - sarr[i - 1][by - 1] - sarr[bx - 1][j - 1] + sarr[i - 1][j - 1];
    		if(now > res) resx = x[i], resy = y[j], res = now;
    	}
    }
    printf("%d %d\n%d", min(resx + K, n) - K, min(resy + K, m), res);
    return 0;
}

Escaping

#include <bits/stdc++.h>
using namespace std;

struct data{ int x, y; } arr[500010];

int n, x, y, res;

int main(){
	int i, a, s, d, f;
	scanf("%d", &n); a = s = d = f = 0;
	for(i = 0; i < n; i++) scanf("%d %d", &arr[i].x, &arr[i].y); scanf("%d %d", &x, &y);
	for(i = 0; i < n; i++){
		if(arr[i].x - x >= abs(arr[i].y - y)) a++;
		if(x - arr[i].x >= abs(arr[i].y - y)) s++;
		if(arr[i].y - y >= abs(arr[i].x - x)) d++;
		if(y - arr[i].y >= abs(arr[i].x - x)) f++;
	}
	if(a && s && d && f) printf("NO\n");
	else printf("YES\n");
	return 0;
}

알고리즘 문제 접근 과정 3

알고리즘 문제 접근 과정 3

보석 - Taejon Asia Regional 2001 B번

관찰

풀이

추가 풀이

Escaping - Seoul Nationalwide Internet Competition 2020 F번

관찰

풀이

코드

보석

보석 - 추가 풀이

Escaping

Wireless Digital Communication 4

WYSINWYX: What You See Is Not What You eXecute