[알고리즘] 조합과 동적 계획법 (dynamic programming)

조합 (Combination)

• 서로 다른 n개의 수 중 순서를 생각하지 않고 r개를 선택; nCr로 표현
• 그에 반해 순열 nPr은 순서를 고려

https://www.pulja.co.kr/post_board_view?postSeq=85

조합의 성질

• 이항계수와 파스칼의 삼각형과 관련
• 이항계수: 이항정리에서 각 항의 계수인 조합 nCr → 쉽게 말해, 이항정리에서는 각 항의 계수가 조합으로 나타난다.
• 이항정리: 두 항의 합의 거듭제곱인 (a+b)^n을 전개한 결과를 정리한 것
• 파스칼의 삼각형: 이항계수들을 삼각형 피라미드 형태로 배열한 것

이항정리

 

https://samtoring.com/str/qstn/QST0009166

 

이를 토대로 코드를 짜면 다음과 같다. 아래쪽에 combi() 함수를 보면 위 성질을 적용하여 재귀 호출한 것을 알 수 있다. 

import java.util.Scanner;

public class Combination {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();

        System.out.println(combi(n, r));
    }

    static int combi(int n, int r) {
        if (n == r || r == 0) {
            return 1;
        }

        return combi(n - 1, r) + combi(n - 1, r - 1);
    }
}

 

팩토리얼 정의를 이용해 조합을 나타낼 수도 있다.

import java.util.Scanner;

public class Combination_iter {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();

        System.out.println(factorial(n) / (factorial(n - r) * factorial(r)));

    }

    private static int factorial(int n) {
        if (n == 1) {
            return 1;
        }

        return n * factorial(n - 1);
    }
}

 

이처럼 자기 자신의 함수를 반복적으로 호출하면서(=재귀 호출) 코드를 실행할 수 있지만 반복문으로도 풀 수 있다. 정확히 말하면 반복문을 통해 더 효율적으로 실행할 수 있다. 왜냐하면 재귀 호출의 경우 같은 함수를 중복적으로 호출하기 때문에 메모리를 불필요하게 사용한다. 예를 들어, combi(5,3)를 호출할 경우 과정은 다음과 같다.  

 

combi(4,3) + combi(4,2)

(combi(3,3) + combi(3,2)) + (combi(3,2) + combi(3,1))

(1 + (combi(2,2) + combi(2,1))) + ((combi(2,2) + combi(2,1)) + (combi(2,1) + combi(2,0)))

(1 + (1 + (combi(1,1) + (combi(1,0)))) + ((1 + (combi(1,1) + combi(1,0))) + ((combi(1,1)+combi(1,0)) + 1))

(1 + (1 + (1 + 1))) + ((1 + (1 + 1)) + ((1 + 1) + 1)) = 10

 

이렇게 보면 같은 함수가 반복적으로 호출되고 있음을 알 수 있는데, 이는 n이 커질수록 기하급수적으로 증가한다. 그렇게 되면 스택에 스택프레임이 많이 쌓이면서 언젠가는 stack overflow를 일으킬 것이다. 이에 대한 대안으로 반복문과 메모리 저장 개념을 이용해 동적 계획법을 활용할 수 있다. 동적계획법에서 메모리에 먼저 값을 저장해 두고 값을 꺼내 쓰는 메모이제이션(memoization)을 사용하는 것이다.

import java.util.Scanner;

public class Combi_loop {

    static int[][] dp;
    
    public static void main(String[] args) {

        /**
         * top-down 방식; 위에서 아래로
         */

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        dp = new int[n + 1][r + 1];

        System.out.println(combi(n, r));
    }

    private static int combi(int n, int r) {
        if (dp[n][r] > 0) { // 값이 저장되어 있다면
            return dp[n][r];
        }

        if (n == r || r == 0) {
            return dp[n][r] = 1;
        }

        return dp[n][r] = combi(n - 1, r) + combi(n - 1, r - 1);
    }
}

import java.util.Scanner;

public class Combi_loop {

    static int[][] dp;

    public static void main(String[] args) {

        /**
         * bottom-up 방식; 아래에서 위로
         */

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int r = sc.nextInt();
        dp = new int[n + 1][r + 1];

        // n == r
        for (int i = 0; i <= r; i++) {
            dp[i][i] = 1;
        }

        // r == 0
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= r; j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        
        System.out.println(dp[n][r]);
    }
}

동적 계획법(Dynamic Programming)

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 [참고: 위키백과]
• 가능한 모든 방법을 고려하기 때문에 시간이 조금 걸리지만 최적해를 구할 수 있다
  cf. 그리디 알고리즘은 그때마다의 최적의 경로를 우선하지만 최종적인 최적해는 보장할 수 없음
• 메모이제이션(memoization)을 활용하여 중복 연산을 줄이고 수행 속도를 높인다 
  cf. memoization: 어떠한 정답을 구하면 그 정답을 메모해 두고 메모를 이용하는 방식
• top-down 방식과 bottom-up 방식 존재
• 최단 경로 문제(다익스트라, 벨만포드 등), LCS(최장 공통 부분 수열) 등에 적용

top-down 방식과 bottom-up 방식은 문제해결의 순서가 이름에서 드러나듯이 차이가 있는데 표로 정리해 보면 다음과 같다.

top-down 방식	bottom-up 방식
1. 하향식 문제해결 방식 2. 가장 큰 문제를 방문한 후 작은 문제를 호출하여 답을 찾는다. 3. 일반적으로 재귀 함수를 이용해 구현한다.  4. 모든 부분을 다 구하지 않아도 될 때 유리하다.	1. 상향식 문제해결 방식 2. 가장 작은 문제들로부터 답을 구해가며 전체 문제의 답을 찾는다. 3. 일반적으로 반복문을 이용해 구현한다. 4. 모든 부분을 다 구해야 할 때 유리하다.

 

무작정 둘 중 어느 방식이 더 좋다고 말하는 것은 적절하지 않다. 문제 상황과 맥락을 고려하여 적절한 방식을 택하는 게 현명하다. 백준 문제를 풀 때도 재귀로 하는 게 메모리나 시간 관점에서 더 좋을 수도 있고, 반대로 반복문으로 구현하는 게 더 빠를 수도 있다. 그러니 둘 다 익혀두는 게 베스트다!

 

[수학 참고:https://terms.naver.com/entry.naver?docId=6605839&cid=40942&categoryId=32213,

https://yeonjewon.tistory.com/80]

이항계수

[반복문, 재귀 참고: https://yeonjewon.tistory.com/80]

[Algorithm] 반복문(iteration) vs 재귀(recursion)

[문제 및 알고리즘 전체 참고: https://stlab.tistory.com/194,

https://stlab.tistory.com/159#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98]

[백준] 1010번 : 다리 놓기 - JAVA [자바]

[백준] 11050번 : 이항 계수 1 - JAVA [자바]

 

[DP 특징 참고: https://jaehoney.tistory.com/208, https://devruby7777.tistory.com/entry/Top-down-DP%EC%99%80-Bottom-up-DP%EC%9D%98-%EC%B0%A8%EC%9D%B4%EC%A0%90%EA%B3%BC-%EC%9E%A5%EB%8B%A8%EC%A0%90-%EC%93%B0%EB%8A%94-%EA%B2%BD%EC%9A%B0, https://velog.io/@chnh506/Top-down-%EB%B0%A9%EC%8B%9D%EA%B3%BC-Bottom-up-%EB%B0%A9%EC%8B%9D]

DP(Dynamic Programming) - Top-down과 Bottom-up

Top-down DP와 Bottom-up DP의 차이점과 장단점, 쓰는 경우

Top-down 방식과 Bottom-up 방식