Java와 Python의 모듈러 연산

프로그래머스의 아방가르드 타일링문제를 풀다가 이런게 있었지.. 하며 다시 공부한 것..

위 문제는 결과값이 매우 크기 때문에, 큰 소수(1,000,000,007)로 나눈 나머지를 정답으로 반환하도록 한다.

메모이제이션을 위해 dp테이블을 선언하고, 점화식을 통해 경우의 수를 계산하는데, dp테이블에 경우의 수를 갱신할 때는 주어진 큰 소수로 나눈 나머지를 저장하는 방식으로 답을 구했다.

처음에는 파이썬(Python3)으로 문제를 풀고, 같은 코드를 자바로 구현해서 제출했다.
각각은 다음과 같으며, T = 1,000,000,007이다.

# 파이썬 코드
...

for i in range(7, len(dp)):
	dp[i] = dp[i-1] + 2*dp[i-2] + 6*dp[i-3] + dp[i-4] - dp[i-6]
    dp[i] %= T

...

// 자바 코드
...

for(int i=7; i < dp.length; i++) {
	dp[i] = dp[i-1] + 2*dp[i-2] + 6*dp[i-3] + dp[i-4] - dp[i-6];
	dp[i] %= T;
}

...

두 코드가 논리적으로 완전히 동일하다고 생각했고, 파이썬으로 작성한 코드는 정답 처리가 되었기 때문에 자바 코드도 동일하게 정답으로 처리될 줄 알았다.
그러나 자바로 작성한 코드는 절반정도의 테스트 케이스를 통과하지 못했다.

문제의 원인을 생각해보다가, 아래의 식이 항상 양수가 아니라는 것을 알 수 있었다.

dp[i-1] + 2*dp[i-2] + 6*dp[i-3] + dp[i-4] - dp[i-6]

그래서 자바 코드를 다음과 같이 수정했고, 모든 테스트 케이스를 통과할 수 있었다.

// 자바 코드
...

for(int i=7; i < dp.length; i++) {
	dp[i] = dp[i-1] + 2*dp[i-2] + 6*dp[i-3] + dp[i-4] - dp[i-6];
    dp[i] += T;
	dp[i] %= T;
}

...

$T∣(a-b)$일 때 $a ≡ b($mod $T)$ 이므로 $a ≡ (a+T) ($mod $T)$이다.
따라서 T를 한번 더해주는 것으로 같은 결과를 가지는 양의 정수를 얻을 수 있다.

---

그러면 파이썬으로 작성한 코드는 왜 통과한걸까?
두 언어가 나눗셈을 다루는 방식이 다르기 때문이다.
각 언어를 사용해서 같은 연산을 실행해보았다.

먼저 자바로 실행한 코드이다. 각 연산의 결과는 주석으로 적어두었다.

// 자바
public class Main {
    public static void main(String[] args) {
        print(7/3);     // 2
        print(7%3);     // 1
        print(-7/-3);   // 2
        print(-7%-3);   // -1
        print(-7/3);    // -2
        print(-7%3);    // -1
        print(7/-3);    // -2
        print(7%-3);    // 1
    }

    public static void print(int num) {
        System.out.println(num);
    }
}

자바의 경우,

• 몫을 구할 때는 제수와 피제수의 부호의 곱을 마지막에 붙여준다.
  -7/3 = -(7/3) = -2
  7/-3 = -(7/3) = -2

• 나머지의 수학적 정의에 따라 $a=bq + r$에 위에서 구해진 몫($q$)을 식에 대입했을 때 가능한 $r$이 모듈러 연산의 결과로 나오게 된다.
  결과적으로 나머지의 부호는 피제수(나누는 수)의 부호를 따라가게 되며
  그렇기 때문에 피제수가 음수라면, 모듈러 연산의 결과가 음수가 나온다.

위 문제를 자바로 푼 코드에서 피제수 (dp[i-1] + 2*dp[i-2] + 6*dp[i-3] + dp[i-4] - dp[i-6] )가 음수일 때 모듈러 연산의 결과값이 음수로 나온 이유는 이 때문이다.

파이썬은 아래와 같다.

# 파이썬
print(7//3)     # 2
print(7%3)      # 1
print(-7//-3)   # 2
print(-7%-3)    # -1
print(-7//3)    # -3
print(-7%3)     # 2
print(7//-3)    # -3
print(7%-3)     # -2

파이썬의 경우,

• 몫을 구할 때 계산된 결과값(실수)를 내림한다.
  7/-3 = -2.33333... $\rarr$(내림)$\rarr$ -3

• 몫이 나눗셈 실수값의 내림이기 때문에, 제수와 피제수의 부호가 다를 경우
  |제수 $\times$ 몫| $\geq$ |피제수| 이다.
  몫은 항상 음수이며(제수/피제수의 부호가 다르므로) $a=bq + r$ 이기 때문에
  r은 |제수 $\times$ 몫|을 감소시켜 |피제수|가 되도록 하는 값이어야 한다.
  따라서 나머지는 제수의 부호를 따라간다.

따라서 위 문제에서는 제수(T)가 양수이므로 모듈러 연산의 결과가 항상 양수였던 것이다.
두 언어 모두 몫을 구하는 방식은 다르나 $a=bq + r$는 만족한다.