챕터4-1. 수학 | 나머지 연산(Modulo)

나머지 연산 개념

# 자주 등장하는 곳
- 다이나믹 문제에서 전체 경우의 수를 구하는 문제일 때, 답을 M으로 나눈 나머지를 출력하라는 문제가 자주 등장한다.
   이 때 최종 계산값에 나머지 연산을 수행한 단순 계산값을 출력하면 된다고 생각하지만 그렇지 않다.
   이런 문제의 의도는 중간 및 최종 계산값이 int형의 저장범위를 넘어서기 때문에 이를 극복하여 문제를 해결하라는 것이다.
- 이런 유형의 문제는 다음의 원리를 이용해 memoization 배열인 d[i]에 M으로 나눈 나머지 값을 저장함으로써 해결할 수 있다.

# 사용가능한 법칙
1. (A + B) % M = ((A % M) + (B % M)) % M

2. (A x B) % M = ((A % M) x (B % M)) % M

3. (A - B) % M = ((A % M) - (B % M) + M) % M      -> 뺄셈 부분에서 음수가 나올 수 있기 때문에 +M을 해줘야함

- 나누기의 경우에는 성립하지 않음(Modular Inverse를 구해야 하는데 이는 중급 강의에서 배움)

- 위의 법칙에서 M을 한번더 % 해주는 이유는 A = 4, B = 4, C = 5일 때를 한번 대입해보면 알 수 있다.

나머지 연산을 적용한 문제풀이

# A, B, M이 주어지고 위의 법칙이 맞는 지 확인하는 문제
- https://www.acmicpc.net/problem/10430

 - 4, 4, 5 입력도 한번 시도해보자

# 위의 법칙을 사용해야하는 다이나믹 문제
- https://ldgeao99.tistory.com/entry/챕터3-3-다이나믹-프로그래밍-문제-풀이2
- 출력해야 하는 값 : 2 x N 직사각형을 채우는 모든 방법의 수를 10007로 나눈 나머지
- d[n] = "2 x N 직사각형을 채우는 모든 방법의 수"
- 점화식 : d[i] = d[i-1] + d[i-2]
- 위 법칙을 사용해야하는 부분 : 
   중간에 d[i] 값이 오버플로우 됨 => 이를 해결하기위해 다음의 법칙을 사용 "(A + B) % M = ((A % M) + (B % M)) % M"
   내가 지금 얻고싶은 값은 d[i]인 d[i-1] + d[i-2] 를 10007로 나눈 값. 즉, (d[i-1] + d[i-2]) % 10007
   그런데 d값들이 중간에 오버플로우가 발생하여 이를 해결하기 위해 모든 d에 원래 결과를 10007로 나눈 나머지를 저장했다. 
   그것이 d'[i]이고, d'[i-1] = d[i-1]%10007, d[i-2] = d[i-2]%10007 이 되는 것이다.

   원래의 (d[i-1] + d[i-2] ) % 10007 을 얻고싶다면 위 법칙에 의해 이와 동일한 (d[i-1]%10007 + d[i-2]%10007) % 10007
   = (d'[i-1] + d'[i-2]) % 10007을 계산하면 되는 것이다.

//Top-down 구현 방식의 재귀호출 부분
d[n] = (getAllCombiCount(n-1) + getAllCombiCount(n-2))% 10007;

//Bottom-up 구현방식의 for문 내부
d[i] = (d[i-1] + d[i-2])% 10007;