모듈로 연산이란? (feat. %)

dp문제를 풀던 중 갑자기 궁금한 점이 생겼다. 

dp를 풀 때 값이 너무 커지게 되면 문제에서 결과값으로 1234567을 나눈 나머지를 결과로 내놓으라고 한다. 

 

마지막에만 1234567을 나눠서 나머지를 구하면 된다고 생각했는데 dp를 하는 중간에도 1234567을 나누더라구요..? 그럼 값이 달라지는거 아닌가 싶어서 찾아보는데 모듈로 연산의 특성이라는 것이 있었다. 

for(int i=3;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
        
        //메모리 초과 및 계산 시간 증가 방지
        dp[i]=dp[i]%1234567;
    }

 

모듈로 연산을 간단하게 설명하면, 컴퓨터공학을 조금이라도 공부하면 알 수 있는 % (나머지) --> 이것임.

 

위의 예처럼 dp[i]가 큰 숫자가 생기는 경우가 있는데 컴퓨터는 너무 큰 숫자를 다루는 데 어려움이 있을 수 있다. 그래서 우리가 모듈로 연산을 통해 적당한 크기 안에서 값을 유지하려고 하는 것이다. 

 

근데 이렇게 모듈로 연산으로 나머지만 저장한다면 기존 값은...? 결국 값이 바뀌는거 아니야...? 하는 수가 있다. 

 

하지만 모듈로 연산은 덧셈, 곱셈 같은 연산과 결합해도 결과가 동일하다는 성질을 가지고 있다. 즉, 중간에 나머지를 구해도 최종 결과에 영향을 주지 않는다.

 

(a + b) % m = [(a % m) + (b % m)] % m

이러한 성질에 따라 우리가 중간중간 모듈로 연산을 해도 최종 값이 달라지지 않는다. 

 

 

물론 이게 막상 코딩할 때 중요하진 않겠지만..그냥 의심 없이 풀어도 된다는..그러한 인사이트를 제공했으면 하는 바람^^..ㅎ