[99클럽 코테 스터디 21일차 TIL] 프로그래머스 - 피보나치 수

99클럽 코테 스터디 21일차 TIL 입니다.

[level 2] 피보나치 수 - 12945

문제 링크

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

n은 2 이상 100,000 이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

return

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

풀이 코드

class Solution {
    public int solution(int n) {
        int[] fibo = new int[n + 1];
        fibo[0] = 0;
        fibo[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1234567;
        }
        return fibo[n];
    }
}

Time: 3.11 ms
Memory: 74.4 MB

풀이 코드 자체는 간단하다. n 번째 피보나치 수를 구해서 1234567 로 나눈 나머지를 반환하면 되기 때문에 배열의 크기를 n + 1 로 선언해야 n 번째 피보나치 수를 구할 수 있다. 이렇게 생각해서 n 번째 피보나치 수를 가져와서 1234567 로 나눈 나머지를 반환하면 절반만 정답이 된다.

왜냐하면 46번째 피보나치 수가 1,836,311,903 (18억 3631만 1903) 이기 때문에 47번째부터는 정수형의 범위를 가뿐히 넘어간다. 심지어 n 은 10만 이하의 수이기 때문에 long 자료형도 금방 넘어가게 된다.

이를 해결하기 위해 1234567 로 먼저 나눠서 배열에 담으면 풀이에 성공한다. 그런데 이 과정에서 이해가 안되는 부분이 있었다. 범위를 넘어가는 문제를 해결하기 위해서 처음엔 아래와 같이 풀었다.

class Solution {
    public int solution(int n) {
        int[] fibo = new int[n + 1];
        fibo[0] = 0;
        fibo[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            fibo[i] = fibo[i - 1] % 1234567 + fibo[i - 2] % 1234567;
        }
        return fibo[n];
    }
}

이렇게 풀면 틀린 풀이가 된다. 왜냐하면 피보나치 수 29번째와 30번째는 아래와 같다.

29번째 피보나치 수 : 514229
30번째 피보나치 수 : 832040

이제 31번째 피보나치 수에 1234567 을 나눈 값을 정답 풀이 코드와 틀린 풀이 코드로 구해보자.

정답 풀이 : (514229 + 832040) % 1234567 -> 1346269 % 1234567 = 111702
틀린 풀이 : 514229 % 1234567 + 832040 % 1234567 -> 514229 + 832040 = 1346269

위처럼 n-1 + n-2 의 값이 1234567 을 넘어가는 순간에 두 풀이에 차이가 생긴다. 그래서 이 다음으로 푼 풀이는 반환할 때 한번 더 1234567 을 나누는 방법이었다.

class Solution {
    public int solution(int n) {
        int[] fibo = new int[n + 1];
        fibo[0] = 0;
        fibo[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            fibo[i] = fibo[i - 1] % 1234567 + fibo[i - 2] % 1234567;
        }
        return fibo[n] % 1234567;
    }
}

앞서 정답 풀이와 틀린 풀이를 비교한 연산 과정을 따라가면 위 풀이가 왜 정답인지는 쉽게 유추가 가능하다. 따라서 아래와 같은 결론이 도출된다.

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

찾아보니 위 법칙은 모듈로 연산 분배 법칙 중 덧셈에 대한 법칙이다. 증명은 아래와 같다.

모듈로 연산 분배 법칙 - 덧셈 증명

좌변 - (a + b) % m
- (a + b) % m 는 a + b를 m 로 나눈 나머지이다.
- a % m 는 a - m * k1, b % m = b - m * k2 로 표현할 수 있다.
- a + b - m * (k1 + k2) = a + b - m * k3 이므로 (a + b) % m = a % m + b % m 은 성립한다.
- 합동식으로 표현하면 a + b = a + b (mod m) 이다. 즉, a % m + b % m = (a + b) % m 이다.

합동식이란?

고정된 양의 정수 m(!= 1)에 대해 두 정수 a, b가 m | (a - b) 를 만족할 때, a 와 b 는 m 을 법으로한 합동 또는 합동식이라고 부르고 기호로는 a = b (mod m) 으로 표현한다.

( | 의 의미는 (a - b) 는 m 으로 나누어 떨어진다는 의미로 a - b 가 m 으로 나누어 떨어진다면, a = b (mod m) 으로 표현하겠다는 것이다. 다르게 말하면 a 와 b 는 m 에 의하여 나눠 졌을 때의 나머지가 동일하다는 것을 의미한다. )

우변 - (a % m + b % m) % m
- 앞서 좌변의 증명에 따라 a + b = a + b (mod m) 이므로, a % m + b % m = (a + b) % m 은 성립한다.
- 따라서 (a % m + b % m) % m = ((a + b) % m) % m 이고, (a + b) % m 을 m 으로 나눈 나머지는 (a + b) 를 m 으로 나눈 나머지와 동일하다.
- 따라서 (a + b) % m = a + b (mod m) 이다.

따라서 (a + b) % m = a % m + b % m, (a % m + b % m) % m = ((a + b) % m) %m = (a + b) % m 이므로 (a + b) % m = (a % m + b % m) % m 은 성립한다.

모듈로 연산 분배 법칙은 덧셈 뿐만 아니라 곱셈과 뺄셈에도 성립된다.

곱셈 - (a * b) % m = ((a % m) * (b % m)) % m
뺄셈 - (a -b) % m = ((a % m) - (b % m) + m) % m # 음수 방지를 위해 m 을 더해준다.

돌아보기

수학 공부를 차근 차근 다시 하고 싶단 생각이 든다. 언제 한번 로드맵을 찾아봐야겠다. 중학 수학부터 배우면 될까?

다음에는

자료형의 범위를 항상 유의하기
결과 값 출력하면서 디버깅하기

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL

Previous[99클럽 코테 스터디 20일차 TIL] 프로그래머스 - 큰 수 만들기 Next[99클럽 코테 스터디 22일차 TIL] 프로그래머스 - 멀리 뛰기

Last updated 3 months ago