-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
이 코드는 어떤 부분이 문제인지 궁금합니다.
23.06.21 21:52 작성 조회수 176
0
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);
}
}
답변을 작성해보세요.
0
김태원
지식공유자2023.06.23
안녕하세요^^
이 문제는 피보나치 수열의 각 항을 매번 재귀를 호출해서 구하면 시간초과로 통과되지 않게 되어 있습니다.
영상의 방법으로 해야 시간초과가 나지 않습니다.
이 문제를 재귀로 통과하고 싶으면 메모이제이션 기법을 사용해야 합니다. 초보자에게는 약간 어려울 수 있습니다. 주로 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);
}
}
답변 1