[Programmers] 피보나치 수 - 연습문제 (DP)

// 피보나치 수 - 연습문제 (DP)
public class Fibonacci {

	// Top-Down(재귀) 방식은 계속해서 자기 자신을 호출하기 때문에 시간과 효율측면에서 좋지 않을 수 있음.
	// Bottom-Up(반복문) 방식을 활용
	// Overflow 처리
	public int solution(int n) {

		if (n == 1 || n == 2) {
			return 1;
		}

		long a = 1, b = 1, c = 0;

		for (int i = 3; i <= n; i++) {
			c = (a + b) % 1234567; // overflow 처리
			a = b;
			b = c;
		}
		return (int) c;
	}

	// Memoization 방식
	// Overflow 처리
	public int solution1(int n) {

		int[] arr = new int[n + 1];

		arr[1] = arr[2] = 1;
		for (int i = 3; i <= n; i++) {
			arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
		}

		return arr[n];
	}

	public static void main(String[] args) {

		Fibonacci s = new Fibonacci();
		System.out.println(s.solution1(3)); // 2
		System.out.println(s.solution1(5)); // 5
		System.out.println(s.solution1(5000000));

	}
}

• Dynamic Programming 이용 (재귀로 구현 시 StackOverFlow 발생)

• 반복문(Bottom-Up)은 재귀(Top-Down)에 비해 시간과 메모리를 적게 사용하는 장점이 있다.
  https://semaph.tistory.com/16 참고

• 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.
  Dynamic Programming의 핵심이 되는 기술
  https://hongku.tistory.com/161 Memoization 참고