C++로 특정 위치에 여는 괄호가 고정된 균형 잡힌 괄호 표현식의 개수 구하기

정수 m과 위치 배열 position[](1 ≤ length(position[]) ≤ 2m)이 주어졌을 때, 길이가 2m인 올바른 괄호 표현식(proper bracket expression)을 만들 수 있는 경우의 수를 구하는 문제입니다. 단, 지정된 위치에는 반드시 여는 괄호가 와야 합니다.

참고: position[] 배열은 1 기반 인덱싱 형태의 [0, 1, 1, 0]과 같이 제공됩니다. 값이 1인 위치에는 반드시 여는 괄호가 배치되어야 하며, 값이 0인 위치에는 여는 괄호 또는 닫는 괄호 중 어느 것이든 자유롭게 배치할 수 있습니다.

예제

입력: n = 2, position[] = [1, 0, 1, 0]
출력: 1
유일하게 가능한 경우:
[ ] [ ]

이 문제는 재귀(Recursion) 방식과 메모이제이션(Memoization)을 적용한 재귀 방식으로 해결할 수 있습니다.

알고리즘

먼저 주어진 배열(예: adj1)에서 여는 괄호가 반드시 와야 하는 모든 위치를 1로 표시합니다. 그다음 다음과 같은 재귀 로직을 실행합니다.

• (여는 괄호 개수 − 닫는 괄호 개수)로 계산한 총 괄호 카운트가 0보다 작아지면 0을 반환합니다.

• 인덱스가 m에 도달했을 때 총 괄호 카운트가 0이면 균형 잡힌 표현식이 완성된 것이므로 1을 반환하고, 그렇지 않으면 0을 반환합니다.

• 현재 인덱스에 미리 1이 할당되어 있다면, 총 괄호 카운트를 1 증가시키고 인덱스를 index+1로 하여 함수를 재귀적으로 호출합니다.

• 그렇지 않은 경우, 해당 위치에 여는 괄호를 넣는 경우(총 괄호 카운트 +1)와 닫는 괄호를 넣는 경우(총 괄호 카운트 −1)를 각각 재귀 호출하여 그 합을 반환하고, 다음 인덱스로 진행합니다.

재귀를 이용한 구현 예제

// 위 알고리즘을 재귀로 구현한 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;

// 올바른 괄호 표현식의 개수를 찾는 함수
int find(int index1, int openbrk1, int m, int adj1[]) {
    // 여는 괄호 - 닫는 괄호가 0보다 작으면
    if (openbrk1 < 0)
        return 0;

    // 인덱스가 표현식의 끝에 도달한 경우
    if (index1 == m) {
        // 괄호가 균형 잡혀 있는지 확인
        if (openbrk1 == 0)
            return 1;
        else
            return 0;
    }

    // 현재 인덱스에 여는 괄호가 미리 지정된 경우
    if (adj1[index1] == 1) {
        // 여는 괄호 개수를 늘리며 앞으로 진행
        return find(index1 + 1, openbrk1 + 1, m, adj1);
    }
    else {
        // 해당 인덱스에 여는 괄호와 닫는 괄호를
        // 각각 넣는 두 가지 경우를 모두 탐색
        return find(index1 + 1, openbrk1 + 1, m, adj1)
             + find(index1 + 1, openbrk1 - 1, m, adj1);
    }
}

// 드라이버 코드
int main() {
    int m = 2;
    // 1번 위치에 여는 괄호 지정
    int adj1[4] = { 1, 0, 0, 0 };
    // find 함수를 호출하여 정답 계산
    cout << find(0, 0, 2 * m, adj1) << endl;
    return 0;
}

출력

2

메모이제이션(Memoization)을 활용한 최적화

위 알고리즘의 시간 복잡도는 메모이제이션을 적용하면 개선할 수 있습니다. 핵심 아이디어는 배열(dp)을 사용해 이전에 계산한 결과를 저장하는 것입니다. 이미 계산된 값이라면 동일한 함수를 재귀적으로 다시 호출하지 않고 저장된 값을 바로 사용하면 됩니다.

구현 예제

// 위 방법을 메모이제이션으로 구현한 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;
#define M 1000

// 올바른 괄호 표현식의 개수를 찾는 함수
int find(int index1, int openbrk1, int m,
         int dp1[M][M], int adj1[]) {
    // 여는 괄호 - 닫는 괄호가 0보다 작으면
    if (openbrk1 < 0)
        return 0;

    // 인덱스가 표현식의 끝에 도달한 경우
    if (index1 == m) {
        // 괄호가 균형 잡혀 있는지 확인
        if (openbrk1 == 0)
            return 1;
        else
            return 0;
    }

    // dp1에 이미 저장된 값이 있으면 그대로 반환
    if (dp1[index1][openbrk1] != -1)
        return dp1[index1][openbrk1];

    // 현재 인덱스에 여는 괄호가 미리 지정된 경우
    if (adj1[index1] == 1) {
        // 여는 괄호 개수를 늘리며 앞으로 진행
        dp1[index1][openbrk1] = find(index1 + 1,
                                     openbrk1 + 1, m, dp1, adj1);
    }
    else {
        // 해당 인덱스에 여는 괄호와 닫는 괄호를
        // 각각 넣는 두 가지 경우를 모두 탐색
        dp1[index1][openbrk1] =
              find(index1 + 1, openbrk1 + 1, m, dp1, adj1)
            + find(index1 + 1, openbrk1 - 1, m, dp1, adj1);
    }

    // 계산된 결과 반환
    return dp1[index1][openbrk1];
}

// 드라이버 코드
int main() {
    // 정답을 미리 계산하기 위한 dp1 배열
    int dp1[M][M];
    int m = 2;
    memset(dp1, -1, sizeof(dp1));

    // 1번 위치에 여는 괄호 지정
    int adj1[4] = { 1, 0, 0, 0 };

    // find 함수를 호출하여 정답 계산
    cout << find(0, 0, 2 * m, dp1, adj1) << endl;
    return 0;
}

출력

2

시간 복잡도

단순 재귀 방식은 같은 상태를 중복해서 계산하므로 비효율적일 수 있지만, 메모이제이션을 적용하면 각 (인덱스, 열린 괄호 개수) 상태를 한 번씩만 계산하므로 전체 시간 복잡도는 O(N²)이 됩니다.