[모듈러 연산] 백준 11726 /프로그래머스 - 피보나치 수

문제 자체는 점화식만 구한다면 어렵지 않다.

 

 

dp[1] = 1 / dp[2] = 2 / dp[3] = dp[2] + 2*dp[1] - dp[1]
dp[n] = d[n-1] + dp[n-2]

를 이용하여 재귀로 풀어주었다.

 

 

 

그러나 이렇게만 푸니 틀렸다.

찾아보니 계산하려는 수가 너무 커져 오버플로우가 발생했기 때문이었다.

 

 

정수형 데이터의 타입을 사용할 때에는 반드시 자신이 사용하고자 하는 데이터의 최소/최대 크기를 고려해야 한다.

오버플로우 : 해당 타입이 표현할 수 있는 '최대 표현 범위'보다 큰 수를 저장할 때 발생하는 현상
언더플로우 : 해당 타입이 표현할 수 있는 '최소 표현 범위'보다 작은 수를 저장할 때 발생하는 현상

 

 

---

위 문제에서는  '방법의 수를 10,007로 나눈 나머지를 출력' 이라는 문구가 있다. 

 

일반적으로 수가 지수 크기로 늘어나는 경우 쉽게 값이 커져 int타입이 표현할 수 있는 범위를 넘어가므로,

소수를 나눈 나머지 값을 이용하는 경우가 있다.

이 문제의 경우에서도, 값을 전부 구한 이후에 출력문에서만 %10007 연산을 해주면 오답 결과를 받는다.

 

이는 dp 배열을 저장하는 과정에서 이미 값이 너무 커져 가진 int 메모리에서  오버플로우가 일어나 값이 변형되어 저장되기 때문이다. 자바에서 정수형 변수의 최대값은 int형이 2^31-1이므로, 이 값을 초과하면 오버플로우가 발생한다.

 

 

따라서, 유사한 문장이 문제에 나온다면, 값을 저장하는 순간부터 해당 연산을 넣어주는 모듈러 연산을 수행하여 오버플로우를 방지해야 한다.

 

 

🔎모듈러 연산(Modular arithmetic)
정수 계산에서 사용되는 연산으로, 어떤 수를 다른 수로 나눈 나머지를 구하는 연산
특히 컴퓨터 과학에서는 주로 오버플로우를 방지하거나, 해시 함수에서 해시 값을 구하는 데에 활용된다.

예를 들어, 아래 코드에서는 10,007으로 모듈러 연산을 수행하여 dp 배열의 값이 int형의 범위를 초과하는 것을 방지하였다. 모듈러 연산은 작은 수를 사용할 때는 부담이 없지만, 매우 큰 수를 사용할 때는 계산 시간이 증가할 수 있으므로 주의해야 한다.

 

 

 

public class Baek_11726 {
    static int[] dp = new int[1001];
    public static void main(String[] args) throws IOException {
        dp[1] = 1;
        dp[2] = 2;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int l = Integer.parseInt(br.readLine());
        System.out.println(tiling(l));
    }

    static int tiling(int l){
        if(l<3||dp[l]!=0) return dp[l];
        return dp[l] = (tiling(l-1) + tiling(l-2))%10007;
    }
}

 

 

 

 

 

---

기타 java 자료형 표현 가능 범위

 

종류	저장공간(byte/bit)	값의 범위	기본값
boolean	1/8	true / false	false
byte	1/8	-128 ~ 127	0
char	2/16	\u0000 ~ \uFFFF / 0~65535(유니코트 문자)	'\u0000'
short	2/16	-32768 ~ 32767	0
int	4/32	-2147483648 ~ 2147483647	0
long	8/64	-9223372036854775808 ~ 9223372036854775807	0L
float	4/32	1.40239846E-45f~ (표현 가능 양수 범위)3.40282347E+38f	0.0f
double	8/64	4.94065645841246544E-324  ~ (표현 가능 양수 범위)1.79769313486231570E+308	0.0 또는 0.0d

 

 

 

 

 

+) 바로 비슷한 문제가 프로그래머스에도 있었다

모듈러 연산을 공부한 덕분에 이번에는 속지 않았다😎

 

 

class Solution {
    static int[] dp; 
    public int solution(int n) {
        int answer = 0;        
        dp = new int[n+1];
        
        dp[1] = 1;
        dp[2] = 1;
        answer = fibo(n);
        
        return answer; 
    }
    static int fibo(int n){
        if(n<3||dp[n]!=0) return dp[n];
        return dp[n] = (fibo(n-1) + fibo(n-2))%1234567; //모듈러 연산
    }
}