C++에서 % 연산자 없이 나머지 구하기: 모듈로 연산자를 사용하지 않는 두 가지 방법

이 문제에서는 두 개의 정수 N과 D가 주어지며, 우리의 목표는 C++에서 모듈로(%) 연산자를 사용하지 않고 나머지를 구하는 프로그램을 작성하는 것입니다.

문제 설명

숫자 N을 D로 나눈 뒤 남는 나머지를 구해야 합니다. 단, 모듈로 또는 % 연산자는 사용할 수 없습니다.

예제로 이해하기

입력

N = 53
D = 3

출력

2

53을 3으로 나누면 몫은 17이고 나머지는 2입니다. 즉, 53 = 3 × 17 + 2라는 관계가 성립합니다.

방법 1: D의 배수를 이용한 방식

가장 직관적인 방법은 N 이하의 수 중에서 D의 배수인 가장 큰 수를 찾은 뒤, 그 값을 N에서 빼는 것입니다. N에서 D의 배수를 제거하고 남은 값이 곧 나머지가 됩니다.

구현 예제

#include <iostream>
using namespace std;
int findRem(int N, int D) {
    int i;
    for(i = 0; ; i++) {
        if(D * i >= N)
            break;
    }
    return N - (D * (i - 1));
}
int main(){
    int N = 45, D = 6;
    cout<<N<<"을 "<<D<<"(으)로 나눈 나머지는 "<<findRem(N, D);
    return 0;
}

출력

45을 6(으)로 나눈 나머지는 3

이 방법은 반복문을 사용하므로 시간 복잡도가 O(N/D)입니다. N이 매우 큰 경우에는 비효율적일 수 있다는 점을 유의해야 합니다.

방법 2: 정수 나눗셈의 몫을 이용한 방식

더 효율적인 방법은 나눗셈의 몫을 활용하는 것입니다. C++에서 나눗셈 결과를 int형 변수에 저장하면 소수점 이하가 자동으로 버려지므로, 별도의 처리 없이 정수 몫을 얻을 수 있습니다. 이 몫에 D를 곱한 값을 N에서 빼면 나머지가 됩니다.

구현 예제

#include <iostream>
using namespace std;
int findRem(int N, int D) {
    int Q = N / D;
    int R = N - (D * Q);
    return R;
}
int main(){
    int N = 45, D = 6;
    cout<<N<<"을 "<<D<<"(으)로 나눈 나머지는 "<<findRem(N, D);
    return 0;
}

출력

45을 6(으)로 나눈 나머지는 3

두 방법 비교

방법 1은 반복문을 통해 D의 배수를 하나씩 찾아가기 때문에 O(N/D)의 시간이 걸립니다. 반면 방법 2는 단 한 번의 나눗셈과 곱셈만으로 O(1) 시간 안에 결과를 얻을 수 있습니다. 따라서 실제 개발에서는 정수 나눗셈의 특성을 활용하는 방법 2가 훨씬 효율적이며 권장되는 접근 방식입니다.