순열(재귀)

순열

순열(permutation)이란 서로 다른 n개의 원소에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말한다.

브루트포스 알고리즘에 많이 사용되기에 잘 익혀두는 것이 좋다.

algorithm에 기본으로 내장된 next_permutation이 있지만 이것을 사용하기에는 제약이 많기에 간단하게 직접 짜서 문제의 요구사항에 맞게 수정하는 것이 좋다.

#include <iostream>
using namespace std;
char arr[4] = {'1', '2', '3', '4'}, used[4], path[4];
void dfs(int level){ // 현재 몇 번째 자리까지 진행되었는지를 인자로 넘겨준다.
    if(level == 4) // 네 번째 자리까지 결정되면 출력하고 함수를 리턴한다.
    {
        cout << path<< '\n';
        return;
    }
    for(int i=0; i<4; i++){
        if(used[i] == 1) // 사용한 적 있는 수는 중복되지 않게 continue 한다.
            continue;
        
        used[i] = 1; // used 배열에 체크하고 path에 적어주고 다음 자릿수를 위해 level+1 을 해준다.
        path[level] = arr[i];
        dfs(level+1);
        used[i] = 0; // 함수가 리턴되었다면 현재 위치의 used 배열과 path 배열을 초기화한다.
        path[level] = 0;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    dfs(0);
    return 0;
}

결과

 

간단하게 순열을 생성해보았다.

순열을 생성하는 알고리즘을 짜기 위해서 재귀를 이용하였다.

 

 

코드에 보이는 것 처럼 used 배열을 사용하여 중복을 제거해주고 중복되지 않은 수는 path 배열에 넣어주어서 원하는 길이의 순열이 되었을 때 출력한다.

 

이 과정에서 배열이 int형이라면 for문 혹은 while을 통해 출력해야 하기에 1자리 수를 사용하였기에 char형으로 선언하여 문자열로 출력을 하였다.