봄봄.devlog

[0625] 브루트포스 | 순열 본문

Algorithm/코드플러스

[0625] 브루트포스 | 순열

jihyun03 2020. 6. 22. 14:36

 

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
Comments