[프로그래머스/JAVA] 피보나치 수

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

평소와 같이 프로그래머스에 들어갔다가 흥미로운 강의를 봤다.

코딩테스트 연습 힌트 모음집

문제 풀 때 힌트가 간절할 때가 많은데 이렇게 모음집이 있다니 무슨 문제인지 보러간다!하고 들어가봤다.

근데 문제가 안나오고 힌트부터 나와서 조금 당황함

아무튼 첫 번째 힌트를 먼저 본 덕에 이 문제는 재귀로 풀면 안된다는 사실을 먼저 알고 시작했다.

 

for문으로 피보나치 수열을 어떻게 구할 수 있을까?

f(n) = f(n-2) + f(n-1)이다. 말로 풀어 쓰자면 내가 구하고자 하는 값은 이 값의 전 값과 전전 값을 더하면 된다.

-----------

f(0) = 0

f(1) = 1

-----------

f(0)과 f(1)은 전 값 또는 전전 값이 없다. 그래서 얘네는 규칙이 아닌 정해진 값이다.

진짜 규칙은 f(2)부터 나온다.

f(2) = f(1) + f(0) = 1 + 0 = 1

f(3) = f(2) + f(1) = 1 + 1 = 2

f(4) = f(3) + f(2) = 2 + 1 = 3

.

.

.

f(n) = f(n-1) + f(n-2)

 

f(0)과 f(1)은 이미 정해져 있으니 f(2)부터 f(n)까지 값을 저장하면서 f(n) = f(n-1) + f(n-2) 를 반복해주면 된다.

a = f(n-2)의 값을 저장할 변수

b = f(n-1)의 값을 저장할 변수

class Solution {
    public int solution(int n) {
        int answer = 0;
        int a = 0;
        int b = 1;
        for(int i=1; i < n; i++){
            int c = a + b;
            a = b;
            b = c % 1234567;
        }
        return answer = b;
    }
}

 

b에 값을 저장하기 전 1234567로 나눠주는 이유 : 나머지 연산의 성질 때문

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

 

피보나치수열의 100000번째 수는 (정확히 얼만지는 모르지만) 매우 큰 수이다. int 뿐 아니라 long의 범위도 벗어난다. 이렇게 큰 수를 다뤄야 할 때 문제에서는 보통 특정 숫자로 나눈 값을 return 하라고 한다.

처음에 이런 유형의 문제를 풀었을 때는 for문이 끝난 뒤 마지막 단계에서만 나머지를 구했었다. 하지만 이렇게 하게되면 for문 안에서 값들이 int 또는 long의 자료형의 범위를 넘어서게 되고, 오버플로우된 값에서 나머지를 구해봤자 오답이 나온다.

 

이 때 사용해야 하는 것이 나머지 연산의 성질

a와 b를 더한 값의 나머지는 a 의 나머지와 b의 나머지를 더한 후 나눈 나머지와 같다.(나머지탈트)

결론은 맨 마지막에만 나누지 말고 모든 단계에서 나눠라!이다.

 

내 코드에서 나머지를 구하는 연산은 딱 한 줄이다. 왜 a+b를 구할 때도 아니고 b에 값을 저장할 때 나눴을까?

사실 a+b를 구할 때 나눠줘도 된다 ㅎ

-------------------------------------------

i = 1 일 때 for문 내부에서는

c = a + b = 0 + 1 = 1

a = b = 1

b = c % 1234567 = 1

-------------------------------------------

i = 2 일 때 for문 내부에서는

c = a + b = 1 + (1 % 1234567) = 2

a = b = (1 % 1234567) = 1

b = c % 1234567 = 2 % 1234567 = 2

-------------------------------------------

i = 3 일 때는 for문 내부에서는

c = a + b = (1 % 1234567)  + (2 % 1234567) = 3

a = b = (2 % 1234567) = 2

b = c % 1234567 = 3 % 1234567 = 3

-------------------------------------------

이와 같이 i가 3만 돼도 a와 b가 이미 1234567로 나눈 나머지임을 볼 수 있다.

 

 

후기

피보나치수열을 오랜만에 구현해봤는데 열심히 규칙 찾고 나머지의 성질까지 찾아볼 수 있는 기회가 되었다.

문제가 어렵지 않아서 사고의 과정을 길게 써봤는데 앞으로 공부할 때도 내가 어떻게 답을 도출해냈는지 정리해보면 좋을 것 같다.