C++에서 곱셈·나눗셈 연산자 없이 두 정수 나누는 방법

문제 개요

두 정수 dividend(피제수)와 divisor(제수)가 주어졌을 때, 곱셈(*), 나눗셈(/), 나머지(%) 연산자를 사용하지 않고 두 수를 나누어 몫을 반환하는 것이 목표입니다. 이때 정수 나눗셈은 0을 향해 잘라내야(truncate toward zero) 하며, 입력값은 모두 32비트 정수입니다.

예를 들어 dividend = 7, divisor = -3이 입력으로 주어지면 출력은 -2가 됩니다.

알고리즘 접근 방법

핵심 아이디어는 비트 시프트 연산을 활용해 제수를 계속 배가시키면서 피제수에서 차감하는 것입니다. 시프트 연산은 곱셈이나 나눗셈 없이도 2의 거듭제곱 배를 빠르게 계산할 수 있게 해주므로, 단순히 제수를 한 번씩 빼는 방식보다 훨씬 효율적입니다.

1. 피제수 x와 제수 y를 인자로 받습니다.
2. 오버플로 처리: 피제수가 INT_MIN이고 제수가 -1이면 결과가 int 표현 범위를 초과하므로 INT_MAX를 반환합니다.
3. a := |x|, b := |y|로 절댓값을 준비하고 ans := 0으로 초기화합니다.
4. a − b ≥ 0인 동안 다음 과정을 반복합니다.
   • p := 0으로 초기화합니다.
   • a − (b를 왼쪽으로 시프트한 값) ≥ 0인 동안 p를 1씩 증가시켜, b를 최대한 크게 확장합니다.
   • a에서 b를 왼쪽으로 p번 시프트한 값을 빼고, ans에는 1을 왼쪽으로 p번 시프트한 값(2^p)을 더합니다.
5. x와 y의 부호가 서로 같으면 ans를, 다르면 −ans를 반환합니다.

이 방식의 시간 복잡도는 O(log²n) 수준으로, 매 반복마다 제수를 지수적으로 확장하기 때문에 입력값이 커져도 빠르게 수렴합니다.

C++ 구현 예시

다음 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int divide(int l, int y) {
        if(l <= INT_MIN && y == -1)return INT_MAX;
        lli a = labs(l);
        lli b = labs(y);
        lli ans = 0;
        while(a-b >= 0){
            int x = 0;
            while(a-(b << 1 << x) >= 0){
                x++;
            }
            a -= b<<x;
            ans += 1<<x;
        }
        return (l>0)== (y>0)?ans:-ans;
    }
};
main(){
    Solution ob;
    cout << ob.divide(40, 3);
}

입력

40
3

출력

13

결과 해석

40을 3으로 나누면 몫은 13입니다. 위 코드는 제수 3을 시프트 연산으로 24(3×2³), 12(3×2²), 3(3×2⁰) 순으로 확장해 가며 피제수 40에서 차감하고, 각 단계에서 대응되는 몫 8, 4, 1을 누적하여 최종 답 13을 얻습니다. 또한 오버플로 가능성을 사전에 검사하고, long long 타입으로 절댓값을 다루어 안정성을 확보했습니다.