조합의 경우수(메모이제이션)

1. 문제 설명

조합의 경우수는 일반적으로 다음과 같은 공식을 이용해 계산한다.

하지만 이 공식 대신 재귀와 메모이제이션을 활용한 방식으로 조합수를 구하는 프로그램을 작성해보자.

 

2. 공식

조합수는 다음과 같은 재귀적 성질을 가진다.

즉, n개의 원소에서 r개를 선택하는 경우는 n-1개의 원소에서 r-1개를 선택하는 경우와 n-1개의 원소에서 r개를 선택하는 경우의 합으로 계산된다.

이 공식에 따라 재귀를 이용하여 조합수를 구할 수 있다.

 

3. 입력

첫째 줄에 자연수 n(3 ≤ n ≤ 33)과 r(0 ≤ r ≤ n)이 주어진다.

 

4. 출력

첫째 줄에 조합수를 출력한다.

 

5. 코드 설명

package com.example.codingtest;

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

public class Main {
    static int[][] dy = new int[35][35];  // 메모이제이션을 위한 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);  // n값 입력
        int r = Integer.parseInt(str[1]);  // r값 입력
        System.out.println(DFS(n, r));     // 결과 출력
    }

    public static int DFS(int n, int r) {
        if (dy[n][r] > 0) {  // 이미 계산된 값이 있다면 그 값을 반환
            return dy[n][r];
        }
        if (n == r || r == 0) {  // nCr에서 n == r이거나 r == 0이면 1 반환
            return 1;
        } else {
            return dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);  // 재귀 호출
        }
    }
}

6. 코드 설명

1. 메모이제이션을 위한 배열 dy: 계산된 값을 저장하여 동일한 계산을 반복하지 않도록 한다.
2. 기저 조건: n == r 또는 r == 0인 경우, 결과는 1이다. 이 경우는 더 이상 분할할 수 없는 최소 조합이므로 재귀를 종료한다.
3. 재귀 호출: nCr은 n-1 C r-1과 n-1 C r의 합으로 구할 수 있다. 이 재귀 과정을 통해 조합수를 계산한다.
4. 메모이제이션 적용: 이미 계산된 값은 dy 배열에 저장하여 재계산을 방지하고 성능을 최적화한다.

7. 동작 과정

입력 값으로 n=5, r=3을 입력받으면, 다음과 같은 과정으로 조합수를 계산한다.

• DFS(5,3)은 DFS(4,2)와 DFS(4,3)의 합이다.
• DFS(4,2)는 DFS(3,1)과 DFS(3,2)의 합이다.
• 이 과정을 반복하여 최종적으로 DFS(5,3)을 구하고, 메모이제이션을 통해 계산된 값을 저장하며 최적화한다.

8. 시간 복잡도

이 방법은 메모이제이션을 적용했기 때문에, 중복 계산을 방지하여 시간 복잡도는 O(n * r)로 줄어든다.

 

9. 예시 실행 결과

• 입력: 5 3
• 출력: 10
• 입력: 33 19
• 출력: 818809200

10. 결론

재귀와 메모이제이션을 활용한 조합수 계산은 시간 복잡도를 줄이고, 효율적인 계산을 가능하게 한다. 또한, 동적 계획법을 적용하여 중복 계산을 피하는 방식으로 성능을 개선할 수 있다.