C/C++로 연속된 1이 없는 이진 문자열의 개수 구하기

이번에는 흥미로운 문제 하나를 살펴보겠습니다. 값 n이 주어졌을 때, 길이가 n이면서 연속된 1(11)이 포함되지 않는 모든 이진 문자열의 개수를 구하는 것입니다.

예를 들어 n = 2라면 가능한 문자열은 {00, 01, 10} 세 가지뿐이므로 출력 결과는 3이 됩니다. '11'은 연속된 1을 포함하므로 제외됩니다.

동적 계획법(Dynamic Programming)을 이용한 풀이

이 문제는 동적 계획법으로 효율적으로 해결할 수 있습니다. 두 개의 배열 a와 b를 사용합니다.

• a[i]: 길이가 i이고, 연속된 1이 없으며, 마지막 문자가 0으로 끝나는 이진 문자열의 개수
• b[i]: 같은 조건에서 마지막 문자가 1로 끝나는 이진 문자열의 개수

핵심 규칙은 다음과 같습니다. 마지막 문자가 0인 문자열에는 뒤에 0 또는 1을 자유롭게 붙일 수 있지만, 마지막 문자가 1인 문자열에는 연속된 1이 생기지 않도록 반드시 0만 붙여야 합니다.

점화식

a[i] = a[i-1] + b[i-1]
b[i] = a[i-1]

즉, 길이 i에서 0으로 끝나는 문자열의 수는 이전 단계의 전체 경우의 수에 0을 붙인 것이고, 1로 끝나는 문자열의 수는 이전 단계에서 0으로 끝난 경우에만 1을 붙인 것입니다.

알고리즘

noConsecutiveOnes(n) −

Begin
    define array a and b of size n
    a[0] := 1
    b[0] := 1
    for i in range 1 to n, do
        a[i] := a[i-1] + b[i - 1]
        b[i] := a[i - 1]
    done
    return a[n-1] + b[n-1]
End

C/C++ 구현 예제

#include <iostream>
using namespace std;
int noConsecutiveOnes(int n) {
    int a[n], b[n];
    a[0] = 1;
    b[0] = 1;
    for (int i = 1; i < n; i++) {
        a[i] = a[i-1] + b[i-1];
        b[i] = a[i-1];
    }
    return a[n-1] + b[n-1];
}
int main() {
    cout << noConsecutiveOnes(4) << endl;
}

실행 결과

8

n = 4일 때 결과는 8입니다. 실제로 길이 4의 이진 문자열 중 연속된 1이 없는 경우는 {0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010}으로 정확히 8개입니다.

이 알고리즘은 각 단계에서 상수 시간의 연산만 수행하므로 전체 시간 복잡도는 O(n)이며, 공간 복잡도 역시 O(n)입니다. 두 개의 변수만 유지하면 공간을 O(1)로 최적화할 수도 있습니다.