이 튜토리얼에서는 하나의 숫자를 최소 개수의 의사 이진수(pseudo-binary number)들의 합으로 표현하는 방법을 다룹니다. 의사 이진수란 0과 1이라는 이진 자릿수만으로 구성된 수를 말하며, 대표적인 예로 00, 11, 10, 100, 111, 1011 등이 있습니다.
먼저 숫자를 의사 이진수의 합으로 나타낸 몇 가지 예시를 살펴보겠습니다.
입력 : 23
출력 : 11 + 11 + 1
설명 : 23 = 11 + 11 + 1, 즉 의사 이진수(11, 11, 1)의 합이 23입니다.
입력 : 50
출력 : 10 + 10 + 10 + 10 + 10
문제 해결 접근 방법
N을 최소 개수의 의사 이진수로 분해하기 위한 가장 효율적인 방법 중 하나는 다음과 같습니다.
N의 각 자릿수에 따라 그 자리를 1 또는 0으로 채운 숫자 X를 만듭니다.
N의 각 자릿수를 하나씩 확인합니다.
해당 자릿수가 0이라면 X의 같은 자리도 0으로 설정합니다.
0이 아니라면 X의 같은 자리를 1로 설정합니다.
예를 들어 N = 32라면 X는 11이 됩니다.
이렇게 만들어진 X는 하나의 의사 이진수입니다.
N에서 X를 뺀 뒤, N이 0이 될 때까지 위 과정을 반복합니다.
이 방법이 작동하는 이유는 각 단계에서 N의 모든 0이 아닌 자릿수를 동시에 1씩 줄일 수 있기 때문입니다. 따라서 필요한 의사 이진수의 개수는 N의 자릿수 중 가장 큰 값과 같아지며, 이것이 이론상 최소 개수입니다.
C++ 구현 예제
위 접근 방식을 구현한 C++ 코드는 다음과 같습니다.
#include<iostream>
using namespace std;
int main(){
int N = 51;
// N이 0이 될 때까지 의사 이진수를 찾습니다.
cout << "pseudo-binary representation of " << N << " is: ";
while (N > 0){
// N의 각 자릿수에 따라 0과 1로 구성된 X를 찾습니다.
int temp = N;
int X = 0, bit = 1;
// temp의 각 자릿수가 0인지 아닌지 확인합니다.
while (temp != 0){
int last_dig = temp % 10;
temp = temp / 10;
if (last_dig != 0)
X += bit;
bit *= 10;
}
// 하나의 의사 이진수를 출력합니다.
cout << X << " ";
// N에서 X를 빼서 값을 갱신합니다.
N = N - X;
}
return 0;
}
실행 결과
pseudo-binary representation of 51 is: 11 10 10 10 10
51은 11 + 10 + 10 + 10 + 10의 합으로 표현되며, 총 5개의 의사 이진수가 사용되었습니다. 이는 51의 십의 자리 숫자가 5이므로 최소 5개가 필요함을 의미합니다.
코드 상세 설명
바깥쪽 while 루프: N이 0보다 클 동안 반복하며, 매번 새로운 의사 이진수 X를 찾아냅니다.
temp 변수와 안쪽 루프: temp에 N의 값을 복사한 뒤, 안쪽 루프에서 temp의 각 자릿수를 검사하여 0이 아닌 자리에는 변수 X의 해당 자리를 1로 설정합니다.
X 출력: 완성된 X는 하나의 의사 이진수이므로 화면에 출력합니다.
N 갱신: N에서 X를 뺀 값으로 N을 업데이트하고, N이 0이 될 때까지 바깥쪽 루프를 다시 실행합니다.
이 알고리즘의 시간 복잡도는 O(d²)입니다. 여기서 d는 N의 자릿수로, 각 반복마다 자릿수를 순회하는 작업이 최대 d번 발생하기 때문입니다.
마무리
이번 튜토리얼에서는 하나의 숫자를 가능한 최소 개수의 의사 이진수 합으로 표현하는 방법을 살펴보았습니다. 각 자릿수를 기반으로 의사 이진수를 찾아내는 직관적인 알고리즘과 이를 구현한 C++ 코드를 함께 다루었으며, 이 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.