본문 바로가기
알고리즘, 자료구조/알고리즘

[백준] 15649 N과 M (1) - 순열

by Wordbe 2019. 9. 19.
728x90

 

단계별로 풀어보기에서 N과 M 시리즈 4개 중 개인적으로 가장 어렵다고 생각한다.

하지만, dfs와 백트래킹을 알고 있다면, N과 M문제 자체가 그렇게 어려운 편은 아니다.

DFS는 그래프에서 깊이 우선 탐색을 의미하지만,

완전 탐색에서 주로 쓰이는 알고리즘으로, 모든 것을 다해보는 브루트포스 알고리즘과도 연관이 있다.

백트래킹은 여기에 조건을 더해주어, 원하는 경로로 탐색할 수 있게 도와주는 장치이다.

 

구현 코드 2개를 소개하고자 한다.

 

#include <cstdio>
using namespace std;
int n, m;
int a[8];

void swap_(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void rotateR(int start, int end){
    int tmp = a[end];
    for (int i=end; i>start; --i) a[i] = a[i - 1];
    a[start] = tmp;
}

void rotateL(int start, int end){
    int tmp = a[start];
    for (int i=start; i<end; ++i) a[i] = a[i + 1];
    a[end] = tmp;
}

void printlnArray(int size){
    for (int i=0; i<size; ++i) printf("%d ", a[i]);
    printf("\n");
}

void permutation(int depth){
    if (depth == m){
        printlnArray(m);
        return;
    }
    
    for (int i=depth; i<n; ++i){
        swap_(a[i], a[depth]);
        permutation(depth + 1);
        swap_(a[i], a[depth]);
    }
}

void permutation_dictionary(int depth){
    if (depth == m){
        printlnArray(m);
        return;
    }
    for (int i=depth; i<n; ++i){
        rotateR(depth, i);
        permutation_dictionary(depth + 1);
        rotateL(depth, i);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; ++i) a[i] = i + 1;
    permutation_dictionary(0);
    return 0;
}

우선 permutation함수는 순서상관없이 모든 순열의 수를 출력하는 함수이다.

사전순으로 출력하고 싶다면, permutation_dictionary를 사용해야 한다.

이 알고리즘을 이해하는 건 예시하나 잡고 일일이 해보면 된다.

nPm 이 있을 때, n = 3, m = 2일 때를 고려해보자.

1 2

1 3

2 1

2 3

3 1

3 2

이렇게 끝이다.

rotateR, rotateL을 살펴보고 싶으면 m수를 좀 더 늘려야 이해가 잘 갈것이다.

 

하지만, 이것보다 더 좋은아이디어라고 생각하는 알고리즘이 밑의 코드에 있다. rotate하는데는 대략 O(N)의 시간이 걸리므로, 밑의 코드가 시간복잡도가 훨씬 낮다. 

nPm의 경우를 모두 찾는 탐색이다보니, O(nPm)의 시간복잡도를 가진다.

#include <iostream>
int N, M;
char a[20];
bool chk[20];
using namespace std;

void permutation(int depth){
    if (depth == M){
        cout << a << '\n';
        return;
    }
    for (int i=0; i<N; ++i){
        if (chk[i]) continue;
        a[depth * 2] = i + '1';
        chk[i] = true;
        permutation(depth + 1);
        chk[i] = false;
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for (int i=0; i<2*M; ++i) a[i] = ' ';
    permutation(0);
    return 0;
}

 

728x90

댓글