조합이란?
- 조합은 위처럼 표현하고, n개의 숫자 r개를 뽑는 경우의 수를 뜻함
- 순열은 위처럼 표현하고 n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 뜻함
- 조합과 순열의 차이는 순서의 고려 유무
순열과 조합의 핵심 이론
- 순열의 수학적 공식
- 조합의 수학적 공식
- 순열과 매우 비슷하며 분모에 r!만 추가됨(r! : 순서가 다른 경우의 수를 제거하는 역할)
예시
- 적당한 조합 문제를 가정
1. 특정 문제 가정
- 5개의 데이터에서 3개를 선택한는 조합의 경우의 수를 푸는 문제로 가정
2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각
- 모든 부분 문제가 해결된 상황이라고 가정(5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정)
- 마지막 데이터의 선택 여부에 따른 경우의 수를 계산
- 만약 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서 2개를 선택
- 만약 마지막 데이터를 포함하지 않고 총 3개의 데이터를 선택하려면 이전 데이터 4개 중 3개를 선택
- 2가지 경우의 수를 합치면 데이터 5개중 3개를 서낵하는 경우의 수가 나옴
- 5개중 3개를 선택하는 경우의 점화식 : D[5][3] = D[4][2] + D[4][3]
3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출
조합 점화식 : D[i][j] = D[i-1][j] + D[i - 1][j - 1]
study