균형 잡힌 괄호 수열¶
균형 잡힌 괄호 수열이란 괄호로만 이루어진 문자열 가운데, 적절한 숫자와 수학 연산을 삽입하면 올바른 수식이 되는 것을 말합니다. 균형 잡힌 괄호 수열은 형식적으로 다음과 같이 정의할 수 있습니다.
- $e$(빈 문자열)는 균형 잡힌 괄호 수열입니다.
- $s$가 균형 잡힌 괄호 수열이면 $(s)$도 균형 잡힌 괄호 수열입니다.
- $s$와 $t$가 균형 잡힌 괄호 수열이면 $s t$도 균형 잡힌 괄호 수열입니다.
예를 들어 $(())()$는 균형 잡힌 괄호 수열이지만 $())($는 그렇지 않습니다.
물론 여러 종류의 괄호를 사용하는 다른 괄호 수열도 비슷한 방식으로 정의할 수 있습니다.
이 글에서는 균형 잡힌 괄호 수열(간단히 수열이라고만 부르겠습니다)과 관련된 몇 가지 고전적인 문제를 다룹니다. 검증, 수열의 개수, 사전순으로 다음 수열 찾기, 특정 크기의 모든 수열 생성, 수열의 인덱스 찾기, 그리고 $k$번째 수열 생성입니다. 또한 각 문제의 두 가지 변형, 즉 한 종류의 괄호만 허용되는 더 간단한 경우와 여러 종류가 있는 더 어려운 경우를 함께 다룹니다.
균형 검증¶
주어진 문자열이 균형 잡혀 있는지 확인하고자 합니다.
먼저 괄호가 한 종류뿐이라고 가정합시다. 이 경우에는 매우 간단한 알고리즘이 있습니다. $\text{depth}$를 현재 열려 있는 괄호의 개수라고 합시다. 처음에는 $\text{depth} = 0$입니다. 문자열의 모든 문자를 순회하면서, 현재 괄호 문자가 여는 괄호이면 $\text{depth}$를 증가시키고, 그렇지 않으면 감소시킵니다. 어느 시점에서든 변수 $\text{depth}$가 음수가 되거나, 마지막에 $0$과 다르다면 그 문자열은 균형 잡힌 괄호열이 아닙니다. 그렇지 않다면 균형 잡힌 수열입니다.
여러 종류의 괄호가 포함된 경우에는 알고리즘을 바꿔야 합니다. 카운터 $\text{depth}$ 대신 스택을 만들고, 만나는 모든 여는 괄호를 이 스택에 저장합니다. 현재 괄호 문자가 여는 괄호이면 스택에 넣습니다. 닫는 괄호이면 스택이 비어 있지 않은지, 그리고 스택의 맨 위 원소가 현재 닫는 괄호와 같은 종류인지 확인합니다. 두 조건이 모두 충족되면 스택에서 여는 괄호를 제거합니다. 어느 시점에서든 조건 중 하나라도 충족되지 않거나, 마지막에 스택이 비어 있지 않다면 그 문자열은 균형 잡혀 있지 않습니다. 그렇지 않다면 균형 잡혀 있습니다.
균형 잡힌 괄호열의 개수¶
공식¶
괄호가 한 종류뿐인 균형 잡힌 괄호 수열의 개수는 카탈랑 수를 이용해 계산할 수 있습니다. 길이가 $2n$인($n$쌍의 괄호로 이루어진) 균형 잡힌 괄호 수열의 개수는 다음과 같습니다.
$k$종류의 괄호를 허용하면 각 쌍은 (다른 쌍과 독립적으로) $k$종류 중 어느 것이든 될 수 있으므로, 균형 잡힌 괄호 수열의 개수는 다음과 같습니다.
동적 계획법¶
한편 이 수들은 동적 계획법을 사용하여 계산할 수도 있습니다. $d[n]$을 괄호 쌍이 $n$개인 올바른 괄호 수열의 개수라고 합시다. 첫 번째 위치에는 항상 여는 괄호가 온다는 점에 유의하십시오. 그리고 그 뒤 어딘가에 이 쌍에 대응하는 닫는 괄호가 있습니다. 이 쌍의 안쪽에는 균형 잡힌 괄호 수열이 있고, 마찬가지로 이 쌍의 뒤쪽에도 균형 잡힌 괄호 수열이 있다는 것은 분명합니다. 따라서 $d[n]$을 계산하기 위해, 이 첫 번째 괄호 쌍 안에 올 수 있는 괄호 쌍 $i$개짜리 균형 잡힌 괄호열이 몇 개인지, 그리고 이 쌍 뒤에 올 수 있는 괄호 쌍 $n-1-i$개짜리 균형 잡힌 괄호열이 몇 개인지를 살펴봅니다. 결과적으로 공식은 다음과 같은 형태입니다:
이 점화식의 초깃값은 $d[0] = 1$입니다.
사전순으로 다음 균형 잡힌 괄호열 찾기¶
여기서는 유효한 괄호 종류가 하나인 경우만 고려합니다.
균형 잡힌 괄호열이 주어졌을 때, (사전순으로) 다음 균형 잡힌 괄호열을 찾아야 합니다.
이 위치까지 닫는 괄호가 여는 괄호보다 많아서는 안 된다는 조건을 위반하지 않으면서 닫는 괄호로 바꿀 수 있는 가장 오른쪽의 여는 괄호를 찾아야 한다는 것은 명백합니다. 이 위치를 바꾼 뒤에는 문자열의 나머지 부분을 사전순으로 가장 작은 것으로 채울 수 있습니다. 즉, 먼저 여는 괄호를 가능한 한 많이 채우고, 남은 위치를 닫는 괄호로 채웁니다. 다시 말해, 가능한 한 긴 접두사를 바꾸지 않고 남겨 두고, 접미사는 사전순으로 가장 작은 것으로 바꿉니다.
이 위치를 찾기 위해 문자를 오른쪽에서 왼쪽으로 순회하면서 여는 괄호와 닫는 괄호의 균형값 $\text{depth}$를 유지할 수 있습니다. 여는 괄호를 만나면 $\text{depth}$를 감소시키고, 닫는 괄호를 만나면 증가시킵니다. 어느 시점에서 여는 괄호를 만났고 이 기호를 처리한 후의 균형값이 양수라면, 바꿀 수 있는 가장 오른쪽 위치를 찾은 것입니다. 그 기호를 바꾸고, 오른쪽에 추가해야 하는 여는 괄호와 닫는 괄호의 개수를 계산한 다음, 이들을 사전순으로 가장 작은 방식으로 배치합니다.
적절한 위치를 찾지 못하면 이 괄호열은 이미 가능한 최대의 괄호열이며, 답이 없습니다.
bool next_balanced_sequence(string & s) {
int n = s.size();
int depth = 0;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == '(')
depth--;
else
depth++;
if (s[i] == '(' && depth > 0) {
depth--;
int open = (n - i - 1 - depth) / 2;
int close = n - i - 1 - open;
string next = s.substr(0, i) + ')' + string(open, '(') + string(close, ')');
s.swap(next);
return true;
}
}
return false;
}
이 함수는 $O(n)$ 시간에 다음 균형 잡힌 괄호 수열을 계산하며, 다음 수열이 없으면 false를 반환합니다.
모든 균형 잡힌 괄호열 찾기¶
때로는 특정 길이 $n$의 균형 잡힌 괄호 수열을 모두 찾아 출력해야 합니다.
이들을 생성하려면 사전순으로 가장 작은 괄호열 $((\dots(())\dots))$에서 시작하여, 이전 절에서 설명한 알고리즘으로 사전순 다음 괄호열을 계속 찾으면 됩니다.
그러나 괄호열의 길이가 그다지 길지 않다면(예: $n$이 $12$보다 작은 경우), C++ STL 함수 next_permutation으로 모든 순열을 편리하게 생성하고 각각이 균형 잡혀 있는지 확인할 수도 있습니다.
또한 동적 계획법으로 모든 괄호열의 개수를 셀 때 사용한 아이디어를 이용하여 이들을 생성할 수도 있습니다. 이 아이디어는 이어지는 두 절에서 다룹니다.
괄호열의 인덱스¶
괄호 쌍이 $n$개인 균형 잡힌 괄호 수열이 주어집니다. 괄호 쌍이 $n$개인 모든 균형 잡힌 괄호열을 사전순으로 정렬한 목록에서 이 괄호열의 인덱스를 찾아야 합니다.
보조 배열 $d[i][j]$를 정의합시다. 여기서 $i$는 괄호 수열(준균형, 즉 모든 닫는 괄호에는 대응하는 여는 괄호가 있지만 모든 여는 괄호에 반드시 대응하는 닫는 괄호가 있는 것은 아닌 수열)의 길이이고, $j$는 현재 균형(여는 괄호와 닫는 괄호 개수의 차이)입니다. $d[i][j]$는 이 매개변수에 맞는 수열의 개수입니다. 이 수들은 괄호 종류가 하나인 경우에 대해서만 계산합니다.
시작값 $i = 0$에 대해서는 답이 자명합니다: $d[0][0] = 1$이고, $j > 0$에 대해 $d[0][j] = 0$입니다. 이제 $i > 0$이라 하고, 수열의 마지막 문자를 살펴봅시다. 마지막 문자가 여는 괄호 $($였다면 이전 상태는 $(i-1, j-1)$이었고, 닫는 괄호 $)$였다면 이전 상태는 $(i-1, j+1)$이었습니다. 따라서 다음과 같은 재귀 공식을 얻습니다:
음수 $j$에 대해서는 당연히 $d[i][j] = 0$이 성립합니다. 따라서 이 배열을 $O(n^2)$에 계산할 수 있습니다.
이제 주어진 수열의 인덱스를 구해 봅시다.
먼저 괄호의 종류가 한 가지뿐이라고 합시다. 현재 얼마나 깊이 중첩되어 있는지를 알려 주는 카운터 $\text{depth}$를 사용하여 수열의 문자들을 순회하겠습니다. 현재 문자 $s[i]$가 $($와 같으면 $\text{depth}$를 1 증가시킵니다. 현재 문자 $s[i]$가 $)$와 같으면, $($로 시작하는 가능한 모든 끝부분(사전순으로 더 작은 수열들)을 고려하여 답에 $d[2n-i-1][\text{depth}+1]$을 더한 뒤 $\text{depth}$를 1 감소시켜야 합니다.
이제 서로 다른 괄호 종류가 $k$가지 있다고 합시다.
따라서 $\text{depth}$를 다시 계산하기 전에 현재 문자 $s[i]$를 볼 때, 현재 문자보다 작은 모든 괄호 종류를 차례로 살펴보며 그 괄호를 현재 위치에 놓아 보고(새로운 균형 $\text{ndepth} = \text{depth} \pm 1$을 얻음), 수열을 마무리하는 방법의 수(길이 $2n-i-1$, 균형 $ndepth$)를 답에 더해야 합니다:
이 공식은 다음과 같이 유도할 수 있습니다: 먼저 괄호 종류가 여러 가지라는 사실을 "잊고" 답 $d[2n - i - 1][\text{ndepth}]$를 그대로 취합니다. 이제 괄호 종류가 $k$가지일 때 답이 어떻게 달라지는지 살펴봅시다. 정해지지 않은 위치가 $2n - i - 1$개 있으며, 그중 $\text{ndepth}$개는 여는 괄호들 때문에 이미 결정되어 있습니다. 하지만 나머지 괄호들($(2n - i - 1 - \text{ndepth})/2$쌍)은 어떤 종류든 될 수 있으므로, 그 수에 $k$의 해당 거듭제곱을 곱합니다.
$k$번째 수열 찾기¶
수열에 있는 괄호 쌍의 개수를 $n$이라 합시다. 주어진 $k$에 대해, 모든 균형 잡힌 괄호열을 사전순으로 정렬한 목록에서 $k$번째 균형 잡힌 괄호열을 찾아야 합니다.
이전 절과 마찬가지로 보조 배열 $d[i][j]$를 계산합니다. 이는 길이가 $i$이고 균형이 $j$인 준(準)균형, 즉 반쯤 균형 잡힌 괄호 수열의 개수입니다.
먼저 괄호 종류가 한 가지뿐인 경우부터 시작합니다.
생성하려는 문자열의 문자들을 순회하겠습니다. 이전 문제와 마찬가지로 현재 중첩 깊이를 나타내는 카운터 $\text{depth}$를 저장합니다. 각 위치에서 여는 괄호를 놓을지 닫는 괄호를 놓을지 결정해야 합니다. 여는 괄호를 놓으려면 $d[2n - i - 1][\text{depth}+1] \ge k$가 참이어야 합니다. 그렇다면 카운터 $\text{depth}$를 1 증가시키고 다음 문자로 넘어갑니다. 그렇지 않다면 $k$에서 $d[2n - i - 1][\text{depth}+1]$을 빼고, 닫는 괄호를 놓은 뒤 다음으로 넘어갑니다.
string kth_balanced(int n, int k) {
vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
d[0][0] = 1;
for (int i = 1; i <= 2*n; i++) {
d[i][0] = d[i-1][1];
for (int j = 1; j < n; j++)
d[i][j] = d[i-1][j-1] + d[i-1][j+1];
d[i][n] = d[i-1][n-1];
}
string ans;
int depth = 0;
for (int i = 0; i < 2*n; i++) {
if (depth + 1 <= n && d[2*n-i-1][depth+1] >= k) {
ans += '(';
depth++;
} else {
ans += ')';
if (depth + 1 <= n)
k -= d[2*n-i-1][depth+1];
depth--;
}
}
return ans;
}
이제 괄호 종류가 $k$가지 있다고 합시다. 풀이는 값 $d[2n-i-1][\text{ndepth}]$에 $k^{(2n-i-1-\text{ndepth})/2}$를 곱해야 하고, 다음 문자에 여러 종류의 괄호가 올 수 있음을 고려해야 한다는 점만 약간 다릅니다.
다음은 소괄호와 대괄호, 두 종류의 괄호를 사용하는 구현입니다:
string kth_balanced2(int n, int k) {
vector<vector<int>> d(2*n+1, vector<int>(n+1, 0));
d[0][0] = 1;
for (int i = 1; i <= 2*n; i++) {
d[i][0] = d[i-1][1];
for (int j = 1; j < n; j++)
d[i][j] = d[i-1][j-1] + d[i-1][j+1];
d[i][n] = d[i-1][n-1];
}
string ans;
int shift, depth = 0;
stack<char> st;
for (int i = 0; i < 2*n; i++) {
// '('
shift = ((2*n-i-1-depth-1) / 2);
if (shift >= 0 && depth + 1 <= n) {
int cnt = d[2*n-i-1][depth+1] << shift;
if (cnt >= k) {
ans += '(';
st.push('(');
depth++;
continue;
}
k -= cnt;
}
// ')'
shift = ((2*n-i-1-depth+1) / 2);
if (shift >= 0 && depth && st.top() == '(') {
int cnt = d[2*n-i-1][depth-1] << shift;
if (cnt >= k) {
ans += ')';
st.pop();
depth--;
continue;
}
k -= cnt;
}
// '['
shift = ((2*n-i-1-depth-1) / 2);
if (shift >= 0 && depth + 1 <= n) {
int cnt = d[2*n-i-1][depth+1] << shift;
if (cnt >= k) {
ans += '[';
st.push('[');
depth++;
continue;
}
k -= cnt;
}
// ']'
ans += ']';
st.pop();
depth--;
}
return ans;
}