[알고리즘] 조합과 순열, 그리고 점화식에 대해서

(00) :: Introduciton

대학교 학부 시절때 공부했던 이론 내용들을 리마인드 하기 위해서 작성된 게시글입니다.

정확하지 않은 내용이 포함되어 있는 경우, 댓글로 남겨주시면 수정할 수 있도록 하겠습니다.

이 게시글은 한 번에 완성되는 게시글이 아니며 내용을 지속적으로 추가할 예정입니다.

알고리즘을 학습하기 전에 수학에서의 조합과 순열이란 무엇인지 가볍게 정리해 보겠습니다.

순열의 사전적 정의는 순서를 고려한 n개의 숫자 중 r개를 뽑은 경우의 수를 말합니다.

수학적으로는 nPr 로 표현되고 공식은 nPr = n! / (n-r)! 입니다.

예) 5개 중 3개를 뽑는 경우의 수는 5P3 = 5! / (5-3)! = 5*4*3*2*1 / 2*1 = 60 입니다.

조합도 순열과 거의 유사합니다.

다만, 조합의 사전적 정의는 순서를 고려하지 않고 n개의 숫자 중 r개를 뽑은 경우의 수를 뜻합니다.

수학적으로는 nCr 로 표현되고 공식은 nCr = n! / (n-r)!r! 입니다.

예) 5개 중 3개를 뽑은 경우의 수는 5C3 = 5! / (5-3)!3! = 5*4*3*2*1 / 2*1*3*2*1 = 10 입니다.

즉, 순열과 조합의 차이점은 순서 고려 여부이며 순서를 고려한 경우 순열의 경우의 수에서 r!를 더 나눈 값인 것입니다.

조합에 대한 점화식을 세우고, 이를 일반식으로 구현해 보겠습니다.

지금 섹션에서는 이론만 다루고 있으므로 실제 언어로서의 구현은 생략하겠습니다.

조합에 대한 점화식을 세우기 위해 크게 3단계로 구분하여 접근해 보겠습니다.

#1 특정 문제를 가정하기

#2 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기

#3 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기

#1 : 5개의 데이터 중 3개를 고르는 경우의 수는 몇 개인가?

#2 : 5개의 데이터 중 4개의 데이터가 이미 선택된 상황에서 마지막 데이터를 선택할지 말지에 대해서 고려하기

깊게 생각해 보면 5개 중 4개의 데이터는 선택이 완료된 상태일 때, 마지막 데이터의 선택 여부에 따라 4개의 데이터 중 몇 개가 선택됐는지 알 수 있다.

그럼 아래 경우의 수를 한 번 살펴보자.

[마지막 데이터를 선택했을 때]

- 마지막 데이터가 선택됐다면 앞의 4개 데이터 중 2개의 데이터가 선택될 것이다. 그래야 5개 중 3개가 선택된 경우의 수에 해당할 수 있기 때문이다.

[마지막 데이터를 선택하지 않았을 때]

- 마지막 데이터가 선택되지 않았다면 앞의 4개 데이터에서 3개의 데이터가 선택되어야 한다. 그래야 5개 중 3개가 선택된 경우의 수에 해당할 수 있기 때문이다.

즉, 위 내용들을 정리해서 간단한 공식으로 정리해 보면 다음과 같다.

# 공식 : D[5][3] = D[4][2] + D[4][3]

#3 : #2에서 도출한 식을 일반 점화식으로 도출하기

위에서 도출된 공식을 일반 점화식으로 도출하면 다음과 같다.

좌측 항에 5와 3을 각각 i, j로 치환하고 우측 항을 계산해 주면 된다.

# 점화식 : D[i][j] = D[i-1][j-1] + D[i-1][j]

점화식 도출 과정에 대해서 위와 같이 정확하게 이해하고 있으면 DP 풀이 시에도 굉장히 도움되니 꼭 여러 번 복습하도록 합시다.

참고자료는 다음과 같습니다.

# -- Thanks to --
#1 Do it! 알고리즘 코딩테스트 (도서)