봄봄.devlog
[0625] 브루트포스 | 순열 본문
01. 순열의 개념
-
1~N 까지로 이루어진 수열
-
1 2 3
-
4 1 3 2
-
5 4 2 3 1
-
6 5 1 2 3 4
-
크기는 항상 N이 되어야 하고, 겹치는 숫자가 존재하지 않음
* 순열을 이용해서 문제를 푼다 => 순서가 매우 중요한 경우
ex) N개 (사과, 바나나, 배, 딸기) 먹는 순서가 바뀌면 값이 달라짐. 따라서 순서가 매우 중요함. 1부터 N까지의 값이 한번씩 나오면서 순서가 다르게!
-
크기가 N인 순열은 총 N!개가 존재한다 => N / N-1 / N-2 / N-3... / 2 / 1가지
-
순열을 사전순으로 나열했을 때 (두 문자열을 비교 ex. abc < abd)
-
N=3인 경우에 사전순은 다음과 같다
-
1 2 3 (첫 순열 : 오름차순)
-
1 3 2
-
2 1 3
-
2 3 1
-
3 1 2
-
3 2 1 (마지막 순열 : 내림차순)
02. 다음 순열
-
순열을 사전순으로 나열했을 때, 사전순으로 다음에 오는 순열과 이전에 오는 순열을 찾는 방법
-
C++ STL의 algorithm에는 이미 next_permutation과 prev_permutation이 존재하기 때문에 사용하면 된다
01) 다음 순열 구하는 방법
① A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
② j >= i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다
③ A[i-1]과 A[j]를 swap한다
④ A[i]부터 순열을 뒤집는다
7! = 7 x 6!
1 2 3 4 5 6 7
1 2 3 4 5 7 6
...
...
1 7 6 5 4 3 2 ( 1에서 2로 넘어갈 때 마지막 순열, 765432 내림차순)
2 1 3 4 5 6 7 ( 2로 시작하는 첫 순열, 134567 오름차순)
그렇다면?
[ 2 3 1 ] 7 6 5 4 => [ 2 3 ? ] [ 오름차순 ] => [ 2 3 4 ] [ 1 5 6 7 ]
02) 다음 순열 구하는 방법(예시)
-
순열 : 7 2 3 6 5 4 1 => [ 7 2 3(i-1) ] >(성립안됨) 6(i) > 5 > 4 > 1 ( "723"으로 시작하는 마지막 순열, ">"방향이 나오지 않는 가장 작은 수 를 찾기!)
-
7 2 3 6 5 4 1 => ? [ 7 2 ? ] [ 오름차순 순열 ] ( 오른쪽에서 3보다 크면서 가장 작은 수(= 가장 오른쪽 = j)를 찾아야 한다) => 7 2 4 6 5 3 1 => 6 5 3 1 을 오름차순으로 => 7 2 4 1 3 5 6
-
A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다
-
즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾아야 한다
-
순열 : 7 2 3 6 5 4 1
03) 순열 시간복잡도
- 값을 swap 하는 시간복잡도 O(1)
- (i-1)값을 찾는 시간복잡도 O(N)
- j 값을 찾는 시간복잡도 O(N)
- 오름차순/내림차순으로 순서를 뒤집는 시간 복잡도 O(N)
※ 순열 시간복잡도 O(N) => i-1 값을 찾고 끝난 다음 j 값을 찾고 끝난 다음, swap하고 값을 뒤집었다.
각각의 관계가 "독립적"이기 때문에 O(N+N+N+1) = O(3N+1) = O(N)
boolean next_permutation(int[] a, int n) { // 크기가 n인 배열 a
int i = n-1;
while(i>0 && a[i-1] >= a[i]) i -= 1; // 부등호 ">"가 성립하지 않는 가장 작은 i-1 찾기, 뒤에서부터 시작
if( i<=0) return 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;
}
03. 모든 순열 구하기
-
첫순열 구하기 1,2,3,.....N
-
다음 순열을 계속 구하다가 다음 순열이 존재하지 않는 마지막 순열이 올 때까지 구하기
04. 팩토리얼
- 모든 순서 : O(N!)
- 모든 순열 : 다음 순열 구하기 O(N) x N! => O(N*N!)
* 11이상은 모든 순서를 만드는 것만으로도 1초가 넘어가기에 대부분 순열로 경우의 수를 만드는 문제는 10이하로 만들어진다.
'Algorithm > 코드플러스' 카테고리의 다른 글
[0629] 브루트포스 | 그냥 다 해보기 (0) | 2020.06.29 |
---|---|
[0626] 브루트포스 (0) | 2020.06.26 |