[Do it! 알고리즘 코딩테스트 with C++] 8장. 조합

해당 게시물은 하루코딩님의 'Do it! 알고리즘 코딩테스트 with C++' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 8장. 조합

8-1. 조합

---

📌 8-1. 조합

* 조합
- nCr: n개의 숫자에서 r개를 뽑는 경우의 수
- nCr = n! / (n-r)! r!

* 순열
- nPr: n개의 숫자에서 r개를 뽑아 순서를 고려해 나열할 경우의 수
- nPr = n! / (n-r)!

* 조합 동작 원리
1. 특정 문제 가정
2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 고려 - ex. 5C3 = 4C3 + 4C2, 점화식으로 표현: D[5][3] = D[4][2] + D[4][3]
3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출 - D[i][j] = D[i - 1][j] + D[i - 1][j - 1]

---