[알고리즘] 3-1. 조합 : dim[i][j] = dim[i-1][j] + dim[i-1][j-1]

1. 순열과 조합

nPr : n개의 숫자 중 r개를 순서를 고려해 나열하는 경우의수

nCr  : n개의 숫자에서 r개를 순서없이 뽑는 경우의 수

 

(1) 순열

: 5개 중 2개를 골라 순서대로 나열하는 경우의 수

[ n개 중 r개를 골라 순서대로 나열하는 경우의 수 = n! / (n-r)!]

-> 5! / (5 - 2)!

-> 5! / 3! = 5 *4

: 순서가 존재하므로, 뽑힌 숫자가 달라도 뽑는 순서가 다르면 다르다

 

(2) 조합

: 5개 중 2개를 뽑는 경우의 수

[ n개 중 r개를 뽑는 경우의 수 = n! / (n-r)! * r!]

-> 5! / (5 - 2)! * 2!

-> 5! / 3! = 5 *4 / 2

: 순서가 존재하지 않으므로, 뽑힌 숫자가 같으면 같으므로, r!를 나눈다 [r!만큼 같은 경우를 제외해야하므로]

 

 

# 조합의 점화식 [알고리즘에서 수학 공식을 표현하는 방법]

1. 특정 문제를 가정
   : 5개의 데이터에서 3개를 선택하는 조합의 경우의 수
   -> 1, 2, 3, 4, 5
2. 이미 선택이 완료된 데이터라고 가정하고, 경우의 수 계산
   : 5개 데이터 중 4개가 이미 선택된 데이터이고, 마지막 데이터 선택 여부에 따른 경우의 수
   
   i) 5를 선택하는 경우          : 선택이 완료된 데이터 중 2개를 선택하는 경우의 수 + = 5개를 3개를 선택하는 경우의 수
   ii) 5를 선택하지 않는 경우 : 선택이 완료된 데이터 중 3개를 선택하는 경우의 수 + = 5개를 3개를 선택하는 경우의 수
   i) + ii)
   = 선택이 완료된 데이터 중 2개를 선택하는 경우의 수 +  3개를 선택하는 경우의 수= 5개를 3개를 선택하는 경우의 수
   
   # 5개 중 3개를 선택하는 경우의 수 점화식
   dim[5][3] = dim[4][2] + dim[4][3]
   -> 5개 중 3개의 경우의 수를 구하는 점화식 (X)
   -> 조합과 관련된 점화식 (O)
3. 가정으로 도출한 점화식을 통해서 일반 점화식 도출
   # 조합 점화식
   dim[i][j] = dim[i-1][j] + dim[i-1][j-1]
   
   

---

문제 076. 이항계수 구하기1

문제 077. 이항계수 구하기2

문제 078. 부녀회장이 될 테야

문제 079. 다리 놓기

문제 080. 조약돌 꺼내기

문제 081. 순열의 순서 구하기

문제 082. 사전 찾기

문제 083. 선물 전달하기