알고리즘 문제 접근 과정 4
알고리즘 문제 접근 과정 4
이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다.
최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다.
줄 세우기 - KOI 2013 지역본선 중등부 4번
관찰
최소한의 이동이라는 조건이 없을 때에, 우리는 어떻게 줄을 세울 수 있을까요? 우리는 1번부터 N번까지의 학생을 모두 순서대로 뒤로 보내거나, N번부터 1번까지의 학생을 모두 앞으로 보내는 방법이 있고, 혹은 이들 중 몇명은 앞으로, 몇 명은 뒤로 보내는 방법으로 해결할 수 있을 것입니다.
그렇다면, 우리는 어떤 학생을 앞으로 보내거나 뒤로 보낼 때,
- 어떤 ‘순서’로 앞 혹은 뒤로 보내거나
- 어떤 ‘학생’을 앞으로, 혹은 뒤로 보내야 할까요?
최소 횟수로 보내기 이전에, 우리가 줄을 세울 수 있는 방법일 경우, 어떤 학생을 ‘먼저’ 앞 혹은 뒤로 보낼지에 대해 생각해보고, 어떤 학생을 ‘앞 혹은 뒤’로 보낼지 생각해보아야 합니다.
만약 모든 학생들을 이동하여 줄을 세운다면 우리는 처음에 생각한 예시처럼 이동시키면 언제나 정렬할 수 있다는 것을 알 수 있습니다.
그렇다면, 몇몇 학생들은 이동하지 않을 경우에, 어떻게 이동하는 것이 좋을까요?
만약 중간에 있는 a번 학생을 이동시키지 않고 나머지 학생들을 모두 앞 혹은 뒤로 이동시킨다고 생각해봅시다.
이 때, 우리는 a번 학생을 제외한 모든 학생들을 앞 혹은 뒤로 이동시켜야 하는데, 줄을 세우기 위해서는 a번 앞에 있는 학생들은 모두 a보다 작아야 하며, a번 뒤에 있는 학생들은 모두 a번 학생보다 더 커야한다는 것을 알 수 있습니다.
즉, 우리는 a번 학생을 기준으로 앞의 학생은 모두 앞으로, 뒤에 있는 학생은 모두 뒤로 보내야한다는 것을 알 수 있습니다. 그렇다면 어떤 순서로 보내야할까요?
먼저, 우리는 학생을 앞으로 보내는 것과 뒤로 보내는 것의 순서는 중요하지 않다는 것을 알 수 있습니다. 어차피 a번 학생은 그대로 있기 때문에, 앞으로 보내는 학생과 뒤로 보내는 학생들은 모두 a를 기준으로 나뉘게 됩니다. 즉, 우리는 앞으로 보내는 학생들 사이의 순서와 뒤로 보내는 학생들 사이의 순서만 잘 맞추면 된다는 것을 알 수 있습니다.
이는 결국 a 이하의 학생을 모두 앞으로 보내 정렬하거나, 뒤로 보내 정렬하는 것과 같으므로, 맨 처음에 본 것과 같이 앞으로 보내는 학생들은 번호가 큰 학생부터 먼저, 뒤로 보내는 학생들은 번호가 작은 학생 먼저 보내면 해결할 수 있습니다.
풀이
그렇다면, a번 뿐만 아닌 b번 학생도 이동하지 않을 때에는 어떻게 될까요? 다음 상황을 봅시다.
만약 a번과 b번을 이동하지 않고, a번 이후에 b번이 있는 상황이라고 합시다. 이 때, a, b를 제외한 모든 학생들은 이동하게 되므로, 항상 a와 b는 인접해있다는 것을 알 수 있습니다.
그러므로 우리는 다음 조건들이 만족해야함을 알 수 있습니다.
- a번 앞의 학생들은 모두 a번보다 작다.
- a번보다 b번 학생이 더 크며, b = a + 1 이어야 한다.
- b번 학생 뒤의 학생들은 모두 b번 학생보다 크다.
즉, 2명의 학생을 이동하지 않는다면, 그 학생들은 서로 인접한 번호여야하며, 작은 쪽이 앞에 와있어야 합니다. a보다 작은 학생들을 앞으로 보내거나, b보다 큰 학생들을 뒤로 보내는 것은 앞선 관찰에서 사용한 방법을 그대로 사용하는 것으로 해결할 수 있습니다.
그렇다면 3명 이상의 학생들을 이동시키지 않을 때에는 어떻게 될까요? 각 학생들은 모두 서로 인접해있게 될 것이기 때문에, 그 학생들은 마찬가지로 모두 순서대로 1 차이 나는 번호를 가지고 있어야 할 것 입니다.
즉, 우리가 이동시키는 학생들을 최소화하기 위해서, 우리는 최대한 긴 순서를 맞춘 연속된 학생 수를 찾아야만 합니다.
즉, 우리는 문제를 가장 긴 순서를 맞춘 연속된 학생 수를 찾는 문제로 바꿀 수 있습니다. 그렇다면 이를 어떻게 해결할 수 있을까요?
가장 쉽게는 모든 학생들에 대해, 그 학생의 뒤에 올 수 있는 학생을 찾는 것입니다.
5 2 4 1 3 으로 줄 서있는 학생들의 경우,
5번 학생으로부터 뒤로 계속 찾아 6번 학생이 있는지 확인하고, 없으므로 5번 학생을 이동시키지 않는다면 4명을 이동시켜야 함을 알 수 있습니다.
2번 학생으로부터도 뒤로 계속 찾아 3번 학생이 있는지 확인하고, 3번 학생이 있으므로 4번 학생이 그 뒤에 있는지 찾지만 없으므로, 3명을 이동시켜야 함을 알 수 있습니다.
이처럼 매 학생마다 뒤로 연속된 번호가 나오는지 모든 학생에 대해 찾아주게 되면, 모든 학생을 보는데 $O(N)$, 뒤의 학생을 찾는데 $O(N)$으로 총 $O(N^2)$에 해결할 수 있습니다.
이를 어떻게 하면 더 개선할 수 있을까요?
바로 ‘배열에 기록하는 방법’을 통해 더 개선시킬 수 있습니다.
5 2 4 1 3 이 있고, 다음과 같은 배열을 만들어 봅시다. a[i] = i번 학생을 마지막으로 하는 가장 긴 연속된 학생 수
첫 학생인 5번 학생의 경우, 자신의 앞에 와야하는 4번 학생의 a[4]가 존재하지 않으므로, 최대 1명만 이동시키지 않을 수 있음을 알 수 있습니다.
2번 학생의 경우도 1번 학생의 a[1]이 존재하지 않으므로, 1이 됩니다.
4번 학생의 경우도, 자신의 앞에 있는 3번 학생이 존재하지 않으므로 1이 됩니다..
1번 학생의 경우도 자신의 앞에 있는 학생이 없으므로 1이 됩니다.
3번 학생의 경우, 자신의 앞에 있는 2번 학생이 존재하고, 그 때 2번 학생을 마지막으로 하는 가장 긴 연속된 학생의 수인 a[2]가 1명이므로, 3번을 마지막으로 하는 것은 2, 3번 학생인 2가 됨을 알 수 있습니다.
즉, 우리는 일련의 과정을 통해 이동하지 않아도 되는 가장 많은 학생의 수는 2가 된다는 것을 알 수 있으며, 이를 통해 답이 3이 됨을 알 수 있습니다.
이렇게 배열에 기록하는 방법을 통해, 우리는 모든 학생들을 다시 찾아보지 않아도 되어, 각 학생마다 최대 한 번 씩만 확인하면 되므로, 총 $O(N)$에 문제를 해결 할 수 있게 됩니다.
사발 뒤집기 - USACO 2006 January Bronze 3번
관찰
우리가 어떤 그릇을 두 번 뒤집는다면 어떻게 될까요? 한 번 뒤집었을 때엔 우리가 뒤집은 그릇과 그 양 옆의 그릇이 뒤집어지지만, 두 번 뒤집었을 때는 그 그릇들이 모두 2번씩 뒤집어지기 때문에, 결국 처음 상태와 같아지게 됩니다. 이는 아예 우리가 택한 그릇들 뒤집지 않는 것과 같은 결과를 만들어내므로, 우리는 두 번 이상 같은 그릇을 뒤집는 것은 항상 좋지 않다는 것을 알 수 있습니다.
그렇다면 결국 모든 그릇은 한 번 뒤집어지거나 한 번도 뒤집어지지 않는, 2개의 상태만으로도 나타낼 수 있게 됩니다.
이를 이용해 가장 쉽게 생각해볼 수 있는 방법은, 모든 그릇들을 각각 뒤집어보는 것과 뒤집지 않는 것, $2^N$개의 상태를 모두 시뮬레이션 하는 것으로, 최종적으로 모든 그릇이 0의 상태가 되었는지 확인한다면, 그릇을 뒤집는지 여부 $2^N$, 각 그릇들이 0인지 확인하는 것 N번으로, 총 $O(N2^N)$에 문제를 해결할 수 있습니다. 이를 이용해 작은 크기의 문제는 해결할 수 있지만, N이 커진다면 시간복잡도는 굉장히 커지므로, 우리는 더 좋은 방법을 생각해야합니다.
풀이
우리가 모든 그릇들을 다 0인 상태로 만들려고 한다면, 1번 그릇 또한 우리가 모든 그릇들을 뒤집고 났을 때 항상 0인 상태로 존재해야 합니다. 그렇다면, 우리는 어떤 그릇들을 뒤집기로 정해놓았을 때, 그 뒤집기가 1번 그릇의 상태를 0으로 만들게 되는지를 모든 뒤집기를 수행하지 않고도 알 수 있을까요?
만약 그릇들이 1 0 0 0 0 0 0 0 과 같이 1번 그릇만 뒤집혀 있는 상태로 놓여있다고 합시다. 이 때 3번 그릇을 뒤집는다면 결과는 어떻게 될까요?
3번 그릇을 뒤집으면 2, 3, 4번 그릇이 모두 뒤집히므로 결과는 1 1 1 1 0 0 0 0 이 되게 되어 1번 그릇은 뒤집히지 않고, 그대로 1인 상태로 놓이게 됩니다. 그렇다면, 4, 5, 6, 7, 8번을 아무렇게나 뒤집는 것으로, 1번 그릇을 0으로 만들 수 있을까요?
실제로 해본다면, 절대 1번 그릇을 0으로 만들 수 없다는 것을 알 수 있습니다. 모든 그릇들은 항상 뒤집힐 때, 자신의 양 옆의 그릇을 추가로 뒤집게 되므로, 3번 이상의 그릇들은 최대 2번 그릇까지 밖에 같이 뒤집지 못합니다.
결국 1번 그릇을 뒤집을 수 있는 경우는, 1번 그릇 혹은 그 양 옆의 그릇을 뒤집는 경우 뿐이므로, 1번 그릇을 뒤집거나, 2번 그릇을 뒤집거나, 1, 2번 그릇 모두 뒤집는 경우, 이 세가지 경우만이 1번 그릇에 영향을 줄 수 있다는 것을 알 수 있습니다.
이를 통해, 만약 1번 그릇이 0인 상태라면, 1, 2번 그릇을 뒤집지 않거나, 1, 2번 그릇을 모두 뒤집는 2가지 경우만 가능하고, 1번 그릇이 1인 상태라면 1번 그릇을 뒤집거나, 2번 그릇만 뒤집는 2가지 경우가 있음을 알 수 있습니다.
우리가 1, 2번 그릇을 원하는 대로 뒤집는 것을 통해 1번 그릇을 0인 상태로 만들고 나면, 나머지 그릇들은 어떻게 0으로 만들 수 있을까요?
1 0 0 0 0 0 0 0 에서 1번 그릇을 뒤집고, 2번 그릇을 뒤집지 않는 것으로 1번 그릇을 0으로 만들었을 때를 생각해봅시다.
이 때에 이미 1, 2번 그릇은 뒤집거나 뒤집지 않는 것을 결정했으므로, 우리는 3~8번의 그릇들만 추가로 뒤집을 수 있게 됩니다. 하지만, 사실 1, 2번을 뒤집어 1번을 0으로 만들어 놓는다면, 3번부터 8번까지의 그릇들은 뒤집는 여부가 항상 유일하게 결정됩니다.
이를 예시를 보면서 알아보겠습니다. 1번 그릇을 0으로 만들었으므로, 2번 그릇을 생각해봅시다. 2번 그릇은 현재 뒤집혀 있는 상태이지만, 1, 2번 그릇들은 뒤집을 때 1번 그릇에 영향을 주므로, 이를 뒤집어 2번을 0으로 만들면 안됩니다. 즉, 남아있는 뒤집을 수 있는 그릇들 중, 2번 그릇에 영향을 줄 수 있는 유일한 그릇은, 2번 그릇의 오른쪽에 있는 3번 그릇이 됩니다. 현재 2번이 뒤집혀있으므로, 3번 그릇은 항상 뒤집을 수 밖에 없게 되고, 상태가 변화하게 됩니다.
1, 2번이 모두 0이 되게 되면, 3번 그릇을 생각해야 합니다. 만약 3번 그릇이 0인 상태라면, 이를 뒤집으면 안되므로 4번 그릇은 뒤집지 말아야하고, 1인 상태라면 4번 그릇을 뒤집어야합니다. 즉, 1번 그릇을 0인 상태로 만들게 되면, 이후 2번 그릇부터는 순차적으로 진행하면서, 현재 보고 있는 그릇의 뒤집힌 상태에 따라 오른쪽 그릇을 뒤집어야하는지 여부가 무조건 결정됩니다. 이를 통해 우리는 3, 4, …, N - 1번 그릇까지 보면서 오른쪽 그릇들을 뒤집을지 결정해줄 수 있고, 더 이상 뒤집을 수 있는 그릇이 없는 N번 그릇에 대해, 0이라면 상태를 만들 수 있고, 그렇지 않다면 만들 수 없다는 것을 알 수 있습니다.
1번 그릇을 0으로 만드는 경우는 어떠한 상태에서도 항상 2개 존재하므로, 각 두 경우에 대해 모두 해보는 것으로 모든 그릇을 0으로 만들 수 있는지 확인해줄 수 있습니다.
이는 결국 1, 2번 그릇을 뒤집고 나면 3번부터 N번까지는 순차적으로 확인하게 되므로, 가능한 경우 중에 더 적게 그릇을 뒤집은 경우가 답이 되어 $O(N)$에 문제를 해결 할 수 있습니다.
코드
줄 세우기
#include <bits/stdc++.h>
using namespace std;
int n, res;
int arr[1000010], dp[1000010];
int main(){
int i;
scanf("%d", &n);
for(i = 0; i < n; i++){
scanf("%d", &arr[i]);
dp[arr[i]] = dp[arr[i] - 1] + 1;
res = max(res, dp[arr[i]]);
}
printf("%d", n - res);
return 0;
}
사발 뒤집기
#include <bits/stdc++.h>
#define n 20
using namespace std;
int arr[30], arr2[30], res = 1e9;
int main(){
int i, now = 0;
for(i = 1; i <= n; i++) scanf("%d", &arr[i]), arr2[i] = arr[i];
for(i = 1; i < n; i++){
if(arr[i]){
arr[i] ^= 1;
arr[i + 1] ^= 1;
arr[i + 2] ^= 1;
now++;
}
}
if(!arr[n]) res = min(res, now);
now = 1;
arr2[1] ^= 1;
arr2[2] ^= 1;
for(i = 1; i < n; i++){
if(arr2[i]){
arr2[i] ^= 1;
arr2[i + 1] ^= 1;
arr2[i + 2] ^= 1;
now++;
}
}
if(!arr2[n]) res = min(res, now);
printf("%d", res);
return 0;
}