이 튜토리얼에서는 주어진 이진수가 비트를 제거했을 때 64로 나누어떨어지는지 확인하는 프로그램을 작성해 보겠습니다.
하나의 이진수가 주어지며, 필요에 따라 일부 비트를 자유롭게 삭제할 수 있습니다. 비트를 제거한 결과가 64로 나누어떨어지면 Yes, 그렇지 않으면 No를 출력하면 됩니다.
문제 해결 접근 방식
핵심 원리는 매우 간단합니다. 64는 2의 6제곱(26)이므로, 어떤 수가 64의 배수라면 이진 표현의 맨 뒤에 반드시 0이 여섯 개 이상 연속으로 위치해야 합니다. 따라서 문자열을 오른쪽에서 왼쪽으로 탐색하면서 0의 개수를 세고, 그 왼쪽에 1비트가 존재하는지만 확인하면 됩니다.
이진수를 문자열 형태로 초기화합니다.
이진수를 오른쪽에서 왼쪽으로 순회하면서 0의 개수를 셉니다.
0이 6개 이상 누적된 상태에서 1비트를 발견하면, 해당 1과 0 여섯 개만 남기고 나머지 비트를 모두 제거했을 때 그 수는 64의 배수가 됩니다.
조건을 만족하면 Yes, 그렇지 않으면 No를 출력합니다.
예제 코드
전체 소스 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
bool isBinaryStringDivisibleBy64(string binary_number, int n) {
int zeroes_count = 0;
for (int i = n - 1; i >= 0; i--) {
if (binary_number[i] == '0') {
zeroes_count++;
}
if (zeroes_count >= 6 && binary_number[i] == '1') {
return true;
}
}
return false;
}
int main() {
string binary_string = "100100100100100";
if (isBinaryStringDivisibleBy64(binary_string, binary_string.length())) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Yes
동작 과정 살펴보기
예제 입력인 "100100100100100"을 기준으로 알고리즘이 어떻게 동작하는지 단계별로 살펴보겠습니다.
맨 오른쪽부터 탐색을 시작하면 처음 두 문자가 '0'이므로 0의 개수는 2가 됩니다.
세 번째 문자가 '1'이지만, 아직 0이 6개 미만이므로 조건을 만족하지 않습니다.
탐색을 계속하면 0이 두 개 더 누적되어 총 4개가 되고, 다시 '1'을 만나지만 여전히 조건을 충족하지 못합니다.
이후 0이 두 개 더 누적되어 총 6개가 된 상태에서 바로 왼쪽의 '1'을 만나는 순간 조건이 성립하여 true를 반환합니다.
즉, 이 이진수에서 1 하나와 0 여섯 개만 남기고 나머지 비트를 모두 제거하면 64의 배수를 만들 수 있습니다.
마무리
이처럼 64가 2의 6제곱이라는 성질만 활용하면 복잡한 나눗셈 연산 없이도 64의 배수 여부를 선형 시간 O(n) 안에 판별할 수 있습니다. 튜토리얼 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.