알고리즘 6 ] 순열 조합

순열

하나의 배열을 이용해서 전체 조합을 만들어 문제를 풀어야 하는 경우 순열 문제로 생각하고 푼다.

문제는 실행복잡도가 N의 N승으로 올라가버리기 때문에 너무 큰 배열(8을 넘어가는)인 경우에는 사용할 수 없다.

 

원리

- 재귀적으로 자리수를 하나씩 고정(k) => 해당 자리에 배열을 하나씩 대입(i) => 재귀로 다음 자리부터 구하도록 넘김

- 자리에 하나씩 넣을 때에는 여러가지 경우의 수가 나와야 하기 때문에 교환하는 형태로 구한다.

- 해당 재귀가 끝나면서 반대로 돌아올 때에는 다음 재귀에 영향을 주지 않기 위해 원래의 배열 형태로 원복시킨다.

 

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
void permutations(vector<int> arr, const int k, const int m);
void solution(vector<int> arr);
 
int main()
{
    vector<int> arr;
    arr.push_back(1);
    arr.push_back(5);
    arr.push_back(6);
    arr.push_back(8);
    solution(arr);
 
    return 0;
}
 
void solution(vector<int> arr)
{
    permutations(arr, 0, arr.size());
}
 
void permutations(vector<int> arr, const int k, const int m)
{
    int i;
    if (k == m)
    {
        for (i = 0; i < m; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
    else
    {
        // 재귀로 돌면서 특정 자리의 수에 모든 수를 대입해서 경우의 수를 만들기
        for (i = k; i < m; i++)
        {
            int tmp = arr[k]; arr[k] = arr[i]; arr[i] = tmp; // 순서 바꾸고
            permutations(arr, k + 1, m); // 다음 한칸으로 바꾸고 재귀
            tmp = arr[k]; arr[k] = arr[i]; arr[i] = tmp; // 원래대로
        }
    }
}