[알고리즘] 조합

알고리즘

[알고리즘] 조합

라임온조 2023. 5. 15. 11:45

1. 개념

n개 중 r개를 선택하는 경우의 수를 뜻한다. 이때, 선택한 것들의 순서가 달라도 같은 것이라고 처리한다. 예를 들어 1 2 3 4 5 중 2개를 뽑았을 때 1 2 를 뽑은 것과 2 1 을 뽑은 것을 같은 것이라고 보는 것이다.

2. 공식

3. 점화식

1) 조합 공식보다 점화식을 사용하면 좋은 이유

조합 공식의 경우 팩토리얼 연산을 사용해야 하는데 큰 수의 경우 계산 비용이 높다.
팩토리얼 연산을 재귀로 구현할 경우 스택 오버 플로우 문제가 발생할 수 있다.
점화식을 사용하면 반복 계산을 피할 수 있다. 이전에 계산된 것을 동적 계획법의 방식으로 사용하기 때문에 계산 비용을 줄일 수 있고 더 효율적으로 접근할 수 있다.

2) 점화식 개념

점화식을 세울 때는 모든 부분 문제가 해결된 상황이라고 가정해야 한다. 즉, 우리는 결과를 내기 전까지 딱 한 번의 실행만 하면 되는 상황인 것이다.

5개 중 3개를 뽑는 상황인데 4개가 이미 선택이 완료된 데이터라고 가정하자. 우리는 마지막 하나에 대한 선택을 해서 결과를 내야 한다. 이때는 2가지 상황이 있다.

마지막 하나를 선택한다. 이때는 이미 선택된 4개 중 2개만 선택이 되어 있어야 한다.

마지막 하나를 선택하지 않는다. 이때는 이미 선택된 4개 중 3개가 선택이 되어 있어야 한다.

이를 식으로 표현하면 다음과 같다.

D[i][j] = D[i-1][j] + D[i-1][j-1] (D[i][j]는 i개 중 j개를 선택하는 조합 경우의 수를 의미한다)

4. 코드

int[][] D = new int[N+1][N+1];
for(int i = 0; i<=N; i++){
    D[i][1] = i;
    D[i][0] = 1;
    D[i][i] = 1;
}
for(int i = 2; i<=N; i++){
    for(int j = 1; j<i; j++){
        D[i][j] = D[i-1][j] + D[i-1][j-1];
    }
}