[알고리즘]나머지 연산(모듈러 연산)

목표

• 나머지 연산에 대해 알아보자 
• 나머지 연산을 이용한 문제 풀이

나머지 연산의 등장 배경 

• 31 mod 4는 무엇일까? 너무 쉽다. '3'!
• 3^31 mod 12는 무엇일까? 😓 계산기를 두드려서라도 구해보자. 
  3^31는 617673396283947이다. 이 숫자의 mod 12는? 머리의 한계가 온다. 
  컴퓨터의 도움을 받아보자 
  

  

  바로 결과 도출

• 3^200 mod 12는 무엇일까? 😒 장난하나 너무 큰 숫자다. 
  이렇게 큰 나머지 숫자를 어떻게 구 할 수있을까?
  
  

나머지 연산

• 나머지 연산은 3가지 특징을 가진다. 

출처 : https://developer-mac.tistory.com/84

• 나머지 연산의 특징을 활용하여 문제를 해결해 보자.
• 3^200 mod 12 
  = ( 3^200 mod 12  ) * (  3^200 mod 12 ) mod 12
  = ( 3^100  mod 12  ) * ( 3^100  mod 12   ) ^2   mod 12 (1)
  = (( 3^50 mod 12  ) * ( 3^50  mod 12   )^2^2 mod 12  (2)
  = (( 3^25 mod 12  ) * ( 3^25 mod 12   )^2^2^2 mod 12 (3)
  = (( 3^12 * 3 mod 12  ) * ( 3^12 * 3 mod 12   )^2^2^2^2 mod 12 (4)
  = (( 3^6 mod 12  ) * ( 3^6 * 3 mod 12   )^2^2^2^2^2 mod 12 (5)
  = (( 3^3 mod 12  ) * ( 3^3 mod 12   )^2^2^2^2^2^2 mod 12 (6)
  = (( 3^1 * 3 mod 12  ) * ( 3^1 * 3 mod 12   )^2^2^2^2^2^2^2 mod 12 (7)
  
  이제 순서대로 계산을 해봅시다.
  
  = (9 * 9 mod 12 )^2^2^2^2^2^2^2 mod 12 (7)
    81 mod 12는 9
  = (9 * 9 mod 12 )^2^2^2^2^2^2 mod 12 (6)
    81 mod 12는 9
  = (9 * 9 mod 12 )^2^2^2^2^2 mod 12 (5)
    81 mod 12는 9
  = (9 * 9 mod 12 )^2^2^2^2 mod 12 (4)
    81 mod 12는 9
  = (9 * 9 mod 12 )^2^2^2 mod 12 (3)
    81 mod 12는 9
  = (9 * 9 mod 12 )^2^2 mod 12 (2)
    81 mod 12는 9
  = (9 * 9 mod 12 )^2 mod 12 (1)
    81 mod 12는 9
  = 9
  
  나머지는 9이다.

나머지 연산 활용하기

• 나머지 연산과 그의 특징을 활용한다면 큰 숫자의 나머지도 구할 수 있다. 
• 코드로 알아보기 
  

  let m = 12;
  let mode  = ( n, k  ) => {
      if(k == 1) { 
          return n % m; 
      };
      let _n = mode( n, Math.floor (k / 2 ));
      _n = _n * _n % m;
      if( k & 1 ) _n = _n * n % m;
      return _n;
  } 
  
  mode(3, 61740) // 9가 나온다​

• 알고리즘 문제로 풀어보기 
  

  1629번: 곱셈

정리 및 마무리

• 나머지 연산의 특징을 잘 활용한다면 어떤 큰 수의 나머지도 구 할 수 있다.

참조

https://developer-mac.tistory.com/84