c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q44 정렬의 교환 횟수 최소화하기

1, 2, 3을 나열하는 방법은 총 6가지이다. 각 경우에서 1, 2, 3 오름차순으로 정렬하기 위해 필요한 최소 이동횟수는 아래와 같다.

1) 1, 2, 3 => 이동횟수 : 0

2) 1, 3, 2 => 이동횟수: 1 (2와 3을 바꿈)

3) 2, 1, 3 => 이동횟수: 1 (1과 2를 바꿈)

4) 2, 3, 1 => 이동횟수: 2 (1과 2를 바꾼 후, 2와 3을 바꿈)

5) 3, 1, 2 => 이동횟수: 2 (1과 3을 바꾼 후, 2와 3을 바꿈)

6) 3, 2, 1 => 이동횟수: 1 (1과 3을 바꿈)

위 최소 이동횟수를 모두 더하면 7이 된다.

[문제] 1, 2, 3, 4, 5, 6, 7을 나열하는 모든 경우에 대해서 오름차순으로 정렬하기 위해 필요한 최소 이동횟수의 합은?

 

 

[알고리즘 #1]

알고리즘 자체는 단순하다.

1 ~ 7 순열을 차례대로 모두 구한 후, 각 경우에 대해서 오름차순으로 정렬하기 위해 필요한 최소 이동횟수를 구한다.

어떤 주어진 배치 (arr)에 대해서 최소 이동횟수를 구하는 함수는 다음과 같다.

copy 배열을 별도로 사용한 이유는 arr의 값을 변화시키면 안되기 때문.

int calc_cnt(int* arr) {
    int copy[N];
    copy_arr(copy, arr);
    int cnt = 0;
    for (int i = 0; i < N - 1; i++) {
        if (copy[i] == i + 1)
            continue;
        for (int j = i + 1; j < N; j++) {
            if (copy[j] == i + 1) {
                swap(&copy[i], &copy[j]);
                cnt++;
            }
        }
    }
    return cnt;
}

예를 들어, 2, 3, 1, 4, 5, 7, 6 으로 나열된 경우 

2, 3, 1, 4, 5, 7, 6 => 1, 3, 2, 4, 5, 7, 6 => 1, 2, 3, 4, 5, 7, 6 => 1, 2, 3, 4, 5, 6, 7

총 3번 이동하면 된다.

 

아래는 전체 코드

#include <stdio.h>
#include <stdbool.h>
#define N 7
void solve(int* arr, bool* isUsed, int* sum, int depth);
int calc_cnt(int* arr);
void swap(int* x, int* y);
void copy_arr(int* copy, int* arr);
int main() {
    int arr[N] = { 0 };
    bool isUsed[N] = { false };
    int sum = 0;
    solve(arr, isUsed, &sum, 0);
    printf("sum = %d\n", sum);
    printf("\n");
}
void solve(int* arr, bool* isUsed, int* sum, int depth) {
    if (depth == N) {
        (*sum) += calc_cnt(arr);
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (isUsed[i - 1] == true)
            continue;
        arr[depth] = i;
        isUsed[i - 1] = true;
        solve(arr, isUsed, sum, depth + 1);
        isUsed[i - 1] = false;
    }
}
int calc_cnt(int* arr) {
    int copy[N];
    copy_arr(copy, arr);
    int cnt = 0;
    for (int i = 0; i < N - 1; i++) {
        if (copy[i] == i + 1)
            continue;
        for (int j = i + 1; j < N; j++) {
            if (copy[j] == i + 1) {
                swap(&copy[i], &copy[j]);
                cnt++;
            }
        }
    }
    return cnt;
}
void swap(int* x, int* y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}
void copy_arr(int* copy, int* arr) {
    for (int i = 0; i < N; i++)
        copy[i] = arr[i];
}
void print_arr(int* arr, int sz) {
    for (int i = 0; i < sz; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

정답은 22,212가지.

 

[알고리즘 #2]

수학을 이용하면 훨씬 더 빠르고 간단하게 답을 구할 수 있다.

1부터 n까지 n개 숫자에 대해 문제에서 구하고자 하는 최소 이동횟수 총합을 f(n)이라고 할 때, f(4)를 한 번 구해보자.

1) 맨 앞자리가 1인 경우 - 총 6가지 배열이 가능하며, 이때의 최소 이동횟수의 합은 7 = f(3) 이다.

1 2 3 4 : 이동횟수 0

1 2 4 3 : 이동횟수 1

1 3 2 4 : 이동횟수 1

1 3 4 2 : 이동횟수 2

1 4 2 3 : 이동횟수 2

1 4 3 2 : 이동횟수 1

=> 합은 7이며, 곧 f(3)과 같다.

2) 맨 앞자리가 2인 경우 - 마찬가지로 총 6가지 배열이 가능하다.

2 1 3 4 => 1과 2를 바꾸면 1 2 3 4 가 된다. 이동횟수 1 + 0 = 1

2 1 4 3 => 1과 2를 바꾸면 1 2 4 3이 된다. 이동횟수 1 + 1 = 2

2 3 1 4 => 1과 2를 바꾸면 1 3 2 4가 된다. 이동횟수 1 + 1 = 2

2 3 4 1 => 1과 2를 바꾸면 1 3 4 2가 된다. 이동횟수 1 + 2 = 3

2 4 1 3 => 1과 2를 바꾸면 1 4 2 3이 된다. 이동횟수 1 + 2 = 3

2 4 3 1 => 1과 2를 바꾸면 1 4 3 2이 된다. 이동횟수 1 + 1 = 2

즉, 맨 앞자리가 2인 경우는 맨 앞자리가 1인 경우에 대해서 이동횟수가 1씩 더 증가한다고 보면 된다.

=> 7 + 3! = 13

3) 맨 앞자리가 3, 4인 경우도 마찬가지로 각각 13이다.

즉, f(4) = f(3) + 3*(f(3) + 3!) = 7 + 3 * 13 = 46

 

이를 일반화하면 아래와 같다.

f(n) = n * f(n - 1) + (n - 1) * (n - 1)! 

아래는 코드

#include <stdio.h>
#define N 7

int main() {
    int F[N + 1] = { 0, 0 };        // f(1) = 0
    int FACTO[N + 1] = { 0, 1 };  

    printf("%d\n", f(F, FACTO, N));
}
int f(int* F, int* FACTO, int n) {
    if (F[n])
        return F[n];
    if (n == 1)
        return F[1];
    F[n] = f(F, FACTO, n - 1) * n + factorial(FACTO, n - 1) * (n - 1);
    return F[n];
}
int factorial(int* FACTO, int n) {
    if (FACTO[n])
        return FACTO[n];
    FACTO[n] = n * factorial(FACTO, n - 1);
    return FACTO[n];
}

코드가 간결하며, 계산 속도도 빠르다.

정답은 동일하게 22,212가지.

n = 7인 경우 합계

n = 10인 경우도 순식간에 구할 수 있다.

n = 10인 경우 합계