[05강] 조합 알고리즘

---

안녕하세요 Gliver 입니다.

이번 글에서는 조합 알고리즘에 대해 알아보겠습니다.

 

목차

1. 조합 알고리즘
2. 실제 문제에서 조합 알고리즘

 

 

조합과 순열

먼저, 조합(Combination)과 순열(Permutation)의 차이점에 대해 간단히 짚고 넘어가겠습니다.

 

조합과 순열의 가장 큰 차이점은 순서라는 개념의 존재 여부입니다.

조합은 순서라는 개념이 존재 x, 순열은 순서라는 개념이 존재 o

 

이해가 안 되시는 분들은 '더보기'를 눌러 예시를 참고해주시기 바랍니다.

 

[예시]
숫자 카드 1, 2, 3이 있습니다.
이때 카드 3장을 가지고 만들 수 있는 순열과 조합은 다음과 같습니다.

ㆍ 조합의 경우 : 조합에는 순서라는 개념이 존재하지 않으므로, {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 을 모두 "1, 2, 3 으로 이루어진 경우" 로 취급하기 때문에 총 1가지 경우가 존재합니다.

ㆍ 순열의 경우 : 순열에는 순서라는 개념이 존재하므로, {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} 을 모두 다른 경우로 취급하기 때문에 총 6가지 경우가 존재합니다.

 

 

 

 

조합 알고리즘

조합은 수식으로 나타내면 nCr 입니다.

즉, 조합의 수식은 전체 원소의 개수 n 과 뽑을 원소의 개수 r 로 구성되어 있습니다.

 

조합 알고리즘

조합 알고리즘은 n개의 원소 중에서 r개를 뽑는 모든 경우에 대해 살펴보는 알고리즘입니다.

예를 들어, 1~11의 숫자가 있고 이 중에서 2개를 뽑는 경우라고 하면 $_{11}\mathrm{C}_{2}(55)$가지 경우에 대해 살펴보는 거임.

 

조합 알고리즘은 원소 n개 중에서 r개를 뽑는 모든 경우를 살펴보는 것이므로,

원소 n개가 들어 있는 배열에 대해 r개의 for문을 통해 원소를 선택하는 과정을 구현하면 됩니다.

 

이해를 돕기 위해서 예시와 그에 대한 간략한 코드를 첨부하겠습니다.

 

ㆍ 1~11의 11개의 원소 중에서 1개를 선택하는 모든 경우를 살펴보는 코드

 

 

 

ㆍ 1~11의 11개의 원소 중에서 2개를 선택하는 모든 경우를 살펴보는 코드

 

 

 

ㆍ 1~11의 11개의 원소 중에서 3개를 선택하는 모든 경우를 살펴보는 코드

 

 

 

 

여기서 핵심은 r개를 고르는 모든 경우를 살펴보는 코드를 짤 때 r개의 for문이 필요하다는 것입니다.

(만약, 배열의 원소를 기준으로 조합 알고리즘을 사용하고자 한다면 인덱스를 기준으로 접근하시면 됩니다)

 

만약, 10개의 원소 중에서 5개를 고르는 모든 경우를 살펴보는 코드는 어떻게 짜야할까요?

5중 for문을 써도 되지만, 일반화를 위해 재귀함수를 이용해서 간략하게 구현해봅시다.

 

 

다중 for문을 재귀함수 형태로 바꿨다고 생각하시면 이해하기 쉽습니다.

Combination() 함수에서 level은 현재 선택한 원소의 개수를 의미하고, index는 '이전 원소의 인덱스+1'이라고 생각하시면 됩니다.

index는 다중 for문에서의 j = i+1 과정을 구현하기 위한 변수임.

 

다음은 위의 코드가 돌아가도록 짠 전체 코드입니다.

 

 

위 코드는 N개의 원소 중에서 R개를 고르는 모든 경우를 살펴보는 코드입니다.

N, R, list 를 적절하게 바꾸어 사용할 수 있음.

 

 

 

실제 문제에서 조합 알고리즘

실제 문제에서 조합 알고리즘은 조합을 구현해야 할 때 쓰면 됩니다.

조합 알고리즘 그 자체로도 많이 쓰이고, 보조적으로도 많이 쓰이는 알고리즘이라 기본적으로 알아두면 좋음.

 

재귀함수를 이용해 조합을 구현하는 것 자체가 쉬운 과정은 아니기에,

코테에서 조합 알고리즘을 쓴다면 그 문제는 난이도가 중, 상 정도 될 것입니다.

 

제 경험상, 조합에 관한 문제는 위의 코드에서 조합을 처리하는 구문인 if (level == R) 부분만 문제에 따라 다를 뿐,

나머지 과정은 비슷했기 때문에 위의 재귀함수로 구현된 코드만 잘 숙지하셔도 충분할 거 같습니다.

 

[관련 문제]

백준 : 로또 (6603번)

백준 : 암호 만들기 (1759번)

 

 

 

---

궁금한 점이나 코멘트는 댓글로 남겨주세요!

 

• 알고리즘 공부법 : https://gliver.tistory.com/6
• 알고리즘 목차 : https://gliver.tistory.com/7