이 글에서는 길이가 n인 이진 문자열(binary string) 중에서 연속된 1이 한 번도 등장하지 않는 문자열의 총 개수를 구하는 방법을 알아봅니다.
이진 문자열이란?
2진법(Binary Number System)은 여러 숫자 표현 방식 중 하나로, 디지털 시스템에서 가장 널리 사용되는 체계입니다. 2진법은 오직 두 가지 동작 상태 또는 조건만 가질 수 있는 장치로 표현되는 값을 나타내는 데 활용됩니다. 대표적인 예로 스위치를 들 수 있는데, 스위치는 '열림'과 '닫힘'이라는 두 가지 상태만 가집니다.
2진법에는 0과 1이라는 단 두 개의 기호만 존재합니다. 이진 문자열이란 이처럼 0 또는 1로만 구성된 문자열을 의미합니다.
문제 이해하기
예시를 통해 요구 사항을 살펴보겠습니다.
입력 − n = 2
출력 − 길이가 2이면서 연속된 1이 없는 이진 문자열의 개수 : 3
설명 − 00, 01, 10 세 가지만 가능하므로 개수는 3입니다. 참고로 11은 연속된 1을 포함하므로 제외됩니다.
입력 − n = 7
출력 − 길이가 7이면서 연속된 1이 없는 이진 문자열의 개수 : 34
접근 방식
문자열 길이 n을 입력으로 받습니다.
count 함수 안에서 크기가 n인 두 개의 배열 arr[]와 arr_2[]를 선언하고, 결과를 저장할 변수 temp를 정의합니다.
두 배열의 0번째 요소를 모두 1로 초기화합니다.
i = 1부터 i < n까지 반복문을 수행합니다.
반복문 안에서 arr[i] = arr[i-1] + arr_2[i-1], arr_2[i] = arr[i-1]을 계산합니다.
temp = arr[n-1] + arr_2[n-1]로 설정한 뒤 temp를 출력합니다.
여기서 arr[i]는 '마지막 비트가 0으로 끝나는 길이 i+1의 유효한 문자열 수', arr_2[i]는 '마지막 비트가 1로 끝나는 문자열 수'를 의미합니다. 마지막이 0이라면 앞 비트는 어떤 값이든 허용되지만, 마지막이 1이라면 바로 앞 비트는 반드시 0이어야 하기 때문입니다. 이 방식은 동적 계획법(DP)에 해당하며 시간 복잡도는 O(n)입니다.
흥미롭게도 이 개수는 피보나치 수열과 같은 패턴을 따릅니다. n = 1일 때 2개, n = 2일 때 3개, n = 3일 때 5개처럼 증가하며, 일반적으로 답은 피보나치 수열의 F(n+2)번째 항과 일치합니다.
예제 코드
#include<stdio.h>
// 연속된 1이 없는 이진 문자열의 개수를 계산하는 함수
void count(int num){
int arr[num];
int arr_2[num];
int i=0, temp=0;
arr[0] = arr_2[0] = 1;
// 각 길이별 개수를 반복문으로 계산
for (i = 1; i < num; i++){
arr[i] = arr[i-1] + arr_2[i-1];
arr_2[i] = arr[i-1];
}
temp = arr[num-1] + arr_2[num-1];
printf("Count of binary strings without consecutive 1's of %d is : %d",num,temp);
printf("\n");
}
int main(){
// count 함수 호출
count(10);
count(7);
count(1);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of binary strings without consecutive 1's of 10 is : 144 Count of binary strings without consecutive 1's of 7 is : 34 Count of binary strings without consecutive 1's of 1 is : 2