알고리즘 #0001

• 문제 링크: 바로가기 (클릭)

I. 문제 상황

1. 초기 코드 작성

• 주어진 문제는 너무나도 유명한 피보나치 수열을 구현하는 문제였고, 아래와 같이 [코드 1]을 작성하였다.
• [코드 1] 처음 작성한 코드 답안

class Solution {
    public int solution(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return (solution(n-1) + solution(n-2))%1234567;
        }
    }
}

2. 실행 결과

• 하지만, 아래의 [결과 1]에서처럼 시간 초과가 발생하였다.
• [결과 1]
  

II. 문제 분석

1. 시간 복잡도 계산

• 메서드를 재귀적으로 호출할 경우, 각 solution(n) 호출 시 solution(n-1)과 solution(n-2)을 호출하게 되며, solution(n-1)과 solution(n-2)에서 각각 solution(n-2), solution(n-3)과 solution(n-3), solution(n-4)를 다시 호출하게 되므로 마치 이진 트리가 확장되는 현상과 비슷하다고 볼 수 있다.
• 따라서, 시간 복잡도는 $O(n^2)$이다.

2. 성능 개선

• 동적 계획법을 사용하여 성능을 개선해보고자 한다.
• Map 자료형을 이용하여 solution(n)을 중복으로 조회하지 않도록한다.
• 이진 트리에서 자식 노드로 내려갈 때마다 파생하여 조회하지 않고 기존 데이터를 저장한 map 자료구조를 선형적으로 조회하기만 하면 된다.
• 이에 따라 [코드 2]와 같이 시간복잡도가 $O(n)$이 되도록 알고리즘을 구현한다.
• [코드 2] Dynamic Programming 적용

import java.util.*;
class Solution {
    private static Map<Integer, Long> map = new HashMap<>();
    public static long solution(int n) {
        if (n <= 1) {
            return (long) n;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        long answer = solution(n-1) + solution(n-2);
        map.put(n, answer);
        return answer%1234567;
    }
}

• [결과 2]