[Java] 재귀 알고리즘 메모화

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다.

---

public class Main {
	static void recur(int n)
	{
	    if(n > 0)
	    {
	        recur(n - 1);
	        System.out.println(n);
	        recur(n-2);
	    }
	}
	
    public static void main(String[] args) throws Exception
    {
    	recur(4);
    }
}
/*
1
2
3
1
4
1
2
*/

위 recur 메소드는 실행 과정에서 같은 계산을 여러번 반복하여 수행한다.

위 에서 보는 것과 같이 recur(4)를 호출하면 recur(1)을 3회 실행한다.

n 값이 커지면 반복하는 계산 횟수는 더욱 늘어난다.

 

recur(3)은 1, 2, 3, 1을 차례로 출력하므로 출력할 문자열"1\n2\n3\n1"을 메모한다.

다시 recur(3)이 호출되었을 때 메모해 둔 문자열을 화면에 출력하면 중복하여 계산할 필요가 없다.

 

여기서 메모화 기법을 사용하면 동일한 계산을 반복하지 않고 1회만 수행할 수 있다.

import java.util.Scanner;

class RecurMemo {
    static String[] memo;

    //--- 메모화를 도입한 메서드 recur ---//
    static void recur(int n) {
        if (memo[n + 1] != null)
            System.out.print(memo[n + 1]);                              // 메모를 출력
        else {
            if (n > 0) {
                recur(n - 1);
                System.out.println(n);
                recur(n - 2);
                memo[n + 1] = memo[n] + n + "\n" + memo[n - 1];        // 메모화
            } else {
                memo[n + 1] = "";     // 메모화 : recur(0)과 recur(-1)은 빈 문자열
            }
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.print("정수를 입력하세요 : ");
        int x = stdIn.nextInt();

        memo = new String[x + 2];
        recur(x);
    }
}

 

구체적으로 보면 memo에 메모하는 과정은 아래와 같다.