하나의 숫자 num이 주어졌을 때, 0과 1만으로 구성되며 길이가 num인 이진 문자열의 개수를 계산하는 것이 이번 문제의 목표입니다.
2진법과 이진 문자열이란?
2진법(Binary Number System)은 숫자 표현 방식 중 하나로, 디지털 시스템에서 가장 널리 사용되는 체계입니다. 2진법은 오직 두 가지 동작 상태 또는 가능한 조건만 가지는 장치로 표현할 수 있는 값을 나타내는 데 사용됩니다. 대표적인 예로 스위치를 들 수 있는데, 스위치는 '켜짐'과 '꺼짐'이라는 두 가지 상태만 가질 수 있습니다.
2진법에는 0과 1이라는 단 두 개의 기호(숫자 값)만 존재합니다. 그리고 이진 문자열(binary string)이란 0 또는 1로만 구성된 문자열을 의미합니다.
예시
입력 − num = 3 출력 − 개수는 8
설명 − 길이 3으로 만들 수 있는 이진 조합은 000, 111, 001, 101, 100, 110, 011, 010으로 총 8가지이므로 개수는 8입니다.
입력 − num = 2 출력 − 개수는 4
설명 − 길이 2로 만들 수 있는 이진 조합은 00, 11, 01, 10으로 총 4가지이므로 개수는 4입니다.
핵심 아이디어
길이가 N인 이진 문자열의 각 자리에는 0 또는 1, 즉 두 가지 선택지가 있습니다. 따라서 만들 수 있는 이진 문자열의 총 개수는 2N입니다.
문제는 N이 매우 커질 수 있다는 점입니다. 2N은 기하급수적으로 증가하기 때문에 일반적인 정수 자료형으로는 표현할 수 없습니다. 이를 해결하기 위해 결과를 큰 소수인 (109 + 7)로 나눈 나머지를 구하는 모듈러 거듭제곱(modular exponentiation) 기법을 사용합니다.
알고리즘 접근 방식
- 자릿수가 매우 클 수 있으므로 long long 타입으로 숫자를 입력받습니다.
- 모듈러 상수 mod를 (long long)(1e9 + 7)로 정의합니다.
- (xy) % p를 O(log y) 시간에 계산하는 반복 함수 power()를 작성합니다.
- result를 1로 초기화하고, x가 p보다 크거나 같으면 x = x % p로 줄입니다.
- y > 0인 동안 반복문을 실행합니다.
- y가 홀수(y & 1)이면 result를 (result * x) % mod로 갱신합니다.
- y = y >> 1로 지수를 절반으로 줄입니다.
- x = (x * x) % mod로 밑을 제곱합니다.
- countbstring() 함수에서 power(2, num, mod)를 호출해 개수를 반환합니다.
- main()에서 결과를 출력합니다.
C++ 구현 예제
#include <iostream>
using namespace std;
#define ll long long
#define mod (ll)(1e9 + 7)
// (x^y)%p를 O(log y) 시간에 구하는 반복 함수
ll power(ll x, ll y, ll p){
ll result = 1;
x = x % p; // x가 p보다 크거나 같으면 갱신
while (y > 0){
// y가 홀수면 result에 x를 곱함
if (y & 1){
result = (result * x) % p;
}
// 이제 y는 짝수
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return result;
}
// 이진 문자열의 개수를 세는 함수
ll countbstring(ll num){
int count = power(2, num, mod);
return count;
}
int main(){
ll num = 3;
cout << "count is: " << countbstring(num);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
count is: 8
복잡도 분석
- 시간 복잡도: O(log N) — 빠른 거듭제곱 알고리즘이 지수를 반복적으로 절반씩 줄여가기 때문입니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 상수 개수의 변수만 사용합니다.