[기초] 순열

순열은 순서가 중요하다.

브루트 포스에 어떻게 적용하느냐? 순서가 중요한 브루트 포스에 적용한다.

 

1. 첫 순열을 만든다.

2. 다음 순열을 구한다.

3. 다음 순열을 구한다.

... 마지막 순열이 나올때 까지 구한다.

 

이때, 필요한 것 ( 사전순 일 때)

1. 첫 순열을 구하는 방법 (오름차순..)

2. 다음 순열을 구하는 방법 (C++ STL 의 <algorithm> 에서는 next_permutation 이나 prev_permutaiton 사용 )

3. 마지막 순열을 구하는 방법 (내림차순..)

xx 로 시작하는 마지막 순열을 찾는 것이 중요하다. 사전순이므로, 마지막 순열을 만족하는 것은 내림차순이 얼마나 지속되느냐를 찾는 것과 동일하다.

 

위의 7236541 에서는 723 으로 시작하는 마지막 순열이라고 볼 수 있는 것이다.

 

내림차순 순열의 첫 시작을 i 번째 라고 하자. (7236541 에서는 6이 i 번째 idx 이다.)

 

그렇다면, i - 1 번째를 바꾸어야 다음 순열 즉, xxx 로 시작하는 첫 순열을 만들 수 있다.

 

무엇과 i - 1 번째 (3) 을 바꾸어야 할까?

 

뒤의 내림차순 수열에서, i - 1 번째 보다는 크고 그 중에서는 가장 작은 수를 택해야 한다.

 

바꾸어 준다면 (7236541 -> 7246531) 이 될 것이다.

 

마지막 순열의 내림차순 (6531) 은 항상 내림차순을 만족하기에 이를 뒤집어 준다.

 

-> 7241356

 

723 으로 시작하는 마지막 순열이 724로 시작하는 첫 순열로 바뀌었다!

 

• 1248 맞춰봐
• 10819 차이를 최대로
• 10971 외판원 순회 2
• 6603 로또