이 코드는 어떤 부분이 문제인지 궁금합니다.

Question

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Main main = new Main(); for (int i = 0; i < n; i++) { System.out.print(main.solution(i) + " "); } } private int solution(int i) { if (i <= 1) { return 1; } return solution(i - 1) + solution(i - 2); } }

김태원 · Answer

안녕하세요^^ 이 문제는 피보나치 수열의 각 항을 매번 재귀를 호출해서 구하면 시간초과로 통과되지 않게 되어 있습니다. 영상의 방법으로 해야 시간초과가 나지 않습니다. 이 문제를 재귀로 통과하고 싶으면 메모이제이션 기법을 사용해야 합니다. 초보자에게는 약간 어려울 수 있습니다. 주로 top - down 다이나믹 기법에 사용합니다. 아래 코드는 위 코드에 메모이제이션을 사용한 코드입니다. 한 번 분석해보세요. import java.util.Scanner; public class Main { public static int[] memo; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); memo = new int[n]; Main main = new Main(); for (int i = 0; i < n; i++) { System.out.print(main.solution(i) + " "); } } private int solution(int i) { if(memo[i] > 0) return memo[i]; if (i <= 1) { return 1; } return memo[i] = solution(i - 1) + solution(i - 2); } }