1. 문제 정리 – 경우의 수 구하기
n개의 항목 중에서r개의 항목을 선택하는 문제- 순서는 상관없음
- 중복 없이 선택해야 함
재귀 함수를 이용해경우의 수를 계산- 재귀 함수는 큰 문제를 작은 문제로 나누어 반복적으로 호출하면서 풀어내는 방식
2. 예제 코드
function combination(n, r) {
if (r === 0 || n === r) return 1; // 종료 조건
return combination(n - 1, r - 1) + combination(n - 1, r);
}
// 예제 실행
console.log(combination(3, 2)); // 출력: 3
3. 목적
- 코드의 목적은 n개의 항목(전체 구슬) 중 r개의 항목(나누어 줄 구글)을 선택하는 경우의 수를 재귀적으로 계산하는 것
- combination(n, r)은
n개의 항목 중r개를 선택하는 조합의 수를 계산해 반환
4. 코드의 전체적인 흐름과 동작 원리
1) 큰 문제를 작은 문제로 나누기
- 3개의 구슬 A, B, C 중에서 2개를 고르는 경우
👉🏻 항목을 포함하거나 포함하지 않는 두 가지
1. A를 포함하는 경우
남은 구슬(B, C) 중에서 1개를 더 선택
→ combination(2, 1)
2. A를 포함하지 않는 경우
남은 구슬(B, C) 중에서 2개를 선택
→ combination(2, 2)
이렇게 문제를 작은 문제들로 쪼개서 해결
2) 종료 조건: 더 이상 쪼갤 필요가 없는 경우
재귀 함수는 종료 조건이 필요
종료 조건은 더 이상 선택할 필요가 없거나 모든 항목을 전부 선택해야 하는 경우입
r === 0
- 이미 필요한 만큼의 항목을 다 골랐으므로, 1가지 경우의 수로 간주하고 1을 반환
n === r
- 남아 있는 모든 항목을 전부 선택해야 하므로, 1가지 경우의 수로 간주하고 1을 반환
- 이 두 조건은 재귀 호출을 멈추고 하나의 유효한 조합을 찾았다는 의미로 1을 반환하는 것
5. 예제 실행 흐름
코드 흐름 이해
1) 종료 조건
if (share === 0 || balls === share) return 1;-
share === 0:
- 더 이상 선택할 구슬이 남아있지 않을 때
- 즉, 필요한 구슬을 모두 골랐을 때 1가지 유효한 조합이 완성된 것으로 간주
-
balls === share:
- 남은 구슬을 전부 골라야 할 때
- 이 경우에도 1가지 방법밖에 없기 때문에 1을 반환
2) 재귀 호출
return solution(balls - 1, share - 1) + solution(balls - 1, share);-
각 호출에서는 두 가지를 선택
현재 구슬을 포함하는 경우- 남은 구슬은 balls - 1개,
- 더 선택할 구슬은 share - 1개
호출:
solution(balls - 1, share - 1)현재 구슬을 포함하지 않는 경우- 남은 구슬은 balls - 1개,
- 선택할 구슬은 그대로 share개
호출:
solution(balls - 1, share)
combination(3, 2)
├─ combination(2, 1)
│ ├─ combination(1, 0) → 1 반환 (r === 0)
│ └─ combination(1, 1) → 1 반환 (n === r)
│ 결과: 1 + 1 = 2
└─ combination(2, 2) → 1 반환 (n === r)
최종 결과: 2 + 1 = 3설명:
combination(3, 2)이 호출되면:
- A를 포함해서 구슬 2개를 선택하는 경우: combination(2, 1)
- A를 포함하지 않고 구슬 2개를 선택하는 경우: combination(2, 2)
combination(2, 1)에서는:
- B를 선택해서 더 이상 구슬을 선택할 필요 없는 경우: combination(1, 0) → 1 반환
- B를 선택하지 않아서 C를 선택하는 경우: combination(1, 1) → 1 반환
결과: 1 + 1 = 2
combination(2, 2)에서는:
-
남은 구슬을 모두 선택해야 하므로 1을 반환
-
최종적으로 combination(3, 2)의 결과는:
2 + 1 = 3
