[06강] 순열 알고리즘

---

안녕하세요 Gliver 입니다.

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

 

목차

1. 순열 알고리즘
2. 실제 문제에서 순열 알고리즘

 

'순열(Permutation)과 조합(Combination)의 차이점'은 이전 글(조합 알고리즘)에서 설명했기 때문에 생략하겠습니다.

 

 

순열 알고리즘

순열은 수식으로 나타내면 nPr 입니다.

즉, 순열의 수식은 전체 원소의 개수 n 과 나열할 원소의 개수 r 로 구성되어 있습니다.

 

순열 알고리즘

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

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

 

순열 알고리즘은 원소 n개 중에서 r개를 나열하는 모든 경우를 살펴보는 것이므로,

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

 

조합과 다르게, 순열의 경우는 순서에 상관있게 선택해야 하므로 원소의 사용 여부를 나타내는 check 배열이 필요함.

 

10개의 원소 중에서 5개를 나열하는 모든 경우를 살펴보는 코드를 5중 for문을 써도 되지만, (이전 글 참조)

일반화를 위해 다중 for문이 돌아가는 원리를 재귀함수를 이용해서 구현해보겠습니다.

 

 

 

조합 알고리즘과의 차이점

조합 알고리즘은 순서에 상관 없으므로 순서를 정해놓고 개수를 뽑았습니다.

반면, 순열 알고리즘은 순서에 상관있게 선택해야 하므로 모든 경우를 살펴보도록 구현해야 합니다.

조합에서 for문은 i=index 로 시작하지만, 순열에서 for문은 i=0으로 시작하므로 모든 경우를 살펴보는 거임.

 

모든 경우를 살펴보는 대신에, 원소가 중복되어 선택되는 것을 방지하기 위해 check 배열을 이용했습니다.

 

다음은 위에서 살펴본 순열 알고리즘을 돌아가도록 작성한 코드입니다. (R=3인 경우)

 

 

 

위 코드는 N개의 원소 중에서 R개를 나열하는 모든 경우를 살펴보는 코드입니다.
N, R, list, check 를 적절하게 바꾸어 사용할 수 있음.

 

 

 

실제 문제에서 순열 알고리즘

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

 

순열 알고리즘도 조합 알고리즘과 비슷하게, 보조적인 알고리즘으로 많이 쓰입니다.

 

참고로, 순열 알고리즘을 지원하는 라이브러리인 permuation 함수가 내장되어 있는 언어도 있습니다.

C++에는 next_permutation, Python에는 permutations 함수가 존재함.

 

[관련 문제]

백준 : 모든 순열 (10974번)

 

 

 

---

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

 

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