정수론

본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

나머지

 이 토픽에서는 정수의 나눗셈에서 발생되는 나머지에 대해 다루려고 합니다.  나머지에 대한 정의는 아래와 같습니다. 

 나머지(영어: remainder)는 산술에서 두 정수의 나눗셈 이후, 온전한 정수 으로 표현할 수 없이 남은 양을 가리킨다. 잉여(剩餘)라고도 한다.

 선형 등식의 일반적인 형태는 a = q × d + r로 표현할 수 있다. 이 등식에서 q는 몫이고 r은 나머지이다. 이 등식은 나머지를 구하기 위해 r = a - q × d로도 표현할 수 있다. 그러나 a와 d는 자연수여야 하며 d는 0이 되어서는 안 된다. 몫은 a를 d로 나눈 정수의 결과물이다. 또, 나머지는 정수여야만 한다. (위키피디아 발췌)

 

 위의 정의와 같이 나머지는 정수의 나누기에서만 발생하는 값으로서, 어떤 값을 몫으로 최대한 나눈 후 더이상 나눌 수 없게 남은 값을 의미합니다. 대부분의 언어에서는 나머지를 한 번에 계산할 수 있도록 연산자를 제공하고 있으며, C/C++에서 나머지 연산자는 아래와 같습니다.

int a, b; //두 정수
int mod = a % b ; // a % b == a를 b로 나눈 나머지

 

 나머지 연산은 보통 나누기와 마찬가지로 더하기/빼기/곱하기 연산에 비해서 상대적으로 무거운 연산에 속합니다. 너무 많은 나머지 연산은 어느정도 실행시간에 영향을 줄 수 있음을 유의하여야 합니다. 

 나머지 연산을 많이 해야 할 경우 아래와 같은 방법으로 처리할 것을 권유합니다.

int get_mod(int a, int b)
{   //a를 b로 나눈 나머지 계산
    if(a > b)
        return a % b;
    else
        return a;
}

 위와 같이 a > b 인 경우에 대해서만 mod연산을 수행하는 경우, 확률적으로 a <= b 인 경우가 많을 수록 시간을 많이 단축할 수 있습니다. 하지만 나머지 연산이 수행되는 횟수 자체가 많지않은 경우에는 그냥 바로 계산하는 것이 더 좋습니다.

댓글

댓글 본문
작성자
비밀번호
버전 관리
코딩몬스터
현재 버전
선택 버전
graphittie 자세히 보기