알고리즘 문제: 구슬 나누기
머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 각 구슬은 모두 다르게 생겼습니다. 머쓱이가 가지고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 반환하는 solution 함수를 완성해주세요.
제한사항
- 1 ≤ balls ≤ 30
- 1 ≤ share ≤ 30
- 구슬을 고르는 순서는 고려하지 않습니다.
share ≤ balls
입출력 예시
| balls | share | result |
|---|---|---|
| 3 | 2 | 3 |
| 5 | 3 | 10 |
입출력 예 설명
입출력 예 #1
서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다.
나의 풀이(재귀함수 사용, 다른사람 풀이 참고함)
class Solution {
public int solution(int balls, int share) {
return combination(balls, share);
}
public static int combination(int balls, int share){
if(balls == share || share == 0) return 1;
return combination((balls -1), (share -1)) + combination(balls - 1, share);
}
}풀이 설명
경우의 수를 구하는 공식은 다음과 같다. 입문편이라 그런지 풀이공식을 친절히 설명해주는 느낌:)
-
힌트를 참고하여 n!(팩토리얼)을 재귀적으로 구현하기로 했다.
-
팩토리얼(!)이란?
- 0! = 1 (0의 팩토리얼은 정의 상 1로 정의함)
- 1! = 1
- 2! = 2 × 1 = 2
- 3! = 3 × 2 × 1 = 6
- 4! = 4 × 3 × 2 × 1 = 24
- 5! = 5 × 4 × 3 × 2 × 1 = 120
-
팩토리얼을 재귀적으로 구현한 메서드
public int factorial(int n) {
// Base Case: 고르는 개수가 0이거나 모든 구슬을 다 고를 때
if (n == 0 || n == 1) {
return 1; // 경우의 수는 1
}
// 현재 구슬을 선택하거나 선택하지 않는 두 가지 경우를 더해주며 재귀 호출
return n * factorial(n - 1);
}
-
이건 사실 이해+암기 의 영역이다.
-
재귀함수에서는 Base Case가 중요한데, 이 메서드에서 사용된 종료조건은 share가 0이거나, 모든 구슬을 다 고를 때이다. 이 때 경우의 수는 1이다.왜냐하면 모든 구슬을 다 고르거나, 아무 구슬도 고르지 않는 경우는 하나씩 이기 때문이다.
-
그 외의 경우: 현재 구슬을 선택하거나 선택하지 않는 두 가지 경우를 더해주며 재귀적 호출을 한다.
balls 구슬 중 하나를 선택한 경우와 선택하지 않은 경우를 더해 모든 가능한 조합의 수를 계산한다.
근데 진짜루 진짜루 솔직히 재귀는 원리는 알겠는데 코드로 구현하라니 너무 어렵다. 베이스케이스를 설정하는 것 부터가 막힌다.
👩🏻💻 그래서 BaseCase의 조건을 설정하는 방법을 찾아봤다.
1. Base Case란?
베이스 케이스는 재귀 호출을 종료하고 결과를 반환하는 기준이 되는 조건이다.
2. Base Case설정이 중요한 이유?
- Base Case를 정확하게 설정하지 않으면 재귀함수를 무한으로 호출하여 스택오버플로우가 발생하는 문제가 생긴다.
3. Base Case를 설정하는 조건?
- 최소 입력 크기: 문제에서 처리해야 할 가장 작은 입력의 크기를 식별한다. 예를 들어, 팩토리얼에서 0!과 1!의 값은 각각 1로 정의되므로, n이 0 또는 1일 때 베이스 케이스를 설정할 수 있다.
- 함수의 입력이 어떤 상황에서 종료되어야 하는지를 정확히 파악하는 것이 중요하다.
- 예시로 주어진 구슬 문제에서 베이스 케이스는 "구슬을 고르는 개수가 0이거나 모든 구슬을 다 고를 때"이다.
- 왜냐하면, 구슬을 고르는 개수가 0일 때 더 이상 구슬을 선택하지 않는 경우의 수는 1가지다. 그리고 모든 구슬을 다 고를 때의 경우는 남은 구슬이 없을 때이다. 모든 구슬을 다 고른 경우도 하나의 경우의 수로 취급된다. 조합의 기본원칙이다. 예를 들어 5개의 구슬 중 5개를 고르는 경우는 1가지의 경우의 수라고 할 수 있다.
일단 여기까지 학습은 했는데 이해력이 부족한건지, 습득력이 부족한건지 재귀 진짜 어렵다!! 😂 숫자를 다 대입해 가면서 연습장을 끄적여봐야 할 듯.
