순열의 모든것 풀어봅시다

순열은 무엇일까요?  재귀를 이용하여 순열을 뽑기 전에 순열은 어떤 모양을 가지고 있는지 

알아야 함으로 어떻게 생겼는지 먼저 알아봅시다.

 순열은  Permutation 으로 nPr n개의 나열된 숫자에서 r개를 뽑는 것을 말합니다.

예를 들어 1, 2, 3, 4 의 숫자에서 2개의 숫자를 뽑는다면 경우는 

위와 같이 같은 숫자를 가진 집합이 존재하면서 뽑히게 됩니다. 1 2와 2 1이 같은 경우로 치지 않고 뽑히는 경우 

달라진다면 순열로 뽑는것이 옳고 1 2와 2 1이 같은 것이라면 조합으로 뽑아야 시간을 줄일 수 있겠죠?

조합은 위에 말한것처럼 순열의 반의 가짓수를 뽑는다고 생각하시면 좀 더 이해하기 쉬울 것 같습니다.

ㅇ 조합에 대한 이야기는 다음 블로그 글을 참조하시면 됩니다.

 

 

 

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

#include<stdio.h>
#include<vector>
using namespace std;
int N, M;
const int DSIZE = 9;
const int chkSIZE = 9;
int D[DSIZE];
int chk[chkSIZE];
void dfs(int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++) printf("%d ", D[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (chk[i] == 0) {
            chk[i] = 1;
            D[idx] = i;
            dfs(idx + 1);
            D[idx] = 0;
            chk[i] = 0;
        }
    }
}
void init() {
    scanf("%d %d", &N, &M);
}
int main(void) {
    init();
    dfs(0);
    return 0;
}

뽑히지 않기위해서 chk 배열을 이용하여 중복이 생기지 않게 했습니다.

이때 나는 중복을 있게 1 1  /  1 2  /  1 3  /  1 4  /  2 1  /  2 2 ...

이렇게 뽑고 싶은경우 chk 가 들어간경우를 빼주면 됩니다.

가장 기본적인 틀이니 외워놓으면 그냥 모든 경우를 적용할수 있습니다.

https://www.acmicpc.net/problem/15654

15654번: N과 M (5)

 

#include<stdio.h>
#include<algorithm>
using namespace std;
int N, M;
const int inputSIZE = 8;
const int chkSIZE = 8;
const int DSIZE = 8;
int input[inputSIZE];
int D[DSIZE];
int chk[chkSIZE];
void init() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", &input[i]);
    }
    sort(input, input + N);
}
void dfs(int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++)printf("%d ", D[i]);
        printf("\n");
    }
    for (int i = 0; i < N; i++) {
        if (chk[i] == 0) {
            chk[i] = 1;
            D[idx] = input[i];
            dfs(idx + 1);
            D[idx] = 0;
            chk[i] = 0;
        }
    }
}
int main(void) {
    init();
    dfs(0);
    return 0;
}

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
map <vector<int>, int> m;
int N, M, ret;
const int doubleChkSIZE = 10001;
const int DSIZE = 8;
const int chkSIZE = 8;
int doubleChk[doubleChkSIZE];
vector<int>D;
int chk[chkSIZE];
vector<int>input;
void init() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        int data = 0;
        scanf("%d", &data);
            input.push_back(data);
    }
    sort(input.begin(), input.end());
}
void dfs(int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", D[i]);
        }
        printf("\n");
        return;
    }
    int before = 0;
    for (int i = 0; i < input.size(); i++) {
        if (chk[i] == 0&&before!=input[i]){ 
            before = input[i];
            chk[i] = 1;
            D.push_back(input[i]);
            dfs(idx + 1);
            D.pop_back();
            chk[i] = 0;
        }
    }
}
int main(void) {
    int T;
    //scanf("%d", &T);
    for (int tc = 1; tc <= 1; tc++) {
        init();
        dfs(0);
 
        //printf("#%d %d\n", tc, ret);
    }
    return 0;
}
 

중복순열

 

중복 순열은 이전에 봤던 순열과 비슷합니다. 아래의 문제를 보면서 이해해 봅시다.
https://www.acmicpc.net/problem/15651

 

15651번: N과 M (3)

1.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int DSIZE = 8;
const int chkSIZE = 9;
int D[DSIZE];
int chk[chkSIZE];
int N, M;
void init() {
    scanf("%d %d", &N, &M);
}
void dfs(int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++)printf("%d ", D[i]);
        printf("\n");
    }
    for (int i=1; i <= N; i++) {
        if (idx < M) {
            D[idx] = i;
            dfs(idx + 1);
            D[idx] = 0;
        }
        
    }
}
int main(void) {
    init();
    dfs(0);
    return 0;
}

https://www.acmicpc.net/problem/15656

 

15656번: N과 M (7)

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
const int DSIZE = 8;
const int inputSIZE = 8;
int D[DSIZE];
int input[inputSIZE];
void init() {
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++) {
        scanf("%d", &input[i]);
    }
    sort(input, input + N);
}
void dfs(int idx) {
    if (idx == M) {
        for (int i = 0; i < M; i++) printf("%d ", D[i]);
        printf("\n");
        return;
    }
    for (int i = 0; i < N; i++) {
        if (idx < M) {
            D[idx] = input[i];
            dfs(idx + 1);
            D[idx] = 0;
        }
    }
}
int main(void)
{
    init();
    dfs(0);
    return 0;
}

여기까지 오시느라 수고 많으셨고 정말 알고 보면 쉽지 않습니까? 당연한 소리 같지만

반복을 통해 익숙해서 나만의 것으로 만들어보면 비슷한 유형의 문제를 풀어도 

겁이 안 날것입니다. 

위에 소스가 완벽한 소스가 아니고 제가 의식의 흐름에 따라 작성한 소스라 빼도 되는

부분이 있을 것이고 할 것인데 참고 정도로만 생각해주시고 위의 소스를 기반으로 더 완벽한

소스를 만들어보시면 좋을 것 같습니다. 

대게 소스를 배열 기반으로 했지만 백터 기반으로도 가능하니 백터를 이용한 방식으로도 해보셔도

좋다고 생각합니다.

오늘은 여기까지이고 감사합니다.