자료구조 여름방학 3주차

조합

조합 자체로 코딩테스트에 많이 등장함

점화식, 동적 계획법을 이해하는데 기초가 되는 내용임

 

순열: n개의 숫자에서 r개를 뽑아 나열하는 경우의 .

조합: 순열과 다르게 순서를 고려하지 않음. 분모에 추가된 r!부분은 순서를 제거하는 역할.

 

 

조합의 점화식

1. 특정 문제 가정

    5개중에 3개 선택

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

    5를 선택했을 때->앞에서 2개의 수가 선택된 상황 4C2

    5를 선택하지 않음-> 앞에서 3개의 수가 선택된 상황 4C3

        따라서 5C3 = 4C3+4C2

3. 일반화 점화식 도출

 

 

백준 11051 

이항계수: 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.