자바로 combination 구현하기
Today I Learned
자바로 Combination 구현하기
자바로 Combination(조합)을 구현하는 법에 대해 공부해보자.
우리가 알고있는 조합의 공식이다. n개중 순서상관없이 r개를 택할때의 경우의 수를 의미한다. 그렇다면 이 조합을 어떻게 구현할 수 있을까.
크게 3가지의 방법이있다. 그중 첫번째는 factorial 메소드를 구현해서 위의 공식대로 연산을 해주는 것이다.
재귀형식의 factorial 메소드를 만들어서 Combination을 구할 수 있다. 아래는 factorial 메소드와 예시로 Combination계산한 코드이다.
- 방법 1
위의 방식은 factorial 메소드를 구현해서 combination의 공식의 분모와 분자를 각각 계산하는 방식이다. combination을 한번에 계산할 수 있는 방법은 없을까. 물론 있다. 그 방법이 두 번째 방법이다.
그 방법을 설명하기 전에 두 가지 성질에 대해서 알고 넘어가야 한다.
[성질 1]
위의 공식을 다른방식으로 표현하면 아래와 같다.
이 표현법은 대학에 와서 처음 알게 되었다. 알고보니 지금까지 고등학교에서 배웠던 Combination 표현법은 오히려 잘 쓰지 않는 표현법이라고 한다. n과 r의 이항계수를 구한다고 하면 아래와 같이 표현할 수 있다.
이 점화식은 파스칼의 법칙 이라고 불린다.
[성질 2]
역시 다른 표현법으로 표현하면 아래와 같다.
n개중 0개를 택하거나 n개중 n개를 택하는 경우의 수는 1이라는 사실은 자명하다.
이제 위의 두 가지의 성질을 이용해서 combination 메소드를 아래와 같이 구현할 수 있다.
- 방법 2
위의 방법은 첫 번째 방법보다는 괜찮아보이지만 문제가 하나 있다. 바로 이미 계산한 결과에 대해서 다시한번 호출을 통해 계산을 한다는 것이 문제이다. 이런 중복계산을 피하기 위해서 동적계획법을 사용하겠다.
배열을 생성해서 이미 계산한 결과를 배열에 저장해준다. 그리고 이미 계산한 결과가 있다면 배열에서 저장된 값을 사용한다. 이를 코드로 구현하면 아래와 같다.
- 방법 3
이렇게 combination 구현 방법들에 대해서 공부해봤다. 이 포스팅이 내가 올리는 첫 번째 포스팅이다. 앞으로 공부한 것들을 꾸준히 올릴 예정이다.