[알고리즘] 프로그래머스 - 피보나치 수

1. 조건

---

2. 내 생각

---

먼저 피보나치수열의 개념을 다시 한 번 생각해보았다. 데이터가 증가하면 시간도 더 증가하며 트리의 높이만큼 진행하게 되는 것으로 아래와 같다.

 

class Solution {
    public int fun(int a) {
        if (a == 0) {
            return 0;
        } else if (a == 1) {
            return 1;
        } else {
            return fun(a-1) + fun(a-2);
        }
    }

    public int solution(int n) {
        return fun(n);
    }
}

위의 코드는 피보나치 수열의 동작 원리에대한 코드이고 재귀 방식을 사용하였다. 하지만 이전의 값을 또 다시 계산하는 로직으로 O(2^n)의 시간복잡도가 예상되었고 아래와 같이 반복문을 통해 O(n)으로 시간복잡도를 낮춰보았다.

class Solution {
    public int solution(int n) {
        int a = 0; 
        int b = 1;

        if (n <= 1) {
            return n;
        }

        for (int i=2 ; i<=n ; i++) {
            int result = a+b;
            a = b;
            b = result;
        }

        return result;
    }
}

3. 실행 결과

---

class Solution {
    public int solution(int n) {
        int a = 0; 
        int b = 1;
        int result = 0;
        if (n <= 1) {
            return n;
        }

        for (int i=2 ; i<=n ; i++) {
            result = (a+b)%1234567;
            a = b;
            b = result;
        }

        return result;
    }
}

최종적인 코드는 주어진 문제의 상황에 맞게 1234567로 나눈값의 나머지를 return하여 문제를 풀 수 있었는데 한 가지 없어도 되는 코드가 있었다. 내가 작성한 코드에서는 매개변수 n의 값이 0과 1일때를 고려해 if 조건문을 만들었는데 문제의 조건에 n은 2 이상의 수라고 명시되어 if 부분이 필요가 없던 것이다.

결론은 내가 작성한 위의 코드에서 If 부분을 제거하여도 정상적으로 코드가 돌아간다는 것이다.