알고리즘 문제 접근 과정 5
알고리즘 문제 접근 과정 5
이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다.
최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다.
두 배열의 합 - KOI 2001 고등부 1번
관찰
우리가 생각해볼 수 있는 가장 쉬운 방법은 무엇이 있을까요? 아마 문제에서 나온 방법을 그대로 사용하는 것이 가장 편한 방법일 것입니다. 우리가 만들 수 있는 A의 부 배열과 B의 부 배열의 모든 가능한 조합을 고려하여, 그 중 합이 T가 되는 경우의 수를 세는 것으로 문제를 해결할 수 있습니다. 이 과정에서 A, B에 대한 부배열 쌍은 각각 약 $N^2$, $M^2$개 존재하게 되어, 실질적으로 만들 수 있는 가능한 조합은 대략 $(NM)^2$개가 존재하게 됩니다. 이를 단순하게 부 배열의 범위가 정해졌을 때, 그 사이에 있는 모든 수를 더하는 방법으로 계산하게 되면 너무 오랜 시간인 $O((NM)^3)$이 걸립니다. 하지만 누적합을 이용해서 범위 (l, r) 사이에 있는 수들의 합을 $O(1)$에 해결하는 아이디어를 사용한다면 모든 쌍을 비교하는 과정을 $O((NM)^2)$에 해결하게 됩니다. 배열의 최대 크기가 1000으로 작기 때문에 모든 부 배열을 구하는 것은 가능하지만, $(NM)^2$의 모든 경우의 수를 찾는 것은 너무 오랜 시간이 걸리게 됩니다.
풀이 1
우리가 A 배열의 특정 부 배열의 값이 a임을 알고 있다고 합시다. 그렇다면, B 배열의 어떤 부 배열의 합 b가, a와 합쳐져서 T가 될 수 있을까요? 이 때, 항상 $T = a + b$를 만족해야하기 때문에 $b = T - a$인 부 배열들만이 T를 만들 수 있게 됩니다. 즉, 우리는 A 배열에 있는 $N^2$ 개의 부 배열들에 대해 각각, $T - a_{i}$ 를 만족하는 B의 부 배열의 개수를 세주는 것으로 문제를 해결할 수 있습니다. 그렇다면, $T - a_{i}$ 를 만족하는 부 배열이 존재하는지, 그리고 그 경우의 수는 몇 가지가 있는지 어떻게 알 수 있을까요?
A, B의 $N^2$ 개의 부 배열들을 각 부 배열의 합을 기준으로 정렬을 해줍시다. 이 때, 우리는 항상 다음 두 조건을 만족하게 됩니다.
- $a_{i} <= a_{j} , i < j$ 즉, a는 단조증가
- $b_{i} <= b_{j} , i < j$ 즉, b는 단조증가
즉, 우리가 i가 1부터 증가하는 순서대로 보게 된다면 항상 $a_{i}$는 증가하게 되고, j를 $N^2$부터 감소하는 순서로 보게 된다면 항상 $b_{j}$는 감소하게 됩니다. 그렇다면, 어떤 $a_{i}$에 대해 $b_{j}$의 합이 T가 된다고 해봅시다.
- $a_{i} + b_{j} = T$
그렇다면 이 때, $a_{i+1}$에 대해 합이 T가 될 수 있는 원소들은 어디에 존재할 수 있을까요?
앞선 a가 단조증가한다는 조건을 이용하면 모든 i에 대해 $a_{i} <= a_{i+1}$을 만족합니다. 즉,
- $a_{i} + b_{j} = T => a_{i+1} + b_{j} >= T$
를 만족하게 되고, b는 항상 값이 단조증가함을 이용하면 $a_{i+1} + b_{k} = T$를 만족할 가능성이 있는 k들은 $k <= j$ 인 k들만 해당됨을 알 수 있습니다.
결국 우리는 앞선 $a_{i} + b_{j} <= T$를 만족하는 j의 최댓값부터 $a_{i+1} + b_{j} >= T$ 를 만족할 때까지 줄여가면서 그 사이에 $a_{i+1} + b_{j} = T$를 만족하는 경우의 수를 모두 세주면 됩니다.
앞선 예시를 통해 더 자세히 알아봅시다.
A = {1, 3, 1, 2}, B = {1, 3, 2}, T = 5 이므로 이를 부배열의 합을 정렬하여 나타내면
가 됩니다. 이 때, $a_{1}$은 $b_{6}, b_{5}$와 합해도 5를 넘어가기 때문에, 이를 j를 줄여 $b_{4}$에서 합이 5가 만족하게 됩니다.
그러면 이후 $a_{2}$는 아무리 커도 j = 4인 때를 넘어가지 않게 되고, j = 4부터 만족할 때까지 j를 줄여나가면, j = 4일 때에만 답을 만족하게 됩니다.
$a_{3}$ 또한 아무리 커도 j = 4인 때를 넘어가지 않고, j = 4를 만족하지 않으므로 j를 줄이게 되면 j = 3일 때 답이 됨을 알 수 있습니다.
($a_{i} = a_{i+1}$일 수 있는 가능성 때문에, j를 바로 줄이지 않고 j = 4와 한 번 비교하게 됩니다)
하지만 우리는 아직 해결하지 못한 문제가 있습니다. 이를 이용해 모든 경우의 수를 다 보지 않고, 실제로 존재하는 쌍들만 확인하여 문제를 해결할 수 있어서, 만약 실제 답이 $N^{2}$보다 작다면(혹은 중복된 부 배열합이 없다면) 문제없이 해결할 수 있지만, 모든 a와 b가 0이고, T 또한 0인 문제가 나온다면, 매 순간 l의 범위는 b의 부 배열의 수 전체가 되어 $N^{4}$가 걸릴 수도 있습니다. 우리는 모든 쌍을 하나씩 세는 것이 아닌, 여러개씩 세서 더 빠르게 만드는 방법을 구해야합니다.
만약 $[a_{i}, a_{i+c}]$ 사이의 원소들이 모두 같은 값이라면 어떻게 될까요? 특정 $a_{i}$에 대해 $[b_{j}, b_{j+d}]$ 사이의 원소들의 합이 T를 만족한다면, $a_{i+1}$ 부터 $a_{i+c}$까지의 원소들 또한 $[b_{j}, b_{j+d}]$에 대해 합이 T를 만족할 것입니다. 그렇다면, 특정 $a_{i}$와 같은 값들의 수를 세주고, 이에 해당하는 $b_{j}$의 값들을 세어 두 수의 곱을 구하게 된다면, 우리는 바로 $a_{i+c+1}$번부터 볼 수 있고, $b_{j-1}$부터 보기만 하면 됩니다. 그렇다면 과연 이 방법으로 시간복잡도를 크게 바꿀 수 있을까요?
Ex)
1을 한 번에 처리하는 것으로, 이후에 나오는 2는 절대로 1과 매치됐던 4 이상의 값들과는 합이 T가 될 수 없음을 알 수 있어, 바로 4보다 작은 값인 3과의 비교를 시작합니다.
정답은 시간복잡도를 바꿀 수 있다 입니다. 이처럼 여러개의 연속된 구간들을 한 번에 볼 수 있게 된다면, 우리는 i를 항상 증가하는 방향으로만 보고, j도 연속된 구간을 구하고 나면, 다음번 $a_{i}$는 증가할 것이기 때문에 $b_{j}$ 또한 항상 이전 구간의 원소와 합하면 값이 T보다 커진다는 사실을 알 수가 있게 됩니다. 즉, j 또한 항상 감소하는 방향으로만 봐야하기 때문에, 우리는 a의 각 원소를 한 번씩만, b의 각 원소 또한 한 번씩만 확인하게 되어, 연속된 구간을 한 번에 처리하는 방법만으로, 답을 구하는 데에는 $O(N^{2} + M^{2})$의 시간만이 걸리게 됩니다.
결국 시간복잡도는 $N^2$, $M^2$개의 배열을 정렬하는데 걸리는 시간인 $O(N^{2}lgN + M^{2}lgM)$이 되어 문제를 빠르게 해결할 수 있습니다.
풀이 2
앞서 우리는 A의 i를 증가하는 방향으로, B의 j를 감소하는 방향으로 문제를 풀었습니다. 우리는 이를 다른 방법을 사용하는 것으로 조금 더 간단하게 해결할 수도 있습니다.
앞선 방법과 동일하게 B의 모든 부 배열의 합들을 만들어 둔 이후, 이를 오름차순으로 정렬해두었다고 생각해봅시다. 이 때, 어떠한 $a_{i}$에 대해서 합이 T가 되는 값들을 빠르게 찾는 방법이 있을까요? 우리는 특별한 방법을 사용하여, 특정한 $a_{i}$에 대해 합이 T가 되도록 하는 $b_{j}$의 경우, 항상 $b_{j} = T - a_{i}$를 만족해야 한다는 조건을 살펴본 적이 있습니다. 즉, 우리는 해당하는 $b_{j}$의 수가 몇 개인지 빠르게 구하는 방법을 알고 있다면 문제를 해결할 수 있게 됩니다. 이 때, 우리는 B 배열이 항상 정렬되어있다는 것을 사용해볼 수 있습니다. 위 조건을 만족하는 $b_{j}$들이 존재한다면 이들은 B 배열 내에서 연속해서 존재하게 됩니다. 그리고 이러한 b의 범위 오른쪽은 항상 $b_{j}$보다 더 큰 값이 존재할 것이고, 이보다 왼쪽에 있는 값들은 항상 $b_{j}$보다 더 작은 값들이 존재할 것입니다. 즉, 이것을 통해서 $b_{j}$가 존재하는 최대 위치와 최소 위치를 구할 수 있다면, 그 사이의 범위에 들어있는 부 배열의 갯수를 빠르게 구할 수 있지 않을까요? 어떠한 $a_{i}$에 대해서, $b_{j} <= T - a_{i}$가 되는 j의 최댓값을 이분탐색을 이용해 구하고, $b_{j} >= T - a_{i}$를 만족하는 j의 최솟값을 이분탐색을 이용해 구해줍니다. 이 값들을 각각 c, d라 하면 항상 $[d, c]$ 에 있는 원소들이 실제 답이 되는 b의 범위가 됩니다. 즉, 하나의 a에 대해 해당하는 b의 범위를 두 번의 이분 탐색을 사용해서 구할 수 있다는 것입니다.
이러한 이분탐색에는 $O(lgM)$ 만큼의 시간이 걸리기 때문에, 우리는 모든 a에 대해 중복을 처리하지 않고, 이분 탐색을 적용해 $O((N^{2} + M^{2})lgM))$의 시간복잡도로 문제를 해결할 수 있습니다. 이는 답을 구하는데 기존의 풀이보다는 조금 더 느리게 동작하지만, 시간복잡도 자체는 정렬하는 시간이 지배한다는 점 때문에 사용해도 같은 시간복잡도를 얻게 됩니다. (만약 부 배열들이 정렬되어 있는 상태라면, 기존의 방법은 $O(N^{2} + M^{2})$에 해결할 수 있으며, 풀이 2는 이분 탐색 과정에서 시간이 더 필요하기 때문에 $O(N^{2}lgM))$의 시간이 필요합니다.)
이렇게 정렬된 배열 내에서 해당 원소의 최대 위치와 최소 위치를 찾는 이분 탐색은 STL로 구현되어 있습니다. 최소 위치에 해당하는 값의 주소는 algorithm header에 들어있는 함수 std::lower_bound()를, 최대 위치는 std::upper_bound()를 이용하여 쉽게 구할 수 있습니다.
JNEXT - spoj
주어진 문제가 영문이기 때문에 번역을 하여 문제를 첨부하겠습니다.
문제
민성이는 누구보다 수를 좋아한다. 그 중에서도 특히 큰 수를 좋아한다. 그래서 N개의 자릿수가 주어지면, 이것을 이어붙여 하나의 큰 수를 만든다.
이를 지켜보던 성희는 놀라운 사실을 알아낸다. 민성이가 큰 수를 만든 것은 맞지만, 그것은 N개의 자릿수들을 이용해 만들 수 있는 ‘가장 큰 수가 아니었던 것’이다. 가장 큰 수를 만들어 알려주는 것은 민성이한테 너무 가혹한 일이기 때문에, 성희는 그 자릿수들을 이용해 만들 수 있는 모든 수들 중, 민성이가 만든 수보다 큰 수들 중, 가장 작은 수를 만들어, 더 큰 수가 있음을 민성이한테 알려주려 한다.
성희가 민성이한테 알려줄 수가 무엇일지 구해보자.
예시
7개의 자릿수 7, 1, 1, 3, 5, 2, 1이 있고, 민솔이가 이를 이용해 7113521 을 만들었다면, 동규는 7, 1, 1, 3, 5, 2, 1로 만들 수 있는 수들 중, 민솔이가 만든 것보다 큰 수 중 가장 작은 수인 7115123을 알려준다.
입력
첫 번째 줄에는 테스트 케이스의 수 t(1 <= t <= 100)가 주어집니다. 두 번째 줄부터 t개의 테스트 케이스가 차례로 주어지는데, 각 테스트 케이스의 첫 번째 줄에는 숫자의 자릿수 n(1 <= n <= 1000000)이 주어지고, 두 번째 줄에는 민성이가 만든 n자리 수의 각 자릿수가 공백을 사이에 두고 주어집니다.
출력
t개의 줄에 걸쳐서 각 테스트 케이스에 대해 성희가 민성이한테 알려줄 수를 출력합니다. 단, 민성이가 만든 수가 가장 큰 수일 경우 성희가 더 큰 수를 만드는 것이 불가능하므로 -1을 출력합니다.
관찰
먼저 가장 쉬운 방법을 생각해봅시다. N개의 자릿수가 있다면, 이를 나열하여 만들 수 있는 모든 수들을 직접 만들어보아 민성이가 만든 수와 비교할 수 있습니다. N개를 나열하는 경우의 수는 모두 N! 만큼의 경우가 생기게 됩니다. 만약 N이 10보다 작다면, 10! = 3,628,800이기 때문에 이를 이용해 만들 수 있는 수는 아무리 많아도 500만개를 넘지 않아, 이를 직접 정렬해보는 것으로 해결할 수도 있을 것입니다.
하지만 N!은 매우 크게 증가하는 수입니다. 즉, N이 조금만 커져도 기하급수적으로 실행시간이 늘어나게 되어 다른 방법을 찾아봐야합니다.
그렇다면, N이 매우 커서 만들 수 있는 수가 굉장히 많은데도 어떻게 성희가 원하는 수를 찾을 수 있을까요? 그 실마리는 민성이가 만든 수보다 큰 수는 매우 많을 수 있지만, 우리가 필요로 하는 수는 그 수들 중 ‘가장 작은 수’ 하나에만 해당한다는 사실에 있습니다.
위의 예시를 봅시다. 민성이가 7113521을 만들고, 성희는 7115123을 만들었습니다. 이 때, 성희가 만든 수와 민성이가 만든 수 중, 변하지 않은 부분을 볼 수 있을까요? 성희가 천의 자리 숫자를 1 이상 증가시켜 값을 더 크게 만들었습니다. 이 때, 만의 자리 이상의 자릿수들은 더 크게할 경우 현재 성희가 만드는 숫자보다 커지게 되고, 더 작게하면 민성이가 만든 수보다도 더 작게 됩니다. 즉, 우리가 변화시키려는 최대 자릿수보다 더 큰 자리의 수들은 바꾸어도 절대 우리가 원하는 답이 될 수 없습니다.
처음 주어진 문제는 7개의 자릿수를 이용하는 문제였지만, 위의 관찰을 통해 우리는 711을 고정시켜야함을 통해, 3521을 5123으로 바꾸는 문제로 바꿀 수 있었습니다.
그렇다면, 천의 자리를 고치지 않고, 백의 자리까지만 고쳐 답을 구할 수 있을까요? 아까의 관찰을 이용하면, 우리는 3도 고정시키게 되어 521보다 더 큰 수를 만드는 문제로 바뀌게 됩니다. 하지만 5, 2, 1을 이용하여 521보다 더 큰 수는 만들 수가 없습니다. 왜냐하면, 521은, 5, 2, 1 중 가장 큰 자릿수부터 가장 큰 자릿수에 넣어 만들었기 때문입니다. 즉, 특정 자릿수까지 내림차순으로 이루어졌을 경우, 이보다 더 큰 수는 만들 수 없습니다.
결국, 우리는 내림차순을 만족하지 않는 최소의 자릿수를 찾아 그보다 더 큰 최소의 수를 만드는 것으로 문제를 해결할 수 있게 됩니다.
풀이
우리는 관찰을 통해, 더 이상 내림차순을 만족하지 않게 되는 최소의 자릿수를 찾아 값을 변화시켜야 한다는 것을 알게 되었습니다. 이는 1의 자릿수부터 시작해, 현재 자릿수보다 다음 자릿수의 값이 작게 되는 최초의 자릿수를 찾는 것으로 찾아낼 수 있습니다. 그렇다면, 그 아래의 자릿수들을 이용해 민성이의 값보다 큰 가장 작은 값은 어떻게 만들 수 있을까요?
변화시켜야하는 자리의 위치를 오른쪽에서부터 세었을 때, i번 위치라고 합시다. 그러면 i번 위치의 값은, 1 ~ i-1번 위치의 값들 중 i번 위치보다 크며, 나머지 값들 보단 가장 작은 값을 이용해 만들어야합니다(그보다 더 큰 값을 이용하면, 항상 더 작게 만들 수 있으므로). 편의상, 이 때의 위치를 j라고 합시다. 이제 i번 값과 j번 값을 바꾸어주면, 1 ~ i-1번 값들이 어떻게 배치돼도 항상 민성이의 수보다 커지게 됩니다. 즉, 우리는 남은 수를 이용해 가장 작은 수를 만들어주면 되므로, 값이 작은 순서대로 i-1번 위치부터 채워주면 됩니다.
위에 설명한 내용은, 스택의 ‘원소들의 들어오고 나가는 순서가 유지된다’는 성질을 이용하면 좀 더 깔끔하게 구현할 수 있습니다.
- 2개의 스택을 준비합니다.
- 1의 자리 자릿수부터 차례대로 1번 스택에 넣으며, 스택의 가장 위에 있는 수가 현재 보고있는 자릿수(편의상 i번 자릿수라 사용)보다 커질 때까지 넣어줍니다.
- 1번 스택의 탑에 있는 수가 i번 자릿수보다 크지 않을 때까지, 1번 스택의 탑을 2번 스택으로 옮겨줍니다.
- i번 자릿수를 1번 스택으로 옮기고, 2번 스택의 탑을 i번 자릿수로 옮깁니다.
- 1번 스택을 모두 2번 스택으로 옮깁니다.
- 2번 스택에 있는 값들을 순서대로 i-1~1번 자릿수로 옮깁니다.
스택에 들어가는 원소들은 항상 오름차순, 혹은 내림차순의 정렬순서가 유지되기 때문에, 위와 같이 1번 스택은 오름차순, 2번 스택은 내림차순 순서로 원소를 넣어주는 것으로 쉽게 구현할 수 있습니다.
그렇다면 -1을 출력하는 경우는 어떻게 알 수 있을까요?
애초에 주어진 자릿수에 사용된 수들이 내림차순으로 정렬되어있다면 가장 큰 수에 해당한다는 사실을 알 수 있습니다. 이것을 처음에 예외를 통해 처리해주는 것이 가능합니다. 혹은 우리가 구현한 과정에서 위 조건을 만족한다면, 스택에는 모든 수들이 다 들어가게 되므로 모든 수를 조건에 맞게 스택에 넣는 것이 가능하다면 -1을 출력하는 식으로 처리해주셔도 됩니다.
스택을 사용하지 않는 방법으로는, 큐를 이용하여도 구현할 수 있습니다. 동작 원리는 스택과 비슷하게 할 수 있으므로 사용하기 더 편한 자료구조를 사용해주시면 됩니다.
코드
두 배열의 합 - 풀이 1
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int T, n, m, ncnt, mcnt;
ll res;
int A[1010], B[1010], Aarr[1000010], Barr[1000010];
int main(){
int i, j, c, d, sum;
scanf("%d", &T);
scanf("%d", &n);
for(i = 0; i < n; i++) scanf("%d", &A[i]);
scanf("%d", &m);
for(i = 0; i < m; i++) scanf("%d", &B[i]);
for(i = 0; i < n; i++){
sum = 0;
for(j = i; j < n; j++){
sum += A[j];
Aarr[ncnt++] = sum;
}
}
for(i = 0; i < m; i++){
sum = 0;
for(j = i; j < m; j++){
sum += B[j];
Barr[mcnt++] = sum;
}
}
sort(Aarr, Aarr + ncnt);
sort(Barr, Barr + mcnt);
i = 0; j = mcnt - 1;
while(i < ncnt){
c = i + 1;
while(c < ncnt && Aarr[c] == Aarr[i]) c++;
while(j >= 0 && Barr[j] + Aarr[i] > T) j--;
if(j < 0 || Barr[j] + Aarr[i] != T){ i = c; continue; }
d = j - 1;
while(d >= 0 && Barr[d] == Barr[j]) d--;
res += 1ll * (c - i) * (j - d);
i = c; j = d;
}
printf("%lld", res);
return 0;
}
두 배열의 합 - 풀이 2
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int T, n, m, ncnt, mcnt;
ll res;
int A[1010], B[1010], Aarr[1000010], Barr[1000010];
int main(){
int i, j, c, d, sum;
scanf("%d", &T);
scanf("%d", &n);
for(i = 0; i < n; i++) scanf("%d", &A[i]);
scanf("%d", &m);
for(i = 0; i < m; i++) scanf("%d", &B[i]);
for(i = 0; i < n; i++){
sum = 0;
for(j = i; j < n; j++){
sum += A[j];
Aarr[ncnt++] = sum;
}
}
for(i = 0; i < m; i++){
sum = 0;
for(j = i; j < m; j++){
sum += B[j];
Barr[mcnt++] = sum;
}
}
sort(Barr, Barr + mcnt);
for(i = 0; i < ncnt; i++){
res += upper_bound(Barr, Barr + mcnt, T - Aarr[i]) - lower_bound(Barr, Barr + mcnt, T - Aarr[i]);
}
printf("%lld", res);
return 0;
}
JNEXT
#include <bits/stdc++.h>
using namespace std;
int T, n;
int arr[1000010];
char rarr[1000010];
stack <int> st, st2;
int main(){
int p, i;
scanf("%d", &T);
for(p = 1; p <= T; p++){
scanf("%d", &n);
for(i = 0; i < n; i++) scanf("%d", &arr[i]); st.push(-1);
for(i = n - 1; i >= 0; i--){
if(st.top() <= arr[i]) st.push(arr[i]);
else{
while(st.top() > arr[i]) st2.push(st.top()), st.pop();
st.push(arr[i]);
arr[i++] = st2.top();
st2.pop();
while(!st.empty()) st2.push(st.top()), st.pop(); st2.pop();
while(!st2.empty()) arr[i++] = st2.top(), st2.pop();
break;
}
}
if(i == -1) printf("-1\n");
else{
for(i = 0; i < n; i++) rarr[i] = '0' + arr[i];
rarr[n] = 0;
printf("%s\n", rarr);
}
while(!st.empty()) st.pop();
while(!st2.empty()) st2.pop();
}
return 0;
}