2-2. 순열

순열

• 1~N까지 이루어진 순열로, 크기는 항상 N이며 겹치는 숫자가 존재하지 않는다.
• 크기가 N인 순열은 총 N!개가 존재한다.
• 순열을 사전순으로 나열했을 때, 다음에 오는 순열과 이전에 오는 순열을 찾을 수 있다.
• N이 3인 경우 사전순으로 나열한 수열은 다음과 같다.
• 아래의 표에서 1번째 순열은 오름차순으로 정렬된 순열이 되며, 마지막 순열(6번째 순열)은 내림차순으로 정렬된 순열임을 알 수 있다.

순서	수열
1번째 순열	123
2번째 순열	132
3번째 순열	213
4번째 순열	231
5번째 순열	312
6번째 순열	321

다음 순열

10972 다음 순열, 백준 온라인 저지
위에서 정리한 내용을 토대로 다음에 오는 순열을 찾을 수 있다.

• A\[i-1\] < A\[i\]를 만족하는 가장 큰 i를 찾는다.
• j>=i이면서 A[j]>A[i-1]를 만족하는 가장 큰 j를 찾는다.
• A[i-1]과 A[i]의 위치를 서로 바꾼다.
• A[i]부터 순열의 순서를 뒤집는다.

bool next_permutation(int *a, int n) {
  int i = n-1;

  while (i > 0 && a[i-1] >= a[i]) i -= 1;

  if (i <= 0) {
      //A[i-1] < A[i]를 만족하는 가장 큰 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;
}

이전 순열

10973 이전 순열, 백준 온라인 저지
다음 순열을 찾은 방법을 뒤집어서 생각하면, 이전 순열을 찾는것도 동일한 방법으로 찾을 수 있다.

모든 순열

10974 모든 순열, 백준 온라인 저지
첫 순열을 찾은 후, 마지막 순열이 될 때까지 다음 순열을 찾으면 된다.

차이를 최대로

10819 차이를 최대로, 백준 온라인 저지
수 N개가 주어졌을 때 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|의 값이 최대가 되도록 숫자를 배치하는 문제이다. 이 때 수의 범위가 3<=N<=8로 제한되는데, 8!=40320으로 모든 경우를 다 해보더라도 경우의 수가 많지 않다. 따라서 다음 순열을 찾는 방법을 이용하여, 모든 경우의 계산결과를 구하면 된다.

외판원 순회2 (Travelling Salesman Problem, TSP)

10971 외판원 순회2, 백준 온라인 저지
한 도시에서 시작해 N개의 모든 도시를 거친 후, 다시 원래의 도시로 돌아온다. 이 때 비용의 최소값을 구하는 문제이다. 수의 범위가 2<=N<=10으로 제한되는데, 10!=3628800으로 모든 경우를 다 해봐도 시간안에 계산할 수 있다. 이 때 모든 경우를 구하는 시간복잡도는 O(N!)이고, 비용을 계산하는데 시간복잡도는 O(N)이므로 전체 시간복잡도는 O(N*N!)이 된다.

• 이 때 전체 비용의 최소값을 구해야하므로, N이 4로 주어졌을 때 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 은 모두 같은 비용이 든다는 것을 알 수 있다. 즉, 시작점을 1로 고정함으로써 계산량을 1/4로 줄일 수 있다.

로또

6603 로또, 백준 온라인 저지
배열에 중복값이 있더라도 다음 순열을 찾는데는 크게 지장이 없다. 입력으로 K개의 수가 주어졌을 때 6개의 수를 고르는 문제는, 6개의 1과 K-6개의 0으로 이루어진 순열로 만들어서 모든 조합을 구할 수 있다.

연산자 끼워넣기

14888 연산자 끼워넣기, 백준 온라인 저지
N개의 수로 이루어진 수열과 N-1개의 연산자가 있을 때, 수식의 결과와 최대값과 최소값을 구하는 문제이다.

• 단, 2<=N<=11이며, 연산자의 우선순위를 무시하고 앞에서부터 계산을 진행한다. 수의 순서는 바꿀 수 없다.
  위의 조건에서 N!가지의 모든 경우의 수를 순회해보면 결과를 구할 수 있다.