DFA 기반 나눗셈 알고리즘 – 결정적 유한 오토마타로 나머지 구하기

DFA 기반 나눗셈이란?

결정적 유한 오토마타(DFA, Deterministic Finite Automaton)는 어떤 수가 다른 수 k로 나누어 떨어지는지 판별하는 데 활용할 수 있습니다. 나누어 떨어지지 않는 경우에는 나머지 값까지 함께 구해 줍니다.

DFA 기반 나눗셈을 수행하려면 먼저 DFA의 전이 테이블(transition table)을 작성해야 합니다. 이 테이블만 있으면 실제 나눗셈 연산 없이도 답을 쉽게 얻을 수 있습니다. DFA에서 각 상태는 입력 비트에 따라 0 또는 1, 단 두 가지 전이만 가진다는 점이 핵심입니다.

동작 원리

2진수를 최상위 비트부터 한 비트씩 읽어 내려간다고 생각해 봅시다. 지금까지 읽은 부분의 나머지가 r일 때 새로운 비트 b를 하나 더 읽으면, 새로운 나머지는 다음 식으로 계산됩니다.

(2 × r + b) mod k

전이 테이블은 바로 이 규칙을 미리 계산해 둔 표입니다.

비트가 0일 때 → 다음 상태 = (현재 상태 × 2) mod n
비트가 1일 때 → 다음 상태 = (현재 상태 × 2 + 1) mod n

모든 비트를 처리한 뒤 최종 상태가 0이면 나누어 떨어지는 것이고, 그렇지 않다면 최종 상태 값이 곧 나머지입니다.

입력 및 출력

입력:
숫자: 50, 제수: 3
출력:
50은 3으로 나누어 떨어지지 않으며, 나머지는 2입니다.

알고리즘

dfaDivision(num, k)

입력: 숫자 num, 제수 k

출력: 나누어 떨어지는지 여부와 나머지

시작
    크기가 k × 2인 전이 테이블 생성  // 0과 1 전이를 위해 열이 2개 필요
    state ← 0
    checkState(num, state, table)
    state 반환
끝

checkState(num, state, table)

입력: 숫자 num, 상태(state), 전이 테이블(table)

출력: 나눗셈 과정을 진행한 뒤 갱신된 상태

시작
    만약 num ≠ 0이라면
        tempNum ← num을 오른쪽으로 1비트 시프트
        checkState(tempNum, state, table)
        index ← num AND 1  // num과 1의 논리곱(AND) 연산
        state ← table[state][index]
끝

C++ 구현 예제

#include <iostream>
using namespace std;

// 전이 테이블을 생성하는 함수
void makeTransTable(int n, int transTable[][2]) {
    int zeroTrans, oneTrans;

    for (int state=0; state<n; ++state) {
        zeroTrans = state<<1;   // 비트 0일 때의 다음 상태
        transTable[state][0] = (zeroTrans < n)? zeroTrans: zeroTrans-n;

        oneTrans = (state<<1) + 1;   // 비트 1일 때의 다음 상태
        transTable[state][1] = (oneTrans < n)? oneTrans: oneTrans-n;
    }
}

// 재귀적으로 비트를 처리하며 상태를 갱신하는 함수
void checkState(int num, int &state, int Table[][2]) {
    if (num != 0) {   // 숫자를 오른쪽 시프트하며 0이 될 때까지 반복
        checkState(num>>1, state, Table);
        state = Table[state][num&1];
    }
}

// 나누어 떨어지는지 판별하는 함수
int isDivisible (int num, int k) {
    int table[k][2];   // 전이 테이블 생성
    makeTransTable(k, table);   // 테이블 채우기
    int state = 0;   // 처음에는 0번 상태에서 시작
    checkState(num, state, table);
    return state;   // 최종 상태가 0이면 나누어 떨어짐
}

int main() {
    int num;
    int k;
    cout << "Enter Number, and Divisor: "; cin >> num>> k;
    int rem = isDivisible (num, k);
    if (rem == 0)
        cout<<num<<" is divisible by "<<k;
    else
        cout<<num<<" is not divisible by "<<k<<" and remainder is: " << rem;
}

실행 결과

Enter Number, and Divisor: 50 3
50 is not divisible by 3 and remainder is: 2

숫자 50을 제수 3으로 나누면 몫은 16, 나머지는 2가 됩니다. 프로그램 역시 동일하게 "50은 3으로 나누어 떨어지지 않으며 나머지는 2"라는 결과를 출력합니다.

시간 복잡도

전이 테이블 작성에 O(k), 숫자의 모든 비트를 처리하는 데 O(log n)이 걸리므로 전체 시간 복잡도는 O(k + log n)입니다. 일반적인 나눗셈 연산을 대체하기보다는, 자릿수가 매우 큰 2진수를 한 비트씩 스트리밍하면서 나머지를 추적해야 하는 상황에서 특히 유용한 기법입니다.