← 전체 회차
A-024● Day 242026.05.28mediumleetcode #22neetcode150

괄호 생성하기

#string#dynamic-programming#backtracking
↗ leetcode #22 · generate-parentheses
01

문제

· problem
P.024

괄호 생성하기

↗ leetcode #22

n개의 괄호 쌍이 주어졌을 때, 올바르게 형성된 괄호의 모든 조합을 생성하는 함수를 작성하시오.

제약
  • · 1 ≤ n ≤ 8
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
3
["((()))","(()())","(())()","()(())","()()()"]
example 2input → output
1
["()"]
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    올바르게 형성된 괄호란 정확히 무엇인가?
  • ☐
    출력이 특정 순서로 정렬되어야 하는가?
  • ☐
    n=3일 때 총 몇 개의 괄호 문자가 있는가?
  • ☐
    모든 2^(2n)개의 이진 조합을 생성한 후 필터링하는 것이 좋은 접근법인가?
  • ☐
    임의의 시점에서 열린 괄호와 닫힌 괄호의 개수 사이에는 어떤 관계가 있어야 하는가?
  • ☐
    첫 번째에 n개의 열린 괄호를 모두 사용한 후 닫힌 괄호를 추가할 수 있는가?
  • ☐
    주어진 n에 대해 정확히 몇 개의 올바른 조합이 존재하는가?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 스택 초기화
○
stack = []
○
res = []
○
stack = set()
○
stack = {}
step 2· 결과 리스트 초기화
○
res = []
○
res = set()
○
res = {}
step 3· 기저 사례 확인│ 중첩
○
if openN == closedN == n:
○
if openN == n:
○
if openN + closedN == 2 * n:
○
if len(stack) == 2 * n:
step 4· 열린 괄호 추가 조건│ 중첩
○
if openN < n:
○
if openN <= n:
○
if closedN < openN:
○
if openN < closedN:
step 5· 닫힌 괄호 추가 조건│ 중첩
○
if closedN < openN:
○
if closedN <= openN:
○
if closedN < n:
○
if openN < n:
step 6· 백트래킹 시작
○
backtrack(0, 0)
○
backtrack(1, 0)
○
backtrack(n, n)
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def generateParenthesis(self, n: int) -> List[str]:
3
        stack = []
4
        res = []
5
6
        def backtrack(openN, closedN):
7
            if openN == closedN == n:
8
                res.append("".join(stack))
9
                return
10
11
            if openN < n:
12
                stack.append("(")
13
                backtrack(openN + 1, closedN)
14
                stack.pop()
15
            if closedN < openN:
16
                stack.append(")")
17
                backtrack(openN, closedN + 1)
18
                stack.pop()
19
20
        backtrack(0, 0)
21
        return res
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
3
→
["((()))","(()())","(())()","()(())","()()()"]
case 2
1
→
["()"]
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.