알고리즘 문제 접근 과정
알고리즘 문제 접근 과정
알고리즘 문제 풀이를 진행하면서, 어느정도 순간에서부터는 내가 모르는 알고리즘 및 자료구조가 필요하다는 점에서 문제 풀이의 어려움을 느끼게 됩니다. 더 발전하기 위해서 다양한 내용들을 찾아서 공부하고 이를 구현하는 방법을 익히는 과정이 필요하게 됩니다.
하지만 처음 공부할 때에 실제로 제가 가장 많이 겪었던 문제, 혹은 다른 사람들이 처음 공부를 시작 하면서 어려웠던 점들에 대해 이야기를 들을 때에 공통적으로 나왔던 부분은 바로, 알고리즘과 자료구조를 알고 있어도, 해당 문제를 어떤 알고리즘과 어떤 자료구조를 사용해야 하는지 제대로 파악하지 못하여 해결하지 못한다는 점입니다.
이러한 문제는 어떤 문제가 주어졌을 때에, 이 문제를 어떻게 파악해나아갈지, 어떻게 저근해야할지 잘 모른다는 것에서 시작합니다. 개선을 위한 가장 좋은 방법은 많은 유형의 문제들을 접해보고, 직접 해결하기 위해 시간을 들이는 것입니다. 그 과정에서 자신만의 문제 해결을 위한 접근 방법을 알게 되고, 문제를 분석하고 파악하는 과정을 익히게 되며, 특별한 알고리즘, 자료구조를 사용할 수 있는 경우들을 경험을 통해 익히는 것이 가능하게 됩니다. 그 이후로는 어떠한 문제를 보아도, ‘이 유형은 이러한 성질들을 만족하므로, 어떠한 알고리즘으로 접근할 수 있다’와 같은 문제에 대한 빠른 파악과 접근이 가능해집니다.
‘알고리즘 문제 접근 방법’에서는 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성하려합니다.
서로 다른 난이도와 유형의 문제들의 접근 과정을 확인하면서, 어떤 방식으로 문제를 파악해나갈 수 있는지에 대한 영감을 받아갈 수 있으면 좋겠습니다.
유의점
많은 경우, 문제들을 해결할 때에 낮은 단계의 아이디어(시간이 오래 걸리는, 혹은 단순한)를 개선하는 방식으로 해결하는 것이 가능합니다. 하지만 모든 경우가 아이디어 개선을 통해 해결할 수 있지는 않습니다. 특정 문제 상황에서만 적용되는 성질을 파악해야할 수도 있으며, 아예 기본적인 아이디어에서 다른 방향으로 접근해야만 시간복잡도를 개선할 수 있거나 더 쉽게 문제를 해결할 수 있는 경우들도 존재합니다.
이러한 경우들이 존재하기 때문에, 문제를 접근할 때에는 특정 성질이나 아이디어에 꽂혀 유연한 사고를 멈추는 일을 조심해야합니다. 이전에 문제를 해결한 경험들이 이후의 문제 풀이들을 빠르게 진행하는 데에 도움을 줄 수는 있으나, 특별한 조건이나 성질을 놓치게 만들 수도 있니다.
문제를 해결하기 위해서는 항상 해당 문제를 접근하는 과정에서 내가 놓친 부분이 없는지 끊임없이 고민해야합니다.
아래에 나오는 문제들을 잘 읽어보신 다음, 충분한 생각을 하신 후 아래의 접근 과정을 읽어보시는 것을 추천드립니다.
다리 - Daejeon Nationalwide Internet Competition 2012 A번
관찰
우리는 특별한 방법이 떠오르지 않을 때에, 문제에서 요구하는 조건을 그대로 구현하는 것으로 가장 쉽게 문제를 해결할 수 있습니다. 물론 효율적임은 보장이 되진 않지만, 문제를 파악하기에 어느정도 좋은 접근방법입니다.
문제에서 요구하는 것은 왼쪽 $n$개의 집에서 오른쪽 $m$개의 집으로 $h$ 높이에 있는 다리를 이용하여 이동할 때에 걸리는 모든 거리의 합을 최소로 시키는 것입니다.
즉, 이를 그대로 구현하여, 가능한 모든 높이에 다리를 설치해보고, 왼쪽 집에서 오른쪽 집으로 이동하는 거리들의 합을 모두 구해본 다음, 그 때의 최솟값을 가지는 $h$를 출력하는 것으로 문제를 해결할 수 있습니다.
모든 집들의 쌍은 총 $n * m$개 존재하고, 가능한 모든 높이의 경우의 수를 $w$라고 했을 때, 모든 $w$개의 위치에 다리를 놓아보고 $n * m$쌍의 거리의 합을 구함으로써, 총 $O(nmw)$에 문제를 해결할 수 있습니다.
우리는 현재 이 상태에서 조금 더 효율적으로 문제를 해결하고 싶습니다. 문제에서 주어진 모든 쌍의 거리의 합을 구하는 부분을 살펴보겠습니다.
여기에서, 하나의 $a_{i}$와 $b_{j}$ 쌍에 대해 거리를 계산하는 식을 보면, $\vert a_{i} - h \vert + 2 + \vert h - b_{j} \vert$가 된다는 것을 알 수 있습니다. 그렇다면 이 식을 각각 $\vert a_{i} - h \vert, 2, \vert h - b_{j} \vert$로 나누어 보겠습니다.
이 때, $2$를 더하는 경우는 $i$와 $j$에 상관없이 항상 2만 더한다는 것을 알 수 있습니다. 그렇다면, 이는 모든 쌍에 대해서 몇 번 일어나게 될까요? 우리가 가진 집의 모든 쌍은 총 $n * m$개가 존재하므로, 우리는 $2$를 $n * m$번 더할 것이라는 것을 알 수 있습니다.
하나의 $a_{i}$에 대해서, $\vert a_{i} - h \vert$는 j에 상관없이 항상 똑같은 값을 가집니다. 즉, 우리는 특별한 $i$에 대해 $\vert a_{i} - h \vert$가 $m$번 더해질 것이란 사실을 알 수 있고, 마찬가지로 $\vert h - b_{j} \vert$ 또한 $i$에 상관없이 똑같은 값을 가지므로, $n$번 더해질 것이란 것을 알 수 있습니다.
즉, 이를 이용하여 $2$는 $i, j$ 상관없이 총 $n * m$번, $\lvert a_{i} - h \rvert$는 $m$번, $\vert h - b_{j} \vert$는 $n$번 더해지게 되므로, 우리는 주어진 식을 다음과 같이 바꿀 수 있습니다.
즉, 우리는 모든 $n, m$ 쌍에 대해 계산하는 것이 아니라, $1$부터 $n$까지의 $i$에 대해서 $\vert a_{i} - h \vert*m$을, $1$부터 $m$까지의 $j$에 대해서 $\vert h - b_{j} \vert * n$을 계산해주면 되므로, 합을 계산하는데 총 $O(n+m)$이 걸리고, 우리는 시간복잡도를 $O(nmw)$에서 $O(w * (n + m))$으로 개선시킬 수 있습니다.
풀이
이제 우리는 변형된 식을 최소로 만드는 다리의 위치를 찾아주는 것으로 문제를 해결할 수 있습니다. 여기에서 어떤 규칙으로 다리의 최소 위치를 찾는지 바로 감을 잡는다면 문제가 없지만, 어떤 경우 우리는 그 규칙을 찾기 어려울 수 있습니다. 이 때엔, 직접 예제를 손수 계산해보는 것으로 규칙을 찾을 수도 있어, 실제로 해보는 것이 좋습니다.
앞선 예시인 왼쪽 강의 집이 각각 $30, 5, -16$에 위치하고, 오른쪽 강의 집이 $25, -5, -10, -20$인 경우를 살펴봅시다.
우리가 $30$보다 높은 위치나 $-20$보다 낮은 위치에 다리를 놓을 필요가 있을까요?
우리가 정답으로 계산하는 $i$와 $j$에 대한 식은 각각 $\vert a_{i} - h \vert와 \vert h - b_{j} \vert$입니다. 여기에서 $h$가 $30$일 때에서 보다 더 높아지거나 $-20$보다 더 낮아질 때를 생각해보겠습니다. 우리는 절댓값을 최소화하기 위해서 집과 다리의 위치의 차를 가장 작게 만들어야 합니다. 하지만, 집들의 위치보다 더 높거나 낮은 곳에 다리를 위치하게 되면, 모든 $\vert a_{i} - h \vert$와 $\vert h - b_{j} \vert$가 더 커지게 됩니다. 즉, 우리는 항상 집들의 최소와 최대 위치 사이에 다리를 놓아야 함을 알 수 있습니다.
빨간 다리를 위치하게 되면, 모든 집들이 다 파란색 다리에 비해 노란색만큼 더 이동해야 함
이제 가장 높은 $30$의 위치에 다리를 놓는 것으로부터 생각해보겠습니다. $(30, 5, -16), (25, -5, -10, -20)$의 집들은 각각 절댓값이 $(0, 25, 46), (5, 35, 45, 50)$이 됩니다. 이 때, 아래로 $1$의 위치만큼 이동했을 때를 생각해보겠습니다. 그 경우 절댓값은 각각 $(1, 24, 45), (4, 34, 44, 49)$가 됩니다. 어떤 변화를 관찰할 수 있을까요?
이 때, 우리는 $30$에 위치한 집 빼고는 절댓값이 모두 $1$씩 줄어들었다는 것을 관찰할 수 있습니다. 이를 살펴보겠습니다.
다른 집들은 모두 $30$보다 낮은 위치에 있었기 때문에, 다리에서 집의 위치를 뺀 값이 모두 양수였습니다. 즉, 다리의 위치가 $1$ 낮아져도 값들이 $0$ 이상임은 보장되고, 결국 값들이 모두 $1$ 줄어든다는 결과를 낳게 됩니다.
$(25, 46, 5, 35, 45, 50) -> (24, 45, 4, 34, 44, 49)$
하지만 $30$의 집은 그 차가 $0$이었기 때문에, 다리가 낮아지면 음수가 되어 값은 더 커지게 됩니다.
혹시 여기에서 한 규칙을 발견할 수 있을까요?
우리는 여기에서 $\vert 다리 - 집 \vert$ 의 값을 보면서 규칙을 알아볼 수 있습니다.
- $다리 - 집 > 0$ 인 경우, 다리가 $1$ 낮아지면 값도 $1$ 줄어들고, $1$ 높아지면 값이 $1$ 증가함
- $다리 - 집 = 0$ 인 경우, 다리가 $1$ 낮아져도 높아져도 값이 $1$ 증가함
- $다리 - 집 < 0$ 인 경우, 다리가 $1$ 낮아지면 값이 $1$ 증가하고, $1$ 낮아지면 값이 $1$ 감소함
즉, 우리는 $\vert 다리 - 집 \vert$이 $0$보다 큰 경우, $0$인 경우, $0$보다 작은 경우로 나누어 케이스를 나눠줄 수 있습니다.
이 때, 우리는 방향성을 알아보기 편하게 하기 위해서 다리의 위치를 항상 $1$씩 감소하면서 살펴보겠습니다. 이 때, 거리의 합은 왼쪽 집과 오른쪽 집에대해 각각 $\vert 다리 - 집 \vert * m, \vert 다리 - 집 \vert * n$이므로, 우리는 다리의 위치가 $1$ 감소할 때 거리의 합의 증감은 다음과 같이 살펴볼 수 있습니다.
- 왼쪽 집에서 $다리 - 집 > 0$인 집이 $p$개, 오른쪽 집에서 $다리 - 집 > 0$인 집이 $q$개라면 합은 $(n - p) * m + (m - q) * n - (p * m + q * n) = (n - 2p) * m + (m - 2q) * n$ 만큼 증가함
초기의 $p$와 $q$는 각각 $n, m$인 상태로 볼 수 있고, 다리가 $1$씩 감소할수록 $p$나 $q$는 항상 감소하게 되므로, 우리는 어느 위치에서 $(n - 2p) * m + (m - 2q) * n > 0$ 이 되는 위치를 찾을 수 있을 것입니다. 즉, 그 이전까지 된다면 거리의 합이 최소가 되는 경우가 됩니다.
이제 다리의 위치가 감소하다가, $(n - 2p) * m + (m - 2q) * n > 0$인 위치를 찾으면 그 이전이 바로 답이 됨을 알 수 있습니다. 하지만 아직도 우리는 다리를 $1$씩 감소하며 답을 찾고 있습니다. 혹시 이를 해결할 방법이 있을가요?
이는 $p$와 $q$가 각각 언제 감소하는지를 가지고 살펴볼 수 있습니다.
만약 다리를 아래로 $1$만큼 내리더라도, 그 위치에 집이 있지 않다고 해봅시다. 이 때, $다리 - 집 > 0$을 만족하는 $p, q$가 감소하는 경우가 있을까요? 정답은 없다 입니다.
왜냐하면 다리를 $1$만큼 내려도 그 위치에 아무런 집이 없다면, 지금 현재 다리의 이상 위치에 있는 집들은 항상 $다리 - 집 <= 0$을 만족하는 상태이고, 다리 아래에 있는 집들, 즉, $다리 - 집 > 0$인 집들은 사실 $다리 - 집 > 1$을 만족하는 상태일 수 밖에 없기 때문입니다.
즉, 현재 $다리 - 집 > 1$인 집들은 $1$씩 줄어도 $다리 - 집 > 0$을 만족하므로, $p$와 $q$는 그대로가 됩니다.
결국 $p$와 $q$가 변하기 위해서는 $1$ 감소할 때 바로 집이 있는 위치가 되어야합니다. 또한 이를 다르게 표현한다면 집이 있는 위치만이 p와 q의 변화가 생긴다를 알 수 있습니다.
결국 우리는 모든 위치를 고려하는 것이 아니라, $n + m$개의 집이 있는 위치만 고려하여 답을 찾아줄 수 있고, 이 중 집의 위치가 높은 곳부터 계산하는 것으로 문제를 해결할 수 있습니다.
집들의 위치를 내림차순으로 정렬하는데 $O((n+m)lg(n+m))$, 좌표를 하나씩 내리는, 총 $O(n + m)$의 시간복잡도로, 최종적으로 정렬하는데 걸리는 시간복잡도로 문제를 해결할 수 있습니다.
동일한 거리를 가지는 위치들 중 가장 낮은 위치에 다리를 놓기로 한다는 점에 유의하여 구현하면 만점을 받을 수 있습니다.
ps. 입력이 정렬되어 들어온다면 우리는 조건을 만족하는 위치를 이분탐색으로 찾을 수 있습니다. 또한 입력이 정렬되지 않은 상태로 들어온다면 우리는 삼분탐색을 이용한 $O((n + m)lgw)$에 문제를 해결할 수도 있습니다.
통학버스 - KOI 2012 초등부 3번
관찰
한 번의 통학버스를 보내 학생들을 등교시킬 때, 학교의 왼쪽 편의 아파트들을 방문한 이후에, 다시 학교의 오른쪽의 아파트들을 방문할 필요가 있을까요? 이 경로 사이에는 중간에 학교를 방문할 수 있기 때문에, 통학버스를 학교에 도착시켜 안에 있는 학생들을 모두 등교시킨 이후에, 다시 오른쪽을 방문하는 것이 더 많은 학생들을 태울 가능성이 있습니다. 즉, 우리는 한 번 버스를 보내게 된다면 왼쪽, 혹은 오른쪽에 있는 아파트들만을 방문한 이후에 돌아오는 것이 항상 더 좋음을 알 수 있습니다.
그렇다면, 첫 번째 버스를 어느 방향의 어디까지 보내서, 각 아파트에서 몇 명을 태워 오는 것이 경로를 최소화 할 수 있을까요? 아마 가장 먼저 드는 생각은 가장 가까운 아파트부터 방문하는 방법일 것입니다. 만약 가장 가까운 아파트에 학생들을 태우가 난 이후 버스가 꽉 차게 된다면, 그보다 더 멀리 있는 아파트까지 가지 않고 학생들을 태워올 수 있으니까요. 물론 가장 가까운 아파트에서 학생들을 태웠을 때, 버스가 꽉 차게 된다면 이는 항상 가장 빠를 것입니다.
하지만 문제는 버스에 빈 자리가 남을 때 생기게 됩니다. 만약 몇 자리가 남았다면, 조금 더 지나가 다음 아파트에서도 태우고 와야할까요? 아니면 일단 학교에 도착해 학생들을 등교시킨 이후 다시 가야할까요?
이는 어떤 경우를 선택해도 항상 다른 방법이 더 좋은 결과를 낳을 수가 있어, 선택하기가 어렵습니다.
만약 5명의 학생을 태울 수 있는 버스가 있고, 학교에서 가까운 순서로 두 개의 아파트에 3명, 2명의 학생이 있다면, 당연히 끝 아파트까지 경유해서 오는 것이 한 번에 모든 학생들을 태워올 수 있기 때문에 최적이 될 것입니다.
하지만 아파트에 학생이 3명, 3명 있다면 끝 아파트에 도착해도 모든 학생을 태울 수 없어, 결국 한 번 더 버스를 보내게 됩니다. 이는 3명을 태우고 학교에 돌아와서, 다시 3명을 태우는 경우보다 더 느리게 됩니다.
다른 상황들에 대해서도, 두 가지 중 무엇을 선택하는지는 쉽지 않다는 것을 직접 해보는 것으로 알아낼 수 있습니다. 가까운 곳의 아파트부터 방문하여 학생을 태울 때, 우리는 위 두 가지 선택지 중에 무엇을 선택해야 거리가 줄어들게 될지 쉽게 알 수 없었고, 이를 해결하기 위해 우리는 접근의 방향을 바꿔볼 필요가 있습니다.
풀이
관찰에서 생각했던 방법과 반대로, 가장 왼쪽 끝에 있는 아파트를 생각해봅시다. 우리는 모든 학생들을 등교시켜야 하기 때문에, 한 번 즈음은 항상 왼쪽 끝에 있는 아파트를 방문해야합니다.
만약 스쿨버스가 이 아파트에 도착하게 된다면, 어차피 더 왼쪽으로 가도 태울수 있는 학생이 없기 때문에, 태울 수 있을만큼 이 아파트에 태운 다음 돌아가는 것이 가장 효과적이라는 것을 알 수 있습니다(어차피 몇 명을 태우든 거리는 똑같으므로). 만약 버스가 다 차게 된다면, 이후에 무조건 한 번 더 아파트를 방문해야합니다다. 하지만 버스가 다 차지 않고 모든 학생들을 태웠다면, 돌아가는 길에 태울 수 있는 학생들을 가능한 많이 태워서 가는 것이 항상 효율적임을 알 수 있습니다.
그렇다면, 돌아올 때 어느 아파트에 있는 학생들을 태우는 것이 가장 효율적일까요? 만약 왼쪽 끝의 아파트와 두 번째 아파트를 동시에 한 번에 태울 수 있다면, 이후의 버스들은 항상 3번째 이상의 아파트만 방문하면 되므로, 버스가 이동하는 거리가 더 줄어들게 됩니다. 즉, 우리는 한 번의 버스 방문을 통해 끝에 있는 아파트들을 모두 채울 수록, 이후에 이동할 거리가 줄어들 가능성이 생기게 됩니다.
1) 두 명을 태울 수 있는 버스가, 두 명을 끝의 두 아파트에서 태울 때의 경로
2) 이후 바로 옆에 있는 아파트만 경유하여 돌아옵니다
3) 버스가 나머지 한 명을 중간의 아파트에서 태울 때의 경로, 1)번과 거리가 같지만
4) 이후 두 번째에 있는 아파트를 경유하여 돌아와야해서, 2)번보다 경로 손해를 봅니다
이를 일반화하면, 우리는 항상 현재 존재하는 가장 멀리에 있는 아파트를 적어도 한 번 방문해야 하기 때문에, 그 아파트를 방문하는 순간에, 멀리있는 아파트들을 최대한 다시 방문하지 않도록 만들어야 합니다.
이로써, 우리는 버스를 이동시킬 때, 특정 방향의 가장 멀리있는 아파트를 방문한 이후, 그 아파트부터 태울 수 있는만큼 최대한 많이 태우며 멀리있는 아파트의 학생들을 등교시키는 것이 효율적이게 됩니다.
이는 입력된 아파트들을 좌표 순서대로 정렬한 이후, 가장 왼쪽에 있는 아파트의 끝에서부터, 그 아파트의 학생들을 태우기 위해 몇 대가 필요한지, 다 태우고 난 이후 마지막 버스에 몇 개의 자리가 남았는지를 관리해줍시다. 만약 마지막 버스에 학생을 더 태울 수 있다면, 그 다음 아파트로 이동하여 남은 수만큼을 채워주고, 다시 빈 버스를 현재 아파트로 이동시키는 것을 반복해주면 학교 왼쪽에 있는 아파트의 학생들을 모두 등교시킬 수 있고, 이와 똑같이 오른쪽에 있는 아파트들도 진행해주면 각 아파트들을 한 번씩만 확인하는 것으로 버스가 이동하는 거리를 알아낼 수 있습니다.
태우고 빈 자리가 남은 버스가 지나갈 수 있는 다음 아파트가 있을 경우만, 바로 학교로 돌아가는 예외처리를 해주게 되면 이외의 상황은 모두 위 상황 중 하나에 속하게 되어 모든 경우를 처리할 수 있습니다.
각 아파트들은 최대 한 번만 확인하게 되므로, 가장 시간이 오래 걸리는 때는 아파트들을 좌표 순서대로 정렬해주는 과정이 되므로, 우리는 $O(NlgN)$에 문제를 해결할 수 있습니다.
이 때, 구현에서 주의해야 할 점은, 버스의 수용인원이 학생들의 수에 비해 너무 적을 때가 됩니다. 만약 인원이 굉장히 많은데 버스의 수용인원이 적다면 우리는 같은 위치에서 학생들을 여러번 반복하여 태워야할 수도 있습니다. 이러한 경우를 하나하나 모두 시뮬레이션 하게 되면 실제로 $NlgN$의 시간복잡도를 만족하지 못할 수 있습니다.
이를 해결하기 위해서, 어떠한 위치에 버스가 여러번 가야하는지 여부를 학생의 수를 버스의 수용인원으로 나눈 몫 만큼은 한 번에 반복할 수 있도록 구현해주어 여러번 같은 위치를 가지 않을 수 있도록 만들어줄 필요가 있습니다.
코드
다리
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct data{ int x, flag; };
int T;
ll n, m;
data arr[2000010];
bool compare(data d1, data d2){
return d1.x > d2.x;
}
int main(){
int p, i;
ll np, nq;
scanf("%d", &T);
for(p = 0; p < T; p++){
scanf("%lld %lld", &n, &m);
for(i = 0; i < n; i++) scanf("%d", &arr[i].x), arr[i].flag = 1;
for(i = n; i < n + m; i++) scanf("%d", &arr[i].x), arr[i].flag = 0;
sort(arr, arr + n + m, compare); np = n; nq = m;
for(i = 0; i <= n + m; i++){
if((n - 2 * np) * m + (m - 2 * nq) * n > 0){ i--; break; }
if(arr[i].flag) np--;
else nq--;
}
printf("%d.0\n", arr[i].x);
}
return 0;
}
통학버스
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct data{ int x, v; };
int N, K, S;
ll res;
vector <data> arr[2];
bool compare(data d1, data d2){
return abs(d1.x - S) < abs(d2.x - S);
}
int main(){
int i, j, a, s, now;
scanf("%d %d %d", &N, &K, &S);
for(i = 0; i < N; i++){
scanf("%d %d", &a, &s);
if(a < S) arr[0].push_back((data){a, s});
else arr[1].push_back((data){a, s});
}
sort(arr[0].begin(), arr[0].end(), compare);
sort(arr[1].begin(), arr[1].end(), compare);
for(i = 0; i < 2; i++){
while(arr[i].size()){
now = 0;
while(arr[i].size()){
res += abs(arr[i].back().x - S) * 2 * (arr[i].back().v / K);
arr[i].back().v %= K;
if(!arr[i].back().v) arr[i].pop_back();
else break;
}
if(!arr[i].size()) break;
res += abs(arr[i].back().x - S) * 2;
while(now < K && arr[i].size()){
now += arr[i].back().v;
if(now > K) arr[i].back().v = now - K;
else arr[i].pop_back();
}
}
}
printf("%lld", res);
return 0;
}