next_permutation => 직역하자면, 다음 수열이라는 의미입니다.
STL에서 제공하는 함수이며 vector, 배열로 구현이 가능합니다.
// 사전 순으로 정렬
1 3 4 2 의 다음 수열은 1 4 2 3 이 됩니다.
이때 1 4 2 3 을 만들기 위해서 4가지 단계를 거치는데
1. 어디까지가 감소 수열인가 찾기.
1 3 4 2 (감소 수열 4 2)
이떄 i = 2
2. i-1보다 작거나 같으며, 가장 뒤에 있는 수 j 를 찾기
1 3 4 2 (2보다 작으며, 가장 앞에 있는 수를 찾습니다)
이때 j = 3 (2를 가르킵니다)의 이전 인덱스 j = 2( 4를 가르킵니다)
3. 그 둘을 Swap 시킵니다.
1 4 3 2
4. i -1 이후로 뒤집습니다.
1 4 2 3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include<iostream> #include<vector> using namespace std; bool next_permutation(int *a, int n){ int i = n-1; // 뒤부터 시작 while(i > 0 && a[i] <= a[i-1]) // 어디까지가 감소수열인가?? i -= 1; if(i <= 0) // 전체가 감소수열이다. return false; // 다음 수열은 존재하지 않는다. int j = n-1; while(a[i-1] >= a[j]) j -= 1; swap(a[i-1],a[j]); // 찾은 수의 바로 앞 swap i-1 j = n - 1; // j는 마지막 while(i < j){ // i-1 이후로, swap해줌 swap(a[i],a[j]); i +=1; j -=1; } return true; } int main(){ int n; cin >> n; int *v = new int[n]; for(int i = 0; i < n; i++) v[i] = i+1; do{ for(int i = 0; i < n; i++) cout << v[i] << ' '; cout << '\n'; }while(next_permutation(v,n)); return 0; } |
C++의 STL에서 제공하는 함수도 존재합니다.
간단하게 사용하면 됩니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ vector<int> a; int n; cin >> n; for(int i = 0; i < n; i++){ int tmp; cin >> tmp; a.push_back(tmp); } do{ for(int i = 0; i < n; i++) cout << a[i]; cout << '\n'; }while(next_permutation(a.begin(), a.end())); return 0; } | cs |
※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.
'C_C++ 프로그래밍 > C_C++ 프로그래밍' 카테고리의 다른 글
[C++] 선택정렬(Selected Sort) (0) | 2019.04.01 |
---|---|
[C++] pair sort (0) | 2019.03.21 |
[C++] 2차원 동적 배열 생성 (0) | 2019.03.19 |
[Algorithm] C++ Bitmask란? (0) | 2019.03.17 |
댓글