java) 조합(combination) 문제 메모이제이션 기법 활용하기 (dfs)

아래와 같은 문제를 풀 경우 메모이제이션 기법을 활용하자

 

메모이제이션이란 이미 확인한 값이 있다면 더이상 자식 노드를 생성하지 않고 해당 값을 사용하여 불필요한 경우의 수를 고려하지 않아도 되는 기법이다.

 

출처: 인프런

 

아래 전체 코드를 보며 메모이제이션 성능을 확인하고자 한다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main {

    static int[][] visited;
    static int n , r ;

    public static int dfs(int n, int r){
        if (n == r || r == 0) return 1;
        else{
            return dfs(n-1,r-1)+dfs(n-1,r);
        }
    }

    public static int dfs_memo(int n, int r) {
        if (visited[n][r] > 0) return visited[n][r];
        if (n == r || r == 0) return 1;
        else{
            return visited[n][r] = dfs_memo(n-1,r-1)+dfs_memo(n-1,r);
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        r = Integer.parseInt(st.nextToken());

        visited = new int[35][35]; // 요구사항

        long beforeTime = System.currentTimeMillis();
        System.out.println("dfs: " + dfs(n,r));
        long afterTime = System.currentTimeMillis();
        long time = (afterTime-beforeTime);
        System.out.println("[메모이제이션 전]dfs 수행 시간: " + time + "ms");

        long memo_beforeTime = System.currentTimeMillis();
        System.out.println("dfs with memo: " + dfs_memo(n,r));
        long memo_afterTime = System.currentTimeMillis();
        long memo_time = (memo_afterTime-memo_beforeTime);
        System.out.println("[메모이제이션 후]dfs 수행 시간: " + memo_time + "ms");
    }
}

 

시간 차이를 명확히 비교 하기 위해 input으로 33 19의 값을 넣었다. 결과는 아래와 같다.

명확한 성능 차이를 보인다.