이번 문제는 하나의 숫자가 이진수 형태로 주어졌을 때, 그 숫자에서 1을 뺀 값, 즉 바로 앞에 있는 숫자의 이진 표현을 구하는 것입니다.
숫자의 이진 표현(binary representation)이란 해당 숫자를 2진법으로 변환하여 0과 1만으로 나타내는 것을 의미합니다.
예를 들어, 23의 이진 표현은 10111입니다.
즉, 이진수 형태의 숫자 n이 주어지면 n-1에 해당하는 이진 표현을 찾아야 하는 것이죠.
이진수 뺄셈의 기본 원리
이 문제를 해결하려면 먼저 이진수 뺄셈의 기본 개념을 이해해야 합니다. 이진수에서 1을 뺄 때 어떤 일이 일어나는지 살펴보겠습니다.
- 0 − 1 = 1 (다음 자릿수에서 1을 빌려오는, 즉 캐리가 발생)
- 1 − 1 = 0
예시로 이해하기
입력 : 101101100
출력 : 101101011
설명 : (101101100)₂는 십진수 364의 이진 표현입니다.
그 앞에 있는 숫자는 363이며, 그 이진 표현은 (101101011)₂입니다.
여기서는 이진수 뺄셈을 활용하여 주어진 수의 이진 표현에서 (1)₂를 빼 결과를 얻었습니다.
문제 해결 로직
이제 프로그램의 핵심 로직을 살펴보고, 이를 바탕으로 알고리즘을 설계해 보겠습니다.
주어진 숫자의 이진 표현에서 1을 빼야 하므로, 다음과 같은 접근 방식을 사용할 수 있습니다.
- 숫자의 가장 오른쪽 비트부터 왼쪽으로 이동하며 탐색을 시작합니다.
- 0을 만나면 모두 1로 뒤집습니다.
- 처음으로 1을 만나는 순간, 그 1을 0으로 바꾸고 탐색을 종료합니다.
- 변경된 최종 결과를 반환합니다.
알고리즘
Step 1 : 오른쪽에서 왼쪽으로 탐색을 시작한다 (인덱스 n-1부터 0까지).
Step 2 : 1을 만나면 0으로 변경하고 반복을 종료한다.
Step 3 : 0을 만나면 1로 변경한다.
Step 4 : 배열(문자열)을 출력한다.
C++ 코드 구현
위 알고리즘을 실제 프로그램으로 구현한 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
string previousNumber(string num) {
int n = num.size();
if (num.compare("1") == 0)
return "0";
int i;
for (i = n - 1; i >= 0; i--) {
if (num.at(i) == '1') {
num.at(i) = '0';
break;
} else
num.at(i) = '1';
}
if (i == 0)
return num.substr(1, n - 1);
return num;
}
int main() {
string number = "1011011000";
cout<<"주어진 숫자의 이진 표현은 "<<number<<endl;
cout<<"이전 숫자의 이진 표현은 "<<previousNumber(number);
return 0;
}
실행 결과
주어진 숫자의 이진 표현은 1011011000
이전 숫자의 이진 표현은 1011010111
정리
이 알고리즘은 문자열을 한 번만 순회하면 되기 때문에 시간 복잡도는 O(n)이며, 여기서 n은 이진 문자열의 길이입니다. 추가적인 메모리 사용 없이 기존 문자열을 직접 수정(in-place)하기 때문에 공간 복잡도도 O(1)로 매우 효율적입니다. 특히 입력이 "1"인 경우에는 결과가 "0"이 되므로 이러한 경계 조건(edge case) 처리도 반드시 포함해야 정확한 동작을 보장할 수 있습니다.