C/C++에서의 몫 연산자 사용 팁

  몫 연산자(/)는 알다시피 컴퓨터공학에서 주로 정수끼리의 나눗셈을 나타낼 때 사용된다. 이름대로 나눗셈의 값을 그대로 반환하는 것이 아닌, '몫'을 반환하는 연산자다. 즉 수학에서 쓰는 '/'와 차이점이 있다(단, 파이썬의 '/'는 수학에서의 쓰임과 동일하다. 대신 파이썬에는 '//'이라는 몫 연산자가 따로 존재한다). 가우스 기호([ ])를 사용해서 말하자면, 정보과학에서 p/q는 수학에서의 $\left[\frac{p}{q}\right]$와 같다고 할 수 있다. 이 글에서는, 몫 연산자의 이러한 점을 이용한 팁을 알아볼 것이다.

 

 ※ 편의상 이후에 등장하는 미지수들은 모두 양수일 경우만 고려한다.

 

floor, ceil, round

  정수와 관련해서, 유명한(?) 함수들이 있다. 바로 floor(x), ceil(x), round(x)이다. 정의는 다음과 같다.

 

• floor(x) = $x$보다 크지 않은 최대의 정수(내림). 기호로는 $\lfloor x \rfloor$이라 쓴다. 가우스함수와 동일하다.
• ceil(x) = $x$보다 작지 않은 최소의 정수(올림). 기호로는 $\lceil x \rceil$이라 쓴다.
• round(x) = $x$와 가장 가까운 정수(반올림). 소수 부분이 $0.5$이상일 경우 올림, 그 미만이면 내림이다.

이때 ${\rm round}(x) = {\rm floor}(x + 0.5)$라는 식이 성립한다. (이는 조금만 생각해 보면 자명하다.) 이 함수들은 C/C++에서도 정의되어 있어 사용할 수 있다. 단 <math.h>(C++에서는 <cmath>) 헤더파일을 추가하여야 한다.
  하지만, 정수 $a$, $b$에 대해 $x$가 $\dfrac{b}{a}$ 꼴(즉 유리수)로 주어진다면, 함수를 가져오지 않고도 다음과 같이 몫 연산자를 이용하여 간단히 해결할 수 있다. (왼쪽의 '/'은 수학 기호이고, 오른쪽의 '/'는 컴퓨터공학의 몫 연산자다.)

 

floor(b/a)   →   b / a
ceil(b/a)   →   (b + a - 1) / a
round(b/a)   →   (b + a / 2) / a

 

  각 식이 맞는 이유는 $b = aq + r$꼴(단 $q$, $r$은 정수, $0 ≤ r < a$)로 나타냄으로써 알 수 있다. 첫 번째는 그냥 몫 연산자의 정의에 의해 자명하고, 두 번째는 $b = aq + r$에서 $r = 0$이면 ${\rm ceil}(b/a) = q$, $r ≠ 0$이면 ${\rm ceil}(b/a) = q+1$이 되므로, 분자에 $a-1$을 더해주고 내림연산(즉 몫 연산)을 적용하면 알맞은 결과가 나오게 된다. 마지막으로 반올림의 경우, 1/2을 더하고 내림하는 것과 같다는 사실을 응용한다.

 

• $a$가 $2k$꼴의 짝수일 경우, $\frac{k-1}{2k}$까지는 0으로 취급하고 $\frac{k}{2k}$부터는 1로 취급해야 하는데, 이는 $k$를 더해주고 내림하는 것과 같다.
• $a$가 $2k+1$꼴의 홀수일 경우, $\frac{k}{2k+1}$까지는 0, $\frac{k+1}{2k+1}$부터는 1로 취급해야 하므로 이 또한 $k$를 더해주고 내림하면 된다.

이때 $a$가 홀수든 짝수든 $k = a/2$이므로(/가 몫 연산자라는 걸 다시 한 번 상기하자) 결국 분자에 $a/2$를 더해주면 같게 되는 것이다.

 

  이렇게 하면 장점이 뭐가 있을까 싶지만, 일단 헤더파일 추가가 필요하지 않으므로 메모리 사용량도 줄어들고, 코드 길이도 줄어든다. 그리고 C/C++에서 저 함수들의 반환값은 double 형이기 때문에 이 값을 정수로 사용하려면 int로 캐스팅해 주어야 하는데(사실 안 그래도 되긴 하지만, 정확도 등에서 문제가 생길 수 있다), 몫 연산자를 이용하면 그럴 필요가 없다. 물론 코드 길이가 줄어드는 건 장점이라고 보긴 힘들지만, 숏코딩을 즐겨 한다면 유용하게 사용할 수 있을 것이다.

 

ax ≤ b

  뜬금없이 부등식을 갑자기 왜 적어 놓은 건지 궁금할 것이다. 사실 부등식은 프로그래밍을 할 때 많이 쓰인다. 대표적으로 반복문이나 조건문에서 조건을 나타낼 때 자주 사용된다. 이렇게 친숙한 표현이지만, $ax ≤ b$ 꼴의 부등식을 무턱대고 사용하다가는 큰코다칠 수도 있다. 다음의 코드를 보자.

#include <stdio.h>
#define NMAX 1000003

int chk[NMAX];

int main()
{
    int N, i, j, ans = 0;
    scanf("%d", &N);

    for (i = 2; i <= N; ++i) {
        if (chk[i]) continue;
        ans++;
        for (j = i; j*i <= N; ++j) chk[i*j] = 1;
    }

    printf("%d", ans);
    return 0;
}

위는 에라토스테네스의 체를 이용해 N까지의 소수의 개수를 구하는 전형적인 코드이다. 입력되는 N의 범위는 대충 100만이라고 하자. 위 코드에서 잘못된 부분을 찾을 수 있겠는가?

 

  아마 평소에 '이것'을 주의하고 있지 않았다면 찾기 상당히 어려울 것이다. 문제가 되는 부분은 바로, 안쪽 for문의 j*i <= N 이 부분이다. j*i를 계산할 때, i가 너무 크면 오버플로우(Overflow)가 발생하여 N과의 대소 비교가 제대로 되지 않는다. 이렇게 부등호 한 쪽에 곱셈식이 있을 경우, 오버플로우를 항상 염두에 두고 있어야 한다. 이를 해결하는 방법으로는 i 혹은 j를 long long 형으로 선언하거나, i*1LL*j <= N처럼 형변환을 해 주는 방법이 있고, 지금부터 소개할 몫 연산자를 이용하는 방법​이 있다.

 

  곱셈과 나눗셈은 역연산 관계다. 그렇기에 수학에서는 $ax ≤ b$를 $x ≤ \dfrac{b}{a}$로 바꿀 수가 있고, 우리는 그것을 잘 알고 있다. 그렇다면 몫 연산자도 이것이 성립할까? 결론부터 말하자면, 그렇다.​ 그리고 이 사실을 이용해 위 상황을 해결할 수 있다. 이를 증명하는 것은 굉장히 간단하다. 위와 똑같이 $b = aq + r$꼴로 생각하자. $ax \le b$이려면 $x \le q$여야 한다. 그리고 $q = b/a$이므로, 결국 $ax \le b$는 $x \le b/a$와 같다. 따라서 j*i <= N 이 부분을  j <= N/i 로 고칠 수 있고, 그러면 오버플로우를 피할 수 있다!

 

  내친김에 다른 부등호($<$, $>$, $\ge$)들도 살펴보자.

 

• 먼저 $ax < b$의 경우. $b = aq + r$이라 하면, $ax < b$는 $r = 0$일 때 $x < q$, $r ≠ 0$일 때 $x \le q$(즉 $x < q+1$)가 된다. 이는 바꿔 말하면 $x < {\rm ceil}(b/a)$이라 할 수 있고, 위의 논의에 의해 결국 $x < (b + a - 1) / a$와 같다.
• 그 다음 $ax > b$의 경우. 마찬가지로 $b = aq + r$이라 하면, $ax > b$이려면 $x > q$이면 된다. 즉 $x > b / a$와 같다.
• 마지막으로 $ax \ge b$의 경우. $b = aq + r$이라 하면, $ax \ge b$는 $r = 0$일 때 $x \ge q$, $r ≠ 0$일 때 $x > q$(즉 $x \ge q+1$)가 된다. 이는 $x \ge {\rm ceil}(b/a)$이라 할 수 있고, 위의 논의에 의해 결국 $x \ge (b + a - 1) / a$와 같다.

위의 내용을 정리하면 다음과 같다.

 

$\texttt{a*x <= b  }\longrightarrow\texttt{  x <= b/a}$
$\texttt{a*x < b  }\longrightarrow\texttt{  x < (b+a-1)/a}$ 
$\texttt{a*x > b  }\longrightarrow\texttt{  x > b/a}$

$\texttt{a*x >= b  }\longrightarrow\texttt{  x >= (b+a-1)/a}$

 

  물론 위에서도 이야기했듯이 long long 형변환을 이용해도 전혀 상관없고, 범위를 봤더니 오버플로우가 일어나지 않는 범위라면 신경을 아예 안 써도 무방하다. 이 글은 그저 몫 연산자를 이용해서 이렇게도 할 수 있다는 걸 보여주는 글일 뿐이다. 코딩 스타일은 자신이 정하는 것이니, 자신과 가장 맞는 걸 골라 사용하면 된다.