728x90
인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다.
- 문제 설명 : n이 입력되면 피보나치 수열 n개의 항을 출력
- 피보나치수열 : 앞의 2개의 수를 합하여 다음 숫자가 되는 수열(첫 번째와 두 번째 항은 1)
자료 구조 책에서 재귀를 설명할 때 흔히 볼 수 있는 문제로 보통 반복문 또는 재귀 두 가지 방법으로 풀이하는데 이번 문제에서는 재귀와 메모이제이션을 사용하여 풀이한다.(물론 속도는 반복문을 사용하는 쪽이 더 빠르다)
참고 : 반복문으로 푸는 방법
재귀를 사용한 풀이
package inflearn;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static int fibo(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fibo(n - 1) + fibo(n - 2);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
for (int i = 1; i <= n; i++) {
System.out.print(fibo(i) + " ");
}
}
}
위 그림은 재귀 형태로 피보나치수열의 다섯 번째 항을 구할때 함수호출 과정이다. 다섯번째 항 하나를 구하는 과정임에도 불구하고, 함수 호출도 많고 중복되는 함수 호출도 눈에 띈다.
재귀 + 메모이제이션을 사용한 풀이
메모이제이션(memoization)이란?
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.
메모이제이션을 사용하여 배열을 하나 만들고 값을 재사용하여 풀이한 결과, 재귀만을 사용한 위의 풀이 방법과 비교하여 실행 속도는 엄청난 차이가 났다.
(50개를 출력하는 상황에 재귀 풀이는 약 76000ns, 재귀+메모이제이션 풀이는 17ns 소요)
package inflearn.recursive_tree_graph;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main7_4 {
//이전에 계산한 값을 저장해놓을 배열
static int[] arr;
public static int fibonacci(int n) {
//n번쨰 수가 저장되어 있다면 재사용
if (arr[n] > 0) {
return arr[n];
}
//arr[n]에 n번째 피보나치 수열 값을 저장해둔다.
if (n == 1 || n == 2) {
arr[n] = 1;
return arr[n];
} else {
arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
return arr[n];
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
arr = new int[n+1];
fibonacci(n);
for (int i = 1; i <= n; i++) {
System.out.print(arr[i] + " ");
}
}
}
댓글