C++에서 DFA 기반 나눗셈 구현하기

결정적 유한 오토마타(DFA, Deterministic Finite Automaton)는 어떤 수가 다른 수 k로 나누어 떨어지는지 확인하는 데 활용할 수 있습니다. 이 알고리즘은 나누어 떨어지지 않는 경우 나머지까지 함께 구해주기 때문에 실용성이 높습니다.

DFA 기반 나눗셈에서는 k개의 상태를 가진 DFA 테이블을 만듭니다. 수를 이진수로 표현하기 때문에 DFA의 각 상태에서 입력은 0과 1뿐입니다.

전이 테이블 생성하기

createTransTable(int k, int transTable[][2]) 함수는 전이 테이블(transTable)을 만들고 상태 정보를 저장하는 역할을 합니다. 이 함수는 제수 k와 2개의 열을 가진 배열 transTable[][2]를 매개변수로 받습니다. 또한 비트 0 입력 시 다음 상태를 저장하는 trans_0과 비트 1 입력 시 다음 상태를 저장하는 trans_1 두 변수를 선언합니다.

void createTransTable(int k, int transTable[][2]){
   int trans_0, trans_1;

함수 내부의 for 루프는 state가 k보다 작을 때까지 반복됩니다. trans_0이 k보다 작으면 transTable[state][0]에 trans_0 값을 대입하고, 그렇지 않으면 trans_0에서 k를 뺀 값을 대입합니다. trans_1도 동일한 방식으로 처리합니다.

for (int state = 0; state < k; state++){
   trans_0 = state << 1;
   transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
   trans_1 = (state << 1) + 1;
   transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
}

나누어 떨어짐 검사하기

checkDivisible(int num, int &state, int transTable[][2]) 함수는 검사할 수 num, 참조로 전달되는 state 변수, 전이 테이블 배열을 받습니다. num이 0이 아니면 비트 우측 시프트(>> 1)를 적용하며 자기 자신을 재귀 호출해 수가 0이 될 때까지 처리합니다. 우측 시프트는 사실상 수를 2로 나누는 것과 같으므로, 결국 num이 0이 될 때까지 이진수 자릿수를 하나씩 처리하게 됩니다. 이후 transTable[state][num&1] 값이 state 변수에 대입됩니다.

void checkDivisible(int num, int &state, int transTable[][2]){
   if (num != 0){
      checkDivisible(num >> 1, state, transTable);
      state = transTable[state][num&1];
   }
}

전체 흐름 구성하기

isDivisible(int num, int k) 함수는 피제수 num과 제수 k를 받아 최종 결과를 반환합니다. 먼저 2열 k행 크기의 전이 테이블 transTable[k][2]를 선언한 뒤, createTransTable(k, transTable)과 checkDivisible(num, state, transTable)을 차례로 호출하여 state 변수를 갱신합니다. 마지막으로 state 변수를 반환하는데, 이 값이 곧 나눗셈의 나머지를 의미합니다.

int isDivisible (int num, int k){
   int transTable[k][2];
   createTransTable(k, transTable);
   int state = 0;
   checkDivisible(num, state, transTable);
   return state;
}

예제 코드

다음은 DFA 기반 나눗셈의 전체 구현 예제입니다.

#include <bits/stdc++.h>
using namespace std;
void createTransTable(int k, int transTable[][2]){
   int trans_0, trans_1;
   for (int state = 0; state < k; state++){
      trans_0 = state << 1;
      transTable[state][0] = (trans_0 < k) ? trans_0 : trans_0 - k;
      trans_1 = (state << 1) + 1;
      transTable[state][1] = (trans_1 < k) ? trans_1 : trans_1 - k;
   }
}
void checkDivisible(int num, int &state, int transTable[][2]){
   if (num != 0){
      checkDivisible(num >> 1, state, transTable);
      state = transTable[state][num&1];
   }
}
int isDivisible (int num, int k){
   int transTable[k][2];
   createTransTable(k, transTable);
   int state = 0;
   checkDivisible(num, state, transTable);
   return state;
}
int main(){
   int num = 67;
   int k = 5;
   int remainder = isDivisible (num, k);
   if (remainder == 0)
      cout <<num<< " is divisible by "<<k;
   else
      cout <<num<< " is not divisible by "<<k<<" and lefts remainder "<<remainder;
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 나옵니다.

67 is not divisible by 5 and lefts remainder 2

67을 5로 나누면 나머지가 2이므로, DFA의 최종 상태(state)가 2가 되어 나누어 떨어지지 않음과 나머지 값을 정확히 알려줍니다. 이처럼 DFA 기반 접근법은 비트 연산만으로 나눗셈 판정과 나머지 계산을 효율적으로 수행할 수 있습니다.