🔵 brute force - 순열 사용하기

안녕하세요 :) 오늘은 순열을 사용하는 BF 알고리즘에 대해 알아보겠습니다. 줄서는 방법, 특정 작업 순서의 모든 경우의 수 등, 순서가 중요한 작업에 있어 BF + 순열을 사용합니다. 그럼 오늘도 화이팅 입니다🌿

순열이란 ?

• 순열이란 1~N까지 이루어진 수열을 의미합니다.
• 따라서, 크기가 N인 순열은 총 N!개 존재하게 됩니다.
• 어떤 수열의 다음 수열을 알아내는 연산의 시간 복잡도는 O(N)이 됩니다.
• BF에서 순열은 순서가 중요할 때, 사용되곤 합니다. (ex. 과일을 먹는 순서 )

다음 순열 찾기 알고리즘 시간 복잡도

1. A[0] ~ A[N-1] 에서, A[i-1] > A[i] 을 만족하지 않는 지점 찾기 -> 조건이 만족하지 않는 지점 A[i-1]

   🕖 최대 N 번 실행되므로, O(N)

2. A[i] ~ A[N-1] 에서, 가장 긴 감소하는 수열 찾기 -> A[i] ~ A[i+?] == B[0] ~ B[?+1]

   🕖 최대 N 번 실행되므로, O(N)

3. A[i] ~ A[N-1] 사이에서, A[i-1] 보다 값이 크며, 가장 작은 수 찾기 -> A[j]

4. A[i-1] 과 A[j]를 swap !

   🕖 최대 한번 실행되므로, O(1)

5. A[i-1] ~ A[N-1] 를 오름차순 정렬

   🕖 O(N)

따라서, O(3N + 1) 이므로, 특정 순열의 다음 순열을 찾는 알고리즘은 O(N)의 시간 복잡도를 가지게 됩니다.

(C++ STL next_permutation, prev_permutation)

bool next_permutation(vector<int> &a, int n) {
    int i = n-1;
    while (i > 0 && a[i-1] >= a[i]) {
        i -= 1;
    }
    if (i <= 0) {
        return false; // 마지막 순열이면 false
    }
    int j = n-1;
    while (a[j] <= a[i-1]) {
        j -= 1;
    }
    swap(a[i-1], a[j]);
    j = n-1;
    while (i < j) {
        swap(a[i], a[j]);
        i += 1;
        j -= 1;
    }
    return true; // 다음 순열이 있다면 true
}

이전 순열 찾기 알고리즘 시간 복잡도

다음 순열 찾기 알고리즘과 조건(부등호의 방향)만 다르므로, O(N)의 시간 복잡도를 가지게 됩니다.

모든 순열 찾기 알고리즘 시간 복잡도

• N 순열에 대한 경우의 수는 N!가지, 특정 순열에 대한 다음 순열을 찾는 연산의 시간 복잡도는 O(N)이므로, 모든 순열 찾기 알고리즘은 O(N!) * O(N)의 시간 복잡도를 가지게 됩니다.
• N이 10 이하이면, 1초안에 BF로 해결할 수 있습니다.