문제 보기 · Level 4 · 연습문제 · 정답률 35% · 푼 사람 3,908명 (2026-09-30 기준)1
문제
괄호 n쌍으로 만들 수 있는 올바른 괄호 문자열(모두 짝이 맞게 닫힌 것)의 개수를 돌려준다.
- 1 ≤ n ≤ 14
풀이
막히면 한 단계씩 펼친다.
필요한 개념
- 동적 계획법: 맨 앞
(와 짝이 되는)의 자리로 경우를 나누면, 안쪽과 바깥쪽이 각각 더 작은 같은 문제가 된다. - 재귀적 정의와 구조적 귀납법: 세는 대상은 그 문서의 균형 괄호다. 그 문서의 규칙 st는 같은 문자열을 여러 방법으로 만든다. ()()()는 ()·()()로도, ()()·()로도 만들어진다. 그래서 규칙 st를 그대로 따라 세면 같은 문자열을 여러 번 센다.
1단계 · 작은 예로 손으로 풀기
n = 3이면 ((())), (()()), (())(), ()(()), ()()()의 5개다.
맨 앞 (의 짝을 기준으로 나눠 본다. 짝 안에 i쌍, 짝 뒤에 3 − 1 − i쌍이 온다.
- 안 0쌍, 뒤 2쌍:
()+ (2쌍 문자열 2개) → ()(()), ()()() - 안 1쌍, 뒤 1쌍:
(())꼴 1개 × 1개 → (())() - 안 2쌍, 뒤 0쌍:
(+ (2쌍 2개) +)→ ((())), (()())
2 + 1 + 2 = 5다.
2단계 · 가장 단순한 방법과 그 속도
괄호 문자열을 모두 만들어 세면 n = 14일 때 약 267만 개를 만든다. 재귀로도 되지만 느리고, 규칙을 쓰면 더하기 몇 번으로 끝난다.
3단계 · 핵심 아이디어
- 상태: dp[k] = 괄호 k쌍으로 만드는 올바른 문자열 수. dp[0] = 1(빈 문자열).
- 점화식: 올바른 문자열은 늘
(로 시작한다. 그(의 짝)안에 i쌍의 올바른 문자열, 짝 뒤에 k − 1 − i쌍의 올바른 문자열이 온다. i마다 두 부분을 따로 고를 수 있으니 dp[i] × dp[k − 1 − i]가지다. dp[k] = Σ dp[i] · dp[k − 1 − i] (i = 0 ~ k − 1). i가 다르면 짝의 자리가 달라 경우끼리 겹치지 않는다. 그래서 i마다의 수를 그대로 더해도 된다. 이 덧셈과 위의 곱이 셈의 기본 법칙의 합의 법칙과 곱의 법칙이다. - 이 수를 카탈란 수(카탈랑 수)라 한다. 닫힌 식은 C(2k, k) / (k + 1)이다2. C(2k, k)는 2k자리 중
(가 들어갈 k자리를 고르는 조합의 수, 곧 짝이 맞든 안 맞든(k개와)k개를 늘어놓는 수다. 그중 1/(k + 1)만 올바르다.
4단계 · 코드 흐름
- dp[0] = 1.
- k = 1 ~ n마다 i = 0 ~ k − 1에 대해 dp[i] · dp[k − 1 − i]를 더한다.
- dp[n]을 돌려준다.
5단계 · 파이썬 코드
def solution(n):
dp = [1] + [0] * n # dp[k]: 괄호 k쌍의 올바른 문자열 수
for k in range(1, n + 1):
for i in range(k): # 첫 "(" 의 짝 안에 i쌍, 뒤에 k-1-i쌍
dp[k] += dp[i] * dp[k - 1 - i]
return dp[n]
[1] + [0] * n: 길이 n + 1의 리스트에서 dp[0]만 1이다.
6단계 · 실행 추적
| k | 계산 | dp[k] |
|---|---|---|
| 0 | 빈 문자열 | 1 |
| 1 | dp[0]·dp[0] | 1 |
| 2 | dp[0]·dp[1] + dp[1]·dp[0] | 2 |
| 3 | dp[0]·dp[2] + dp[1]·dp[1] + dp[2]·dp[0] = 2 + 1 + 2 | 5 |
| 4 | 1·5 + 1·2 + 2·1 + 5·1 | 14 |
n = 14면 2,674,440이다.
7단계 · 복잡도와 흔한 실수
\(O(n^2)\), n = 14면 100번 남짓이다.
- dp[0]을 0으로 두어 모든 값이 0이 된다. 빈 문자열도 한 가지로 센다.
- 짝의 안과 밖을 나누지 않고 “앞에 붙이기/뒤에 붙이기”로 세어 같은 문자열을 여러 번 센다(예: ()()를 두 번).
검증: 문제의 예시 2개를 통과했고, 6단계의 dp 값을 확인했다. n = 1 ~ 10에서 “올바른 문자열을 모두 만든 개수”, 닫힌 식 C(2n, n)/(n + 1)과 같았고, n = 14의 값도 닫힌 식과 같았다 — 30_pg12929_p1.py