[Algorithm] 집합·조합론·기초 수식

순열과 조합

구분	기호	정의
순열	nPr	서로 다른 n개에서 r개를 뽑아 순서 있게 늘어놓는 것
중복순열	nΠr	서로 다른 n개에서 중복을 허락하여 r개를 택해 순서 있게 늘어놓는 것
조합	nCr	서로 다른 n개에서 순서 없이 r개를 뽑는 것
중복조합	nHr	서로 다른 n개에서 중복을 허락하여 r개를 선택하는 것

점화식과 메모이제이션

점화식을 세우는 문제는 90% 이상 메모이제이션을 사용한다. 작은 입력에 대한 값(예: 9, 99, 9999 같은 경계값)을 미리 채워두고 큰 값을 이로부터 계산한다.

기초 수열

• 등차수열 — 이웃한 항의 차가 일정

• 등비수열 — 이웃한 항의 비가 일정
• 계차수열 — 이웃한 항의 차로 이루어진 수열(차가 다시 수열을 이룸)