나머지의 순환
우리는 0이상의 양의 정수 n의 나머지 a와 몫 b에 대하여 아래와 같은 표현을 사용할 수 있습니다.
n = ax + b (단, 0 <= b < a)
위와 같은 식에서 몫을 a라고 한다면, b는 [0, a-1]의 범위 안에 존재하게 됩니다. 또한 n이 1씩 증가할수록 b는 차례로 1씩 증가하다가 0으로 돌아오고, 다시 증가하고를 반복합니다. 즉, n이 차례로 증가할 때 마다 나머지 b는 [0, a-1]범위를 순환하게 됩니다.
아래의 문제들은 나머지의 순환성을 이용하면 풀 수 있는 문제들입니다. 한 번 풀이를 생각해보시길 바랍니다.
나머지 뿐만 아니라 다양한 수들의 순환성에 대한 토픽은 나중에 따로 작성하도록 하겠습니다.
|
[연습 문제 1] N(1 ≤ N ≤ 2, 000, 000)은 사람의 수를 뜻하며, i번째 사람의 나이는 다음의 공식을 통해 구할 수 있다. Xi+1 = (11Xi+97) mod 100 이 때 모든 사람의 나이를 오름차순으로 정렬하였을 때 P번째 사람의 나이를 계산하시오.
제출 및 채점 : http://judge.lavida.us/problem.php?id=2103 |
|
[연습 문제 2] 임의의 여섯개의 정수 X1, X2, X3, P1, P2, P3,가 있다. 아래의 조건을 만족하는 가장 작은 정수 N을 찾으시오. N을 P1으로 나눈 나머지가 X1 (X1 < P1) N을 P2으로 나눈 나머지가 X2 (X2 < P2) N을 P3으로 나눈 나머지가 X3 (X3 < P3) ( 0 <= Xi <=300 ) ( 1 <= Pi <=300 ) ( 0 <= N <= 1,000,000,000 )
제출 및 채점 : http://judge.lavida.us/problem.php?id=1010 |
나머지의 법칙
나머지 연산은 기본적으로 결합, 분배, 교환법칙이 모두 성립하지 않습니다. 그래서 사용할때에 항상 계산순서와 위치에 주의를 해야합니다. 단 나머지 연산에서 성립하는 독특한 성질들도 있습니다.
a를 b로 나눈 나머지를 a mod b = a % b라고 표현하기로 합시다. 이 때 나머지는 다음과 같은 식들이 항상 성립합니다.
( a + m ) % m = a % m
( (a % m) + ( b % m) ) % m = ( a + b ) % m
( ( a % m) * ( b % m) ) % m = ( a * b) % m
나머지의 역방향 계산법
주로 환형 큐(Circular Queue)와 같이 인덱스가 순환하는 구조에 자주 사용되는 방법입니다. 아래와 같은 원판을 상상 해 봅시다.
현재 우리가 a칸에 서 있다고 가정할 때에 b칸 만큼 앞으로 전진했을 때 서 있을 칸의 위치는 아래와 같이 간단하게 계산할 수 있습니다.
int next_step(int now,int len, int count)
{ //길이가 len인 원형 판에서
// now번 칸에 서 있을 때 count 칸 만큼 전진하면
// 서 있게 되는 칸의 번호 계산하기
return ( now + count ) % len;
}
그렇다면 반대로 b칸 만큼 뒤로 간 경우 서 있게 될 인덱스는 어떻게 계산할 수 있을까요? b가 a보다 작거나 같다면 바로 (a-b)%m번 칸에 서 있다는 것을 알 수 있지만, b가 a보다 큰 경우 (a-b)가 음수가 되어 음수 나머지가 발생하게 됩니다. 위 처럼 환형으로 순환하는 인덱스를 계산하고 싶을때에는 아래와 같이 구현하면 됩니다.
int back_step(int now, int len, int count)
{ //길이가 len인 원형 판에서
//now번 칸에 서 있을 때
//count칸 만큼 후진한 후 서 있는 칸 번호
return ( now - (count % len) + len ) % len;
}
위처럼 계산할 수 있는 이유는 , 어차피 원형판위에 존재하는 칸의 개수 len번째마다 같은 위치에 서있게 되므로 결국 count칸 만큼 뒤로 간 결과는 (count % len)만큼 뒤로 간 결과와 같습니다. 이 때 (count % len)은 len보다 작으므로 여기에 len을 더해주면 최종적으로 len으로 나눈 나머지를 구했을 때 결과는 같지만, len - (count % len)이 항상 양수이므로 양수만으로 계산을 할 수 있게 됩니다.
