조합의 수 구하기

순열과 조합..

학창시절 nPr이니 nCr이니 하며 수학시간에 열심히 배웠던 기억이 있다.

알고리즘을 공부하면서 다시 보려고 하니 까먹은 기억을 되살리려다보니 기억보다 기록을 해두자 라는 생각으로 정리하게 되었다.

먼저, 간단한 개념은 알고 있었다. 내가 이해가 잘안됬던 것은....

---

그렇다.. 조합에서 위와 같은 식이 어떻게 적용이 되는 것인지 바로 확 와닿지 않았다.

공부하다 보면서 아! 그렇구나 하며 다시 알게 되었고, 이를 까먹지 않기 위해 알기 쉽게 정리하려고 한다.

서론이 너무 길었던 것 같다.. 자 지금부터 예를 들어 설명해 보겠다.

---

여기 아래와 같이 6명의 사람이 있다.

면접을 보는 사람들이다.

총 6명의 사람이 면접을 보았고, 이 회사에서는 3명을 채용하고자 한다.

면접보는 6명의 사람들

 

• 먼저 조합의 개념을 간단히 짚어보면, 조합(Combination) - nCr 이런형태로 표현하게 되는데 n개중 r개를 뽑는데 순서에 상관없이 무작위로 뽑아낸다는 것이다.
• 위의 케이스를 예를 들어 설명하자면, 6명의 사람 중 적합한 3명의 인원을 채용하겠다 라는 뜻이다.

---

자 그러면 이어서 위의 식이 어떻게 성립하는지 예를 들어 설명하겠다.

• 면접이 다 끝나고나서 면접관들은 서로 어떤사람이 맘에 드는지 얘기를 한다.
• 여기서 3번 사람을 면접관들이 다 공통적으로 마음에 들어서 이사람은 뽑자 vs 3번사람은 너무 별로인데요? 하면서 제외하고 가정하는 케이스로 생각해보자

  ---

먼저 3번 사람이 면접관들이 다 공통적으로 마음에 들 경우

• 회사에서는 3명의 인원을 채용해야 함으로 3번 지원자를 제외한 나머지 5명중에서 2명을 더 추가적으로 합격시켜야한다.
• 이것은 5명 중에 2명이므로 5 Combination 2 이다.

3번사람은 너무 별로인데요? 일 경우

• 회사에서는 3명의 인원을 채용해야하는데 3번은 별로니 제외하고 남은 사람중에서 3명을 뽑기로 한다.
• 이것은 5명 중에서 3명을  채용해야 하는 것임으로 5 Combination 3 이다.

 

결론적으로 회사에서 봤을 때 6명의 면접본 인원 중에서 3명을 뽑는 경우의 수는 

3번이 포함되는 경우의 수와 3번이 제외되고 다시 뽑는 경우의 수 합과 같다. 이것을 나타내주는 식이 위에서 선언한 식의 뜻이다.

 

코드로 구현하면 아래와 같다. (메모이제이션을 포함하였다)

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

// 조합의 경우수 구하기
public class infCombination {
    int [][] combi = new int[35][35];
    public int DFS(int n, int r){
        // 이미 재귀가 돌아서 구한 값이냐?
        // 구한값이라면 재귀돌지말고 그 값을 가져와라
        if(combi[n][r] > 0) return combi[n][r];
        if(n == r || r==0) return 1;
        else return combi[n][r] = DFS(n-1, r-1) + DFS(n-1, r);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        infCombination T = new infCombination();
        System.out.println(T.DFS(n, r));
    }
}