피보나치 재귀 - 메모이제이션

연어는결국강으로·2022년 11월 19일
0

알고리즘 공부

목록 보기
12/15

보통의 대부분의 사람이 그렇듯이(나 역시 낑낑대면서 푼 결과가 아래이다.) 처음 피보나치를 풀면 아래와 같이 풀이하게 된다.

public class No01 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		for (int i = 1; i <= n; i++) {
			System.out.println(dfsN(n));
		}
	}

	public static int dfsN(int n) {
		if (n == 1) {
			return 1;
		} else if (n == 2) {
			return 1;
		} else {
			return dfsN(n - 2) + dfsN(n - 1);
		}
	}
	
}

n=45쯤을 넣게 되면 엄청난 시간이 소요된다. 다음값을 나올때까지 꽤나 오래 기다려야 한다.

그래서 이것을 좀 더 개선해보면 아래와 같이 배열에 재귀함수의 결과를 기록하는 것이다.

public class No01 {

	public static int[] fibo;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		fibo = new int[n + 1];
		dfsN(n);
		for (int i = 1; i <= n; i++) {
			System.out.println(fibo[i]);
		}
	}

	public static int dfsN(int n) {
		if (n == 1) {
			return fibo[n] = 1;
		} else if (n == 2) {
			return fibo[n] = 1;
		} else {
			return fibo[n] = dfsN(n - 2) + dfsN(n - 1);
		}
	}
	
}

한 차원 더 업그레이드하여 메모이제이션을 쓰면 시간을 더욱 단축할 수 있다. 말하자면 fibo배열에 저장해놓은 값을 쓰는 것이다. 메모이제이션을 쓰고 실행해보면 결과가 바로 출력된다.

public class No01 {

	public static int[] fibo;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		fibo = new int[n + 1];
		dfsN(n);
		for (int i = 1; i <= n; i++) {
			System.out.println(fibo[i]);
		}
	}

	public static int dfsN(int n) {
		if (fibo[n] != 0) {
			return fibo[n];
		}

		if (n == 1) {
			return fibo[n] = 1;
		} else if (n == 2) {
			return fibo[n] = 1;
		} else {
			return fibo[n] = dfsN(n - 2) + dfsN(n - 1);
		}
	}
	
}

재귀와 반복문의 성능을 비교하면 당연히 반복문의 성능이 우월하다. 그 이유는 반복문의 경우 스택프레임을 하나만 쓰는데, 재귀의 경우 재귀로 호출할 때마다 스택프레임을 계속해서 쓰기 때문이다.

0개의 댓글

Powered by GraphCDN, the GraphQL CDN