dfs 를 이용하여 조합 구하기

오늘은 dfs를 이용한 조합 구하기를 정리해볼꺼다.

 

조합은 서로다른 n 개중에 r개를 선택하는 경우의 수를 의미한다. 

 

조합을 다른식으로 표현하면 아래처럼 표현이 되는데 알고리즘을 구현할때는 아래 방법을 알고 있어야 한다.

그리고 이를 dfs를 이용해 내려가다 보면 이런 생각이 들것이다. 

"중복되는 것들이 생기네?"

 

이렇게 중복되는 값을 또 재귀로 돌리다보면 분명 성능이 좋지 않다. 이를 위해 다이나믹 프로그래밍 즉 dp를 이용하여 효과적으로 구현할 수가 있다.

 

아래는 구현안 예제 코드이다.

import java.util.Scanner;

public class Combination {
    static int[][] dp ;
    public static void main(String[] args) {
        Combination comb = new Combination();
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int r = in.nextInt();

        dp = new int[n+1][n+1];

        System.out.println(comb.dfs(n,r));
    }

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

끝.