📍 조합
코딩 테스트에서 자주 출제되는 주제이다.
동적 계획법을 이해하는데 기초가 되는 매우 중요한 장이다.
조합 점화식 도출 방법에 대해 꼼꼼히 학습하는 것을 추천한다.
✅ 정의
조합(combination)은 nCr로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다.
순서를 고려하지 않는다.
✅ 조합의 점화식
1. 특정 문제를 가정하기
- 적당한 조합 문제를 가정한다.
- 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정해본다.
2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기
- 모든 부분 문제가 해결된 상황이라고 가정해본다.
- 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다.
- 모든 부분 문제가 해결된 상황이라고 가정하는 방법은 조합뿐 아니라 다이내믹 프로그래밍에서도 꼭 필요하므로 확실하게 이해해야 한다.
//5개 중 3개를 선택하는 경우의 수 점화식 D[5][3] = D[4][2] + D[4][3]
3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기
- 일반화된 점화식을 이용하면 조합과 관련된 모든 경우의 수를 쉽게 구할 수 있다.
// 조합 점화식 D[i][j] = D[i-1][j] + D[i-1][j-1]
📍 순열
✅ 정의
순열은 nPr로 표현하고, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 뜻한다.
728x90
'알고리즘 코딩테스트' 카테고리의 다른 글
[D-4] 14501 : 퇴사 준비하기(Java) (0) | 2025.02.24 |
---|---|
[D-5] 1722 : 순열의 순서(Java) (2) | 2025.02.23 |
[D-7] 최소 공통 조상 (0) | 2025.02.21 |
[D-8] 🤔세그먼트 트리 (0) | 2025.02.20 |
[D-9] 이진 트리 (0) | 2025.02.19 |