2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/정보영재

순열,조합,중복 조합의 원리

원당컴퓨터학원 2018. 3. 21. 09:30


오늘은 정보올림피아드 2017년 초등 39번 문제(http://wondangcom.tistory.com/73) 풀이 도중에 중복조합이라는 것을 이해하지 못하는 학생이 있어서...


중복 조합이 무엇인지 살펴 볼까 합니다.


중복 조합을 살펴 보기 이전에 먼저 순열의 개념을 알고 넘어가면 쉬울것 같아요...


순열이란 순서가 있는 조합을 이야기 합니다.

예를 들어 1,2,3 이라는 세개의 숫자를 가지고 3자리 수를 만들수 있는 모든 조합의 갯수는 123 과 213 과 같이 순서가 있을때 서로 다른 값을 가지게 되므로 이것을 순서가 있는 조합, 즉 순열이라고 합니다.


이 순열을 구하는 계산 방식은 맨 첫자리에 3개가 올 수 있고 두번째는 첫번째에서 하나를 골랐기 때문에 하나를 뺀 2개 마지막은 3개에서 2개를 고른 상태이므로 1개 밖에 남지 않기 때문에 모든 순열의 갯수는 3 * 2 * 1 = 6가지가 됩니다.

 


위와 같이 맨 첫자리에서 1,2,3 을 선택하면 두번째 자리는 선택하고 남은 둘중 하나밖에는 선택 할 수 없다.


만약 1,2,3,4,5 의 5개의 숫자를 이용해서 3자리 숫자를 만드는 경우의 수는 5 * 4 * 3 = 60 가지 일것입니다.

이렇게 순열을 구하는 공식은 nPr = n! /(n-r)! (n 개 중에서 r개를 선택하는 경우) 으로 표현을 할 수 있습니다.

예) 5P3 = ( 5*4*3*2*1) / ( 2 * 1) = 5 * 4 * 3 의 원리 (5개의 숫자중에 3자리 숫자를 만드는 경우의 수)



이렇게 순서가 있는 조합을 순열이라고 하는데요...


다음과 같이 순서가 없는 경우를 조합이라고 합니다.

1번공,2번공,3번공,4번공,5번공 이 주머니에 들어 있을때 세개의 공을 꺼내는 경우의 수를 구하라 와 같이 3개의 공을 꺼내서 순서로 나열 하는 것이 아니라... 1,2,3 순서로 꺼냈든 3,2,1 순서로 꺼냈든 상관없이 1번공 2번공 3번공이 꺼내졌다는 똑같은 경우로 인식을 하는 것입니다.


이러한 경우는 5P3 과 같이 3개를 꺼내서 순서를 나열한 후에 꺼내어진 3개 중에 3개를 꺼내서 순서를 나열하는 3P3 = 3! 의 경우의 갯수로 나누는 조합과 동일합니다.

따라서 이러한 조합의 공식은 nCr = nPr/r! = n!/( (n-r)! * r!) 으로 표현할 수 있습니다.


중복조합은 

1번공,2번공,3번공,4번공,5번공의 갯수가 주머니 안에 무한개로 많이 있는 경우 3개를 꺼내서 순서 없이 나열하는 경우 입니다.

3개를 꺼내면 111 이 될수도 있고, 222,333,444,555 또는 112,113... 등과 같이 될수도 있습니다.



이때 보통 원과 막대기로 구분을 하는데요...

다음과 같이 3개의 공을 꺼내야 하므로 원을 3개를 그립니다.


이제 이 원 사이에 5그룹의 공을 뽑아서 넣어야 하므로 4개의 막대기를 그려 넣습니다.

1번공 | 2번공 | 3번공 | 4번공 | 5번공

이렇게 하면 막대기가 4개 입니다.


가령 111 과 같은 경우는 그림으로 표현하면 다음과 같습니다.

- 3개의 꺼낸 공이 1번그룹에 위치해 있는 모습


이와 같이 그리면 123 의 공을 꺼낸 경우는 다음과 같은 모습이 될것입니다.


이렇게 그림을 그려 보면 총 5개의 중복 가능한 공을 3개를 꺼내는 경우 5 -1 (막대 갯수) + 3 (꺼내는 갯수) 중에서 3개를 꺼내는 경우의 수와 동일합니다.


(5 - 1) + 3 C 3 과 동일한 가짓수가 됩니다.

이것을 식으로 표현하면 다음과 같습니다.

nHr = (n-1)+rCr = n+r-1Cr

이며 n은 중복 가능한 수이며 r은 뽑는 갯수를 뜻합니다.


조합에서는 3C7 과 같이 3개에서 7개를 뽑을 수 없지만 중복 조합에서는 3H7 과 같이 3개의 중복 데이터에서 7개를 뽑을수 있는 경우도 가능한것입니다.


이 글이 중복조합을 헷갈리는 분들에게 도움이 되었으면 좋겠다는 생각을 해 보게 되네요.^^








사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기