Overflow(오버 플로우) 방지하기 : 나머지 연산 활용

문제 상황

코딩 테스트 문제를 풀다 보면, 다음과 같은 조건이 있을 때가 있다.

경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

위와 같은 조건은 숫자가 너무 커져 발생하는 오버 플로우를 방지하기 위함이다.

하지만 최종 값에만 나머지 연산을 적용할 경우 여전히 오버 플로우가 발생할 때가 있다.

# (n x 2) 바닥 채우기
# n 번째 바닥 
def solution(n):
    # 경우의 수 저장
    DP = [1, 2]
    for i in range(2, n):
        DP.append(DP[i - 2] + DP[i - 1])
    return DP[n - 1] % 1000000007 # 최종 값에만 나머지 연산을 적용할 경우

이럴 땐 연산 과정 중간 중간 나머지 연산을 추가로 적용하는 방식으로 문제를 해결한다.

# (n x 2) 바닥 채우기
# n 번째 바닥 
def solution(n):
    # 경우의 수 저장
    DP = [1, 2]
    for i in range(2, n):
        DP.append((DP[i - 2] + DP[i - 1]) % 1000000007)
    return DP[n - 1] % 1000000007

왜 동작?

나머지 연산을 연산 과정 중에 적용할 수 있는 이유는, 나머지 연산의 분배 법칙 덕분이다.

분배 법칙은 덧셈, 곱셈, 뺄셈에서 성립하고, 아래와 같은 특성이 있다.

 

(A + B) % M = (A % M + B % M) % M

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

(A - B) % M = (A % M - B % M + M) % M

---

참고

[ps] 코딩 테스트에 필요한 수학

프로그래머스

• 예시 코드