이항계수, 동적계획법

이항계수.. 고등학교 수학에서도 어려웠는데

백준 문제에서 나왔을때 뜨억!! 하고 놀랐다

 

굳어버린 머리를 일깨워서 다시 정리해보면

이항정리가 어려웠던 것 같기도 하고..? ..??

아무튼 이항계수는 집합에서 원소를 선택하는 경우의 수이다. 

이항계수는 다음과 같은 특징을 가진다.

• 순서가 중요하지 않음
• 중복 선택 불가
• 팩토리얼을 이용하여 계산

 

 

프로그래밍 사용 예시

확률 계산	사건이 일어날 확률 계산 ex) 주사위를 던져 3번 이상 5가 나올 확률 계산
통계 분석	특정 조건을 만족하는 데이터 선택, 가능한 조합의 수 계산
동적계획법	중복 계산을 피하기 위해 이항 계수를 미리 사용하여 값을 미리 계산한다

 

동적계획법

복잡한 문제를 간단한 하위 문제로 나누어 풀고 그 결과를 저장해 동일한 하위문제에 재활용하는 알고리즘 설계 기법이다.

최적화 문제나 최단 경로 문제를 푸는데 사용된다.

 

주요 특징

1. 메모이제이션

계산한 결과를 배열이나 다른 자료구조에 저장에 두었다가 필요할 때 가져와 사용한다. 

이를 통해 중복 계산을 피하고 실행 시간을 단축시킨다.

 

2. 최적 부분 구조

큰 문제의 최적해를 그 하위 문제들의 최적해를 합친 것으로 구성한다. 이 식이 충족될 때 까지

동적 계획법을 적용시킨다.

 

3. 점화식

문제를 작은 하위 문제로 분할하고 하위 문제들 간의 관계를 수식으로 표현한다.

동적 계획법에서는 점화식을 사용하여 문제를 해결한다.

 

자바 코드 예시

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

public class BinomialCoefficientExample {

    // 정수 n의 팩토리얼 계산 함수
    public static long factorial(int n) {
        if (n == 0 || n == 1) {
            return 1; // 0 또는 1의 팩토리얼은 1이므로 바로 반환
        }
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result *= i; // 2부터 n까지의 곱을 계산하여 팩토리얼 구함
        }
        return result; // 결과 반환
    }

    // 이항 계수 계산 함수
    public static long binomialCoefficient(int n, int k) {
        if (k < 0 || k > n) {
            return 0; // k가 범위를 벗어나면 계산 불가능하므로 0 반환
        }
        // n! / (k! * (n-k)!)
        long numerator = factorial(n); // 분자 계산: n!
        long denominator = factorial(k) * factorial(n - k); // 분모 계산: k! * (n-k)!
        return numerator / denominator; // 이항 계수 반환
    }

    public static void main(String[] args) throws IOException {
        // BufferedReader를 사용하여 입력을 받음
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //n과 k를 입력받음
        int n = Integer.parseInt(br.readLine());
        int k = Integer.parseInt(br.readLine());

        // 이항 계수 계산
        long result = binomialCoefficient(n, k);
        
        System.out.println(result);
        br.close();
    }
}