[알고리즘] 순열과 조합

📚순열(Permutation)

- 순열은 서로 다른 n개의 원소 중 r개를 선택하여 일렬로 나열하는 것을 말합니다. 이 때, 같은 원소가 중복되지 않고, 순서가 중요합니다.

예를 들어, 3개의 원소 A, B, C 중에서 2개를 선택하여 만들 수 있는 순열은 AB, AC, BA, BC, CA, CB입니다.

 

 

- nPr : 서로 다른 n개에서 순서를 고려하여 r개를 뽑는 경우의 수를 의미합니다.

 

- 예를 들어 4P2일 경우 4! / (4-2)!  = 12 가지입니다.

 

1,2,3,4 중 2개를 뽑는 경우의 수를 나타내면 다음과 같습니다.

 

(1,2), (1,3), (1,4)   -> 3가지

(2,1), (2,3), (2,4)  -> 3가지

(3,1), (3,2), (3,4)  -> 3가지

(4,1), (4,2), (4,3)  -> 3가지

 

 

💡 Python에서 itertools 라이브러리의 permutations를 import하여 사용한 순열 구현 코드입니다.

 

모듈 사용한 순열코드

 

 

 

💡 다음 코드는 itertools 모듈을 사용하지 않고 구현한 순열 코드입니다.

 

모듈 사용안한 순열 코드

 

 

 

📚조합(Combination)

-서로 다른 n개의 원소 중 r개를 선택하는 것을 말합니다. 이 때, 같은 원소가 중복되지 않으며, 순서가 중요하지 않습니다.

예를 들어, 3개의 원소 A, B, C 중에서 2개를 선택하여 만들 수 있는 조합은 AB, AC, BC입니다.

- nCr : 서로 다른 n개에서 순서를 생각하지 않고 r개를 뽑는 경우의 수를 의미합니다.

 

- 예를 들어 4C2일 경우 4! / (4-2)!2!  = 6 가지입니다.

 

1,2,3,4 중 2개를 뽑는 경우의 수를 나타내면 다음과 같습니다.

 

(1,2), (1,3), (1,4) -> 3가지

(2,3), (2,4) -> 2가지

(3,4) -> 1가지

 

 

💡 Python에서 itertools 라이브러리의 permutations를 import하여 사용한 조합 구현 코드입니다.

 

모듈 사용한 조합 코드

 

💡 다음 코드는 itertools 모듈을 사용하지 않고 구현한 조합 코드입니다.

모듈 사용안한 조합 코드