[0주차] 순열(permutation)과 조합(combination) - 조합편

📌  조합이란?

 

순서의 고려 없이 단순하게 선택만 하는 경우의 수, n 명중의 r명을 뽑기만 하는 방법의 수를 의미한다.

 

 

 

4C2를 구하는 공식은 순열을 구하는 공식보다는 조금 어렵다. 아이러니하게도 조합을 구하기 위해서는 순열을 먼저 구한 후, 제거시키면 된다. (저질러놓고 취소하는 방식) 즉 4C2 = 4P2/2!  이 된다.

 

 

📌 C++ 재귀함수에서의  조합

 

C++ 라이브러리에는 순열을 위한 라이브러리와 함수가 준비되어있지만 아쉽게도 조합을 위한 것은 준비되어 있지 않다. 순열과 마찬가지로 조합 또한 재귀 함수로 구현할 수 있고, 중첩 for문을 통해 구현도 가능하다.

 

코드는 다음과 같다. 

 

 

1) 호출: combi(0, 0, [])

• start = 0, depth = 0, result = []
• 반복문: for (int i = 0; i < 5; i++)
  • 즉, i = 0,1,2,3,4 순회

1-1) i = 0

• result.push_back(a[0]) → result = [1]
• 재귀 호출: combi(0+1, 0+1, [1]) = combi(1, 1, [1])

---

2) 호출: combi(1, 1, [1])

• start = 1, depth = 1, result = [1]
• 반복문: for (int i = 1; i < 5; i++)
  • 즉, i = 1,2,3,4

2-1) i = 1

• result.push_back(a[1]) → result = [1, 2]
• 재귀 호출: combi(2, 2, [1,2])

---

3) 호출: combi(2, 2, [1,2])

• start = 2, depth = 2, result = [1,2]
• 반복문: i = 2,3,4

3-1) i = 2

• result.push_back(a[2]) → result = [1,2,3]
• 재귀 호출: combi(3, 3, [1,2,3])

---

4) 호출: combi(3, 3, [1,2,3])

• depth = 3, k = 3 → 기저 조건 충족
  • 출력: 1 2 3
• 반환 → 복귀

---

5) 복귀: combi(2, 2, [1,2,3])

• 돌아와서 result.pop_back() → result = [1,2]
• 다음 i = 3로 진행

3-2) i = 3

• result.push_back(a[3]) → result = [1,2,4]
• 재귀 호출: combi(4, 3, [1,2,4])

---

6) 호출: combi(4, 3, [1,2,4])

• depth = 3 → 기저 조건
  • 출력: 1 2 4
• 반환

---

7) 복귀: combi(2,2, [1,2,4])

• result.pop_back() → result = [1,2]
• 다음 i = 4

3-3) i = 4

• result.push_back(a[4]) → result = [1,2,5]
• 재귀 호출: combi(5, 3, [1,2,5])

---

8) 호출: combi(5, 3, [1,2,5])

• depth = 3 → 기저 조건
  • 출력: 1 2 5
• 반환

---

9) 복귀: combi(2,2, [1,2,5])

• result.pop_back() → result = [1,2]
• 반복문 i=2,3,4 끝
• 반환

---

10) 복귀: combi(1,1,[1,2])

• result.pop_back() → result = [1]
• 다음 i = 2

2-2) i = 2

• result.push_back(a[2]) → result = [1,3]
• 재귀 호출: combi(3, 2, [1,3])

---

11) 호출: combi(3,2,[1,3])

• start = 3, depth = 2, result = [1,3]
• 반복문: i = 3,4

11-1) i = 3

• result.push_back(a[3]) → result = [1,3,4]
• 재귀 호출: combi(4, 3, [1,3,4])

---

12) 호출: combi(4,3,[1,3,4])

• depth = 3 → 기저 조건
  • 출력: 1 3 4
• 반환

---

13) 복귀: combi(3,2,[1,3,4])

• result.pop_back() → [1,3]
• 다음 i = 4

11-2) i = 4

• result.push_back(a[4]) → [1,3,5]
• 재귀 호출: combi(5,3,[1,3,5])

---

14) 호출: combi(5,3,[1,3,5])

• depth=3 → 기저 조건
  • 출력: 1 3 5
• 반환

---

15) 복귀: combi(3,2,[1,3,5])

• result.pop_back() → [1,3]
• i=4 끝
• 반환

---

16) 복귀: combi(1,1,[1,3])

• result.pop_back() → [1]
• 다음 i = 3

2-3) i = 3

• result.push_back(a[3]) → [1,4]
• 재귀 호출: combi(4,2,[1,4])

---

17) 호출: combi(4,2,[1,4])

• start=4, depth=2, result=[1,4]
• 반복문: i=4

17-1) i=4

• result.push_back(a[4]) → [1,4,5]
• 재귀 호출: combi(5,3,[1,4,5])

---

18) 호출: combi(5,3,[1,4,5])

• depth=3 → 기저 조건
  • 출력: 1 4 5
• 반환

---

19) 복귀: combi(4,2,[1,4,5])

• result.pop_back() → [1,4]
• i=4 종료
• 반환

---

20) 복귀: combi(1,1,[1,4])

• result.pop_back() → [1]
• 다음 i = 4

2-4) i=4

• result.push_back(a[4]) → [1,5]
• 재귀 호출: combi(5,2,[1,5])

---

21) 호출: combi(5,2,[1,5])

• start=5, depth=2
• 반복문: for (int i=5; i<5; i++) → 실행 안 됨(i=5 >=5)
• 반환

---

22) 복귀: combi(1,1,[1,5])

• result.pop_back() → [1]
• i=4 끝
• 반환

---

23) 복귀: combi(0,0,[1])

• result.pop_back() → []
• 다음 i = 1

이제 i=1 (여기는 맨 처음 combi(0,0,[])의 반복문)

1-2) i = 1

• result.push_back(a[1]) → [2]
• 재귀 호출: combi(2,1,[2])

(이후 흐름은 위와 비슷한 패턴으로 반복)

 

 

📌 C++ 반복문에서의  조합

 

반복문에서의 조합은 훨씬 구현이 간편하다. 3개 이하의 원소를 구하는 문제에서는 반복문으로 풀 것을 권유 받았다. 집합의 크기는 전과 같이 5개이며 조합하려는 원소 역시 3개로 전과 같다. 

 

 

 

코드를 보면 대충 눈치 채겠지만 이차원 배열, 3차원 배열을 출력하는 형식과 같다. 같은 맥락으로 만약에 2개의 원소를 출력하고 싶다면 

for문이 훨씬 구현 면에서 쉽지만  속도 면에서 아쉬움이 있으니 재귀 함수는 꼭 잊지 말자. 

 

 

📌 Pseudo Code

 

조합 : 
1) 기저사례 : 깊이가 조합하려는 수가 같다면 -> if(depth == k) 
2) 배열의 길이 시작부터 n 만큼 반복 -> for( int i = start; i < n; i++) 
2-1) result 배열에 원소 추가 -> result.push_back(a[i])
2-2)  재귀함수 호출 -> combi( i + 1 , depth + 1 , result); 
2-3) 원상 복귀 -> result.pop_back();