피보나치 수열
1, 1, 2, 3, 5, 8, 13, 21, ...
public class Fibo { public static long fiboByRecursion(long n) { if (n == 1 || n == 2) return 1; return fibo(n-1) + fibo(n-2); } public static long fiboByLoop(long n) { if (n == 1 || n == 2) return 1; long sum = 1; long prev = 1; long temp; for(long i=3; i<=n; i++) { // sum은 n-1 // prev는 n-2 temp = sum; sum = sum + prev; // n-1 + n-2 prev = temp; // n-2에 n-1을 대입 } return sum; } public static void main(String[] args) { System.out.println( Fibo.fiboByRecursion(10) ); System.out.println( Fibo.fiboByLoop(10) ); } }
n이 작을때는 문제 없으나 40 이상으로 넘어가면 수행시간이 기하급수적으로 증가한다.
중복계산을 없애기 위해 memoization을 사용하자.
반환형이 long임에도 n이 커지면 오버플로가 발생할 수 있다는 점을 유의하자.
public class Fibo { static final long memo[] = new long[200]; public static long fibo(long n) { if(memo[n] > 0) return memo[n]; if (n == 1 || n == 2) return memo[n] = 1; return memo[n] = fibo(n-1) + fibo(n-2); } public static void main(String[] args) { System.out.println( Fibo.fibo(8) ); } }
memoization을 적용하였다
TBC
#1
0과 1로 이루어진 문자열이 있다. 이 문자열에는 1이 연속하여 나올 수 있지만 0이 연속하여 나올 수는 없다.
예를 들어 1111, 110111, 010101, 1101110은 올바른 문자열이지만 000, 1100111 등은 잘못된 문자열이다.
길이가 n인 올바른 문자열은 몇 개일까?
#2
n개의 계단을 한 번에 하나 또는 두개씩 올라간다. n개의 계단이 있을 때 이를 올라가는 방법은 몇 가지인가?
#3
매일 1/2 확률로 회사에 지각하는 사람이 있다. 3일 연속 지각했을때에만 팀장에게 혼난다. 20일간 출근할 때, 한 번도 혼나지 않을 확률은 얼마일까? 매일 2/3 확률로 지각할 경우의 확률은?
댓글0