[수학] 순열과 조합

예전 수학시간에 배웠던 개념인 순열(Permutation)과 조합(Combination)에 대해서 확인해보려고 한다. 생각보다 문제나 코테에 많이 나오는 것 같아서 정확하게 이해를 할 필요가 있었기 때문에 선수지식과, 인터넷 자료들을 취합해서 한 번 더 정리해봤다.

 

1. 순열(Permutation)

정의 : 순서가 부여된 임의의 집합 n개를 다른 순서로 뒤섞는 연산이다.

풀이 : 말 그대로 순서가 존재하는 열이다. 순서에 따라 결과가 달라지며, 중복을 허용할 수도 있고 없을 수도 있다. 중복허용을 하는 경우, 경우의 수는 n!과 같다. 

 

ex) 숫자배열 array = {1, 2, 3}가 있을 때, 2개의 숫자를 뽑아 중복허용여부에 따른 순열을 나열하기

 * 중복허용 : {1,2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}, {1,1}, {2,2}, {3,3}

 * 중복비허용 : {1,2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}, {1,1}, {2,2}, {3,3}

 

즉, 자바의 라이브러리 입장에서 봤을 때 중복허용된 순열은 list와 유사하고 중복비허용은 set과 유사하다. 하지만 둘 다 많이 사용한다고 생각되기 때문에 문제에 따라 중복허용여부를 반드시 체크해야할 것 같다.

 

 

 

2. 조합(Combination)

 

정의 : 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다.

풀의 : 순열 중 중복비허용된 순열에 순서를 고려하지 않는 숫자의 나열이다. 즉, 나열된 순서가 달라도 구성요소가 같으면 동일한 조합으로 인식이 되기 때문에 경우의 수가 더 적다.

 

ex) 숫자배열 array = {1, 2, 3}가 있을 때, 2개의 숫자를 뽑아 조합 나열하기

 * 중복허용 : {1,2}, {1,3}, {2,3}, {1,1}, {2,2}, {3,3}

 * 중복비허용 : {1,2}, {1,3}, {2,1}, {2,3}, {3,1}, {3,2}, {1,1}, {2,2}, {3,3}

 

즉, 자바의 라이브러리 입장에서 봤을 때 중복허용된 순열은 list와 유사하고 중복비허용은 set과 유사하다. 하지만 둘 다 많이 사용한다고 생각되기 때문에 문제에 따라 중복허용여부를 반드시 체크해야할 것 같다.