next permutation

알고리듬 - Next Permutation

Permutation 관련 문제를 푸는데 더 빠른시간에 푼 코드를 확인해보니 Next Permutation(NP)을 사용하고 있었다. 특정 조건을 만족한다면 NP를 활용하는 것이 좋아보여서 이에 대한 내용을 작성하고자 한다. 다음 순열(Next Permutation) Next Permutation(이하 NP)은 순열을 순차적으로 탐색하는 알고리듬이다. 특징 재귀를 활용하지 않는다. 재귀를 활용한 순열 탐색보다 속도가 빠르다. 사전 순 정렬이 된 상태에서 탐색을 시작해야 온전히 모든 순열을 구할 수 있다. 특정 개수의 순열을 뽑을 수 없다. 동작 과정 NP의 동작 과정은 아래와 같다. 배열의 가장 오른쪽에서 시작해 왼쪽으로 가며 값이 작아지는 순간의 인덱스(Pivot)을 구한다. 배열의 가장 오른쪽에서 시..