모듈러 연산 간단 이해해보기

개요

백준 문제(10844번)를 풀던 중, 자료형 오버플로우로 골치를 썩히다 AI의 힘을 빌려 알게 된 개념을 정리해보려 한다.

개념

"나머지 연산"

어떤 정수를 특정 숫자로 나누었을 때의 나머지를 구하고, 이 나머지를 기준으로 숫자가 순환하는 수학적 체계이다.

표현방법

A를 N으로 나누었을 때의 나머지가 R

A mod N = R

ex) 시계
시계의 숫자는 12를 주기로 숫자가 처음으로 돌아간다.
10시 + 5시간 = 오후 3시 (15 mod 12 = 3)

분배 법칙

덧셈, 뺄셈, 곱셈에 대해 분배 법칙도 성립한다.

• 덧셈: (A+B) mod N = ((A mod N) + (B mod N)) mod N
• 뺄셈: (A-B) mod N = ((A mod N) - (B mod N) + N) mod N
• 곱셈: (A X B) mod N = ((A mod N) X (B mod N)) mod N

문제 내에서의 모듈러 연산

10844번의 출력 부분이다.
처음에 문제를 풀 때에는 2차원 배열에 저장한 값이 int 자료형 범위를 넘어갈 거라는 생각은 아예 안하고 문제를 풀었고, 그냥 마지막에 1,000,000,000로 나눠서 출력하는 아래와 같은 방법을 사용했고,

   System.out.println(
            Arrays.stream(dp[N])
            .sum()
            % MOD
    );

결과는 역시 틀렸다고 나왔다.

그래서 2차원 배열 중간중간 값을 채울 때마다 1,000,000,000(MOD)로 나머지 연산을 진행해주었다.

        // 모듈러 연산 (오버플로우 방지)
        for (int i = 2; i <= N; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 0) {
                    dp[i][j] = (dp[i - 1][j + 1]) % MOD;
                } else if (j == 9) {
                    dp[i][j] = (dp[i - 1][j - 1]) % MOD;
                } else {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
                }
            }
        }

결론

문제를 풀면서 차라리 예외가 발생했다면, '아 이 문제구나' 하고 금방 찾을 수 있겠지만 예외가 발생하지 않으니 문제원인을 깨닫는데 시간이 좀 걸렸다.
자료형 오버플로우에 대한 경각심을 다시금 강하게 가지게 되었다.

---

PS. 2026 4월 28일부로 BOJ 서비스가 종료된다고 한다.
개인적으로 이만큼 문제가 많이 있고, 알고리즘 구분이 잘 된 아카이브는 없었는데.. 알고리즘 문제 풀이를 본격적으로 깊게 파보지는 못했지만, 아무래도 아쉬움이 많이 남는다.