개발세리의 성장기🌿
🔵 brute force - 순열 사용하기 본문
안녕하세요 :) 오늘은 순열을 사용하는 BF 알고리즘에 대해 알아보겠습니다. 줄서는 방법, 특정 작업 순서의 모든 경우의 수 등, 순서가 중요한 작업에 있어 BF + 순열을 사용합니다. 그럼 오늘도 화이팅 입니다🌿
순열이란 ?
- 순열이란 1~N까지 이루어진 수열을 의미합니다.
- 따라서, 크기가 N인 순열은 총 N!개 존재하게 됩니다.
- 어떤 수열의 다음 수열을 알아내는 연산의 시간 복잡도는 O(N)이 됩니다.
- BF에서 순열은 순서가 중요할 때, 사용되곤 합니다. (ex. 과일을 먹는 순서 )
다음 순열 찾기 알고리즘 시간 복잡도
-
A[0] ~ A[N-1] 에서, A[i-1] > A[i] 을 만족하지 않는 지점 찾기 -> 조건이 만족하지 않는 지점 A[i-1]
🕖 최대 N 번 실행되므로, O(N)
-
A[i] ~ A[N-1] 에서, 가장 긴 감소하는 수열 찾기 -> A[i] ~ A[i+?] == B[0] ~ B[?+1]
🕖 최대 N 번 실행되므로, O(N)
-
A[i] ~ A[N-1] 사이에서, A[i-1] 보다 값이 크며, 가장 작은 수 찾기 -> A[j]
-
A[i-1] 과 A[j]를 swap !
🕖 최대 한번 실행되므로, O(1)
-
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로 해결할 수 있습니다.
'algorithm > PS' 카테고리의 다른 글
🌌 graph - 그래프의 표현, DFS와 BFS (0) | 2021.01.21 |
---|---|
🔵 brute force - 입문 (0) | 2021.01.20 |
수학) 소수 판별법: 에라토스테네스의 체 (0) | 2020.04.22 |
그리디) 그리디를 공부하면서 (0) | 2020.03.10 |
그래프) 2. DFS (그래프의 깊이 우선 탐색) (0) | 2020.02.14 |
Comments