[DSA][Backtracking] 06. Catalan Numbers

Problem

지난번 Generate Parenthesis 문제에서 정수 n이 주어졌을 때 만들 수 있는 모든 유효한 괄호 문자열(valid parentheses)을 구했는데 (2025.12.04 - [자료구조와 알고리즘] - [DSA][Backtracking] 06. Generate Parentheses), 이 문제를 분석하다 보면 아래와 같은 다소 직관적으로 이해하기 어려운 시간 복잡도가 등장한다.

이번 포스팅에서는 이 복잡도가 어디서 나오는 결과인지를 수학적·직관적으로 살펴보자.

 

먼저 문제 조건을 다시 해석해 보자.

괄호 쌍이 n개라는 것은 여는 괄호 '('가 n개, 닫는 괄호 ')'가 n개로 총 2n개의 문자가 주어진다는 뜻이다. 이 문자들을 나열하는 모든 경우의 수는 2n개의 자리 중에서 '('이 들어갈 n개의 자리를 고르는 경우의 수와 같으므로, 다음과 같이 표현할 수 있다.

하지만 이 중에서 우리가 실제로 원하는 것은 유효한 괄호 문자열(valid parentheses)뿐이다.

 

유효한 괄호 문자열이란 문자열의 어느 위치까지 보더라도, 닫는 괄호 ')'의 개수가 여는 괄호 '('의 개수를 초과하지 않는 문자열이다. 다르게 얘기하면 문자열의 어떤 접두사(prefix)에서도 ')'가 '('보다 먼저 많이 등장하는 경우가 없어야 한다. 만약 어떤 접두사에서 ')'의 개수가 '('보다 많아졌다면, 이는 괄호 쌍 ()을 가능한 만큼 제거했을 때 닫히지 못한 ')'가 남게 된다는 것, 즉, 닫힐 수 없는 괄호가 먼저 등장했다는 뜻이며, 괄호의 짝이 맞을 수 없다는 의미이다.

 

Reflection principle

Reflection principle은 제약을 어긴 경로를, 다른 경로와 1:1로 대응시키는 방법이다. 두 집합 A와 B 사이의 일대일 대응이란,

• 단사(Injective)
  서로 다른 a1, a2 ∈ A는 서로 다른 f(a1), f(a2) ∈ B와 대응된다.
• 전사(Surjective)
  B의 모든 원소 b ∈ B는 f(a) = b가 되도록 하는 어떤 a ∈ A가 존재한다.

'('를  위로 한 칸 이동, ')'를 아래로 한 칸 이동하는 것이라고 생각하자. 그렇다면, 길이가 2n인 괄호 문자열은 0에서 시작하여 위로 n번, 아래로 n번 이동하여 다시 높이 0으로 돌아오는 문제라고 생각할 수 있다. 이 관점에서 유효한 문자열이란, 어떤 상황에서도 ')'가 '('보다 많아서는 안 되기 때문에, 한 번도 0보다 낮은 곳으로 내려가면 안 된다는 것을 의미한다.

어떤 지점에서 높이가 0보다 낮아졌다는 것은,  '('가 k개 있을 때 ')'가 k + 1개 있었다는 의미이므로 그 이후의 경로에는 '('가 n - k, ')'가 n - k  - 1개 있을 것이다. 따라서 최초로 0보다 낮아진 지점 이후 경로의 '('와 ')'를 바꾸면 (= x축에 대해 반사, ↑/↓를 바꾼다.) '('가 n - 1개, ')'가 n + 1개 있는 문자열과 같다.

 

Relection Principle의 핵심 아이디어는, 어떤 경로가 처음으로 X축 아래로 내려가는 지점이 있다면 그 지점 이후의 경로를 X축에 대해 반사시켜 새로운 경로를 만들 수 있고, 이를 통해 원래 문제를 더 간단한 조합 문제로 바꿀 수 있다는 것이다. 더 쉽게 결론부터 말하자면 중간에 X축 밑으로 내려오는 지점이 있는 경로와 0에서 시작해서 -2로 끝나는 경로 (='('를 n - 1개, ')를 n + 1개 나열하는 경우의 수)가 일대일 대응이 된다는 것을 보장할 수 있다면 후자의 경우의 수를 세는 것이 훨씬 쉬운데, 반사 원리는 두 개가 같다는 것을 보여준다.

 

집합 A를 중간에 음수가 되는 순간이 존재하는 경로, 집합 B를 0에서 시작해서 −2에서 끝나는 경로라고 하면

 

1) 단사

서로 다른 두 경로 P1, P2 ∈ A에 대해 각 경로에서 처음 음수가 되는 순간 이후를 반사하여 Q1, Q2 ∈B를 생성했다고 가정하자.

Q1, Q2에 대해 최초로 음수가 되는 순간은 P1, P2에서의 순간과 각각 같기 때문에, 해당 지점을  기준으로 반사된 구간을 다시 반사하면 원래의 경로로 완전히 복원이 가능하다. 따라서 P1 ≠ P2라면 Q1 ≠ Q2이다.

 

2) 전사

임의의 경로 Q1 ∈ B이 있다고 하자. 끝점이 -2이므로 Q는 어떤 경로에서는 반드시  -1에서 -2로 내려가는 순간이 있다.

따라서 이 순간의 이후 구간을 전부 반사하면 A의 원소가 되기 때문에 모든 B의 원소에 대응되는 A의 원소가 존재함을 알 수 있다.

 

따라서 유효하지 않은 문자열의 개수는 n + 1개의 '('와 n - 1개의 ')'를 나열하는 조합의 수와 같다.

 

Conclusion

유효한 문자열의 개수는, 전체 경우의 수에서 유효하지 않은 문자열의 개수를 제외한 것이므로

n번째 카탈란 수와 일치한다.