피보나치수

피보나치 수를 구하는 가장 기초적인 알고리즘입니다. $$ F_n = F_{n-1} + F_{n-2} (n>=2) $$ 점화식을 그대로 구현하여 재귀적으로 풀어내면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 /** * */ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; /** * @author jaeji * */ public class Main { static int fibonacci(int no) { if(no==0) return 0; else if(no==1) return 1; else return fibonacci(no-1)+fibonacci(no-2); } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //BufferedReader br = new BufferedReader( new FileReader("input.txt" ) ); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int result = fibonacci(n); System.out.println(result); } }

피보나치 수 두번째 입니다. DP로 푸는 문제입니다. 점화식으로 풀때는 Top-down 방식이지만 DP로 풀때는 Bottom-up 방식입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.StringTokenizer; /** * @author jaeji * */ public class Main { static long[] arr = new long[91]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) ); //BufferedReader br = new BufferedReader( new FileReader("input.txt" ) ); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); arr[1] = 1; for(int i=2;i<=n;i++) { arr[i] = arr[i-1] + arr[i-2]; } System.out.println(arr[n]); } }