문제 정의
이진수(binary number)는 0과 1, 단 두 개의 숫자만으로 표현되는 수입니다. 모든 이진수는 이진 비트(bit)의 나열로 볼 수 있으며, 이를 이진 문자열(binary string)이라고 부릅니다.
이번 글에서 다룰 문제는 다음과 같습니다. 길이가 N비트인 모든 이진 문자열 중에서, 연속된 1(consecutive 1's)을 포함하지 않는 문자열의 개수를 구하는 것입니다.
예를 들어 N = 5일 때, 주어진 조건을 만족하는 이진 문자열은 다음과 같습니다.
00000 00001 00010 00100 00101
01000 01001 01010 10000 10001
10010 10100 10101
총 13개의 문자열이 존재하며, 어느 문자열에도 '11'처럼 1이 연달아 나오는 경우가 없음을 확인할 수 있습니다.
방법 1: 완전 탐색(Brute Force)
가장 직관적인 방법은 생성 가능한 모든 N자리 이진 문자열을 만들어 보고, 그중 조건을 만족하는 문자열만 골라내는 것입니다. 하지만 N자리 이진 문자열의 개수는 2N개로 지수적으로 증가하기 때문에, N이 커질수록 실행 시간이 급격히 늘어나 실용성이 떨어집니다.
방법 2: 재귀(Recursion) 활용
더 효율적인 방법은 재귀 호출을 이용하는 것입니다. 재귀의 각 단계에서 부분적으로 완성된 문자열 뒤에 0 또는 1을 붙이고, 남은 자릿수를 하나 줄여 다시 재귀 호출을 진행합니다.
여기서 핵심 규칙은 다음과 같습니다.
- 마지막에 붙인 숫자가 0이라면 → 다음 자리에 0과 1을 모두 붙일 수 있습니다.
- 마지막에 붙인 숫자가 1이라면 → 다음 자리에는 반드시 0만 붙일 수 있습니다.
이 규칙을 지키면 출력되는 문자열에 연속된 1이 절대 등장하지 않으므로, 불필요한 탐색 가지를 크게 줄일 수 있습니다.
입력: n = 5
출력: 연속된 1이 없는 5자리 이진 문자열의 개수는 13개입니다.
C++ 구현 예제
#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
if (n == 0)
return 0;
if (n == 1) {
if (last_digit)
return 1;
else
return 2;
}
if (last_digit == 0)
return countStrings(n - 1, 0) + countStrings(n - 1, 1);
else
return countStrings(n - 1, 0);
}
int main() {
int n = 5;
cout << "Number of " << n << "-digit binary strings without any "
"consecutive 1's are " << countStrings(n, 0);
return 0;
}
코드 설명
countStrings(n, last_digit): 앞으로 채워야 할 자릿수가 n개이고, 직전 자릿수가 last_digit일 때 만들 수 있는 유효한 문자열의 개수를 반환합니다.- n = 1이고 직전 숫자가 1이면 마지막 자리에 0만 올 수 있으므로 1을, 직전 숫자가 0이면 0과 1 모두 가능하므로 2를 반환합니다.
- 직전 숫자가 0이면 다음 자리에 0과 1을 각각 붙이는 두 갈래의 합을, 직전 숫자가 1이면 0만 붙이는 한 갈래를 재귀적으로 계산합니다.
참고: 피보나치 수열과의 관계
흥미롭게도 이 문제의 답은 피보나치 수열(Fibonacci sequence)과 밀접한 관련이 있습니다. 길이가 n인 이진 문자열 중 연속된 1이 없는 문자열의 개수는 피보나치 수 F(n+2)와 같습니다. 예를 들어 n = 5일 때 F(7) = 13으로, 위 결과와 일치합니다. 따라서 동적 계획법(DP)으로 피보나치 수를 계산하면 O(n)의 시간 복잡도로 더 빠르게 답을 구할 수 있습니다.