[순열] 백준 : N과 M - 1, 3, 5, 7, 9, 11 (순열)

N과 M (1) : https://www.acmicpc.net/problem/15649

N과 M (3) : https://www.acmicpc.net/problem/15651

N과 M (5) : https://www.acmicpc.net/problem/15654

N과 M (7) : https://www.acmicpc.net/problem/15656

N과 M (9) : https://www.acmicpc.net/problem/15663

N과 M (11) : https://www.acmicpc.net/problem/15665

 

1번은 n개의 자연수 중 m개를 고르는 순열(nPm)을 구하는 문제이고,

3번은 중복 순열을 구하는 문제이다.

5번은 1번과 똑같이 nPm을 구하는 문제인데, n개의 자연수가 크기에 상관없이 주어진다.

7번은 5번에다 중복 순열을 적용,

9번은 일반 순열에다 수열의 중복되는 숫자를 한번만 출력,

11번은 중복 순열에다 수열의 중복되는 숫자를 한번만 출력.

 

---

 

1. 스왑과 재귀를 사용해서 순열을 구현하는 경우

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;

void permutation(vector<int> nums, int depth)
{
  if (depth == M)
  {
    for (int i = 0; M > i; i++)
      cout << nums[i] << ' ';
    cout << '\n';
  }

  for (int i = depth; N > i; i++)
  {
    iter_swap(nums.begin() + i, nums.begin() + depth);
    permutation(nums, depth + 1);
  }
}

int main(void)
{
  cin >> N;
  cin >> M;

  vector<int> nums;

  for (int i = 1; N + 1 > i; i++)
    nums.push_back(i);

  permutation(nums, 0);
  return 0;
}

1번 문제. n이하의 숫자를 nums에 저장한 다음, depth와 i에 해당하는 숫자를 계속 스왑하며 재귀적으로 permutation을 실행한다. 즉,

 

nums = [1, 2, 3, 4]이고 첫 스타트 즉 depth가 0이라면, 

1. [1, 2, 3, 4] => depth + 1 상태로 재귀 => [1, 2, 3, 4] & depth + 2 상태로 재귀 + [1, 3, 2, 4] & depth + 2상태로 재귀...

2. [2, 1, 3, 4] => depth + 1 상태로 재귀 => [2, 1, 3, 4] & depth + 2 상태로 재귀 + [2, 3, 1, 4] & depth + 2상태로 재귀...

3. [3, 1, 2, 4] => depth + 1 상태로 재귀 => [3, 1, 2, 4] & depth + 2 상태로 재귀 + [3, 2, 1, 4] & depth + 2상태로 재귀...

4. [4, 1, 2, 3] => depth + 1 상태로 재귀 => [4, 1, 2, 3] & depth + 2 상태로 재귀 + [4, 2, 1, 3] & depth + 2상태로 재귀...

 

등으로 계속 스왑과 재귀를 진행하게 된다. 

기저조건은 당연히 depth와 M이 같아지는 때이다. 여기에선, depth에 해당하는 수만큼 nums에서 프린트해주면 된다.

 

 

 

---

 

 

 

2. 재귀만으로 순열을 구현하는 경우

 

// 5번 문제.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, numStatus[8] = {0};
vector<int> nums, number;

void permutation(vector<int> nums)
{
  if (nums.size() == M)
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = 0; N > i; i++)
  {
    if (numStatus[i])
      continue;

    nums.push_back(number[i]);
    numStatus[i] = 1;

    permutation(nums);
    nums.pop_back();
    numStatus[i] = 0;
  }
}

int main(void)
{
  int k;

  cin >> N;
  cin >> M;

  for (int i = 0; N > i; i++)
  {
    cin >> k;
    number.push_back(k);
  }
 
 
  // input으로 들어온 숫자들을 정렬한 후 순열을 구함.
  // 1번 문제에서, cin으로 숫자를 받아 정렬해준 차이밖에 없음.
  sort(number.begin(), number.end()); 
  

  permutation(nums);
  return 0;
}

 

같은 수가 중복되는 경우를 막기 위하여, numStatus 배열을 만들고 0으로 초기화한다.

 

for 문을 돌면서, 숫자 하나씩 nums 배열에 넣고 numStatus를 1로 변경하면서 재귀를 진행한다. numStatus와 if문으로 인해, 이미 선택된 숫자인 경우(numStatus[i] == 1)에는 그냥 패스한다. 재귀가 진행된 후에는 다시 숫자를 nums 배열에서 빼고, numStatus를 0으로 바꾼다.

 

기저 조건은, 고른 숫자들의 갯수(nums 배열의 크기) == M 일 때이다. 이 경우엔 nums를 전부 프린트한다.

 

 

// 9번 문제.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, numStatus[8] = {0};
vector<int> nums, number;

void permutation(vector<int> nums)
{
  int prevNum; // 이전 숫자를 저장하는 변수를 선언.

  if (nums.size() == M)
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = 0; N > i; i++)
  {
    if (numStatus[i])
      continue;

    // 정렬된 배열에서는, 만약 중복된 값이 들어올 시 이전의 숫자와 동일한 값이므로,
    // 재귀를 건너뛴다.
    if (i != 0)
      if (prevNum == number[i])
        continue;

    nums.push_back(number[i]);
    numStatus[i] = 1;

    permutation(nums);

    nums.pop_back();
    numStatus[i] = 0;
    prevNum = number[i];
  }
}

int main(void)
{
  int k;

  cin >> N;
  cin >> M;

  for (int i = 0; N > i; i++)
  {
    cin >> k;
    number.push_back(k);
  }

  sort(number.begin(), number.end());

  permutation(nums);
  return 0;
}

 

 

---

 

 

3. 중복 순열일 경우

 

// 3번 문제

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, number[7] = {1, 2, 3, 4, 5, 6, 7};
vector<int> nums;

void repPer(vector<int> nums)
{
  if (nums.size() == M)
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = 0; N > i; i++)
  {

    nums.push_back(number[i]);
    repPer(nums);
    nums.pop_back();
  }
}

int main(void)
{
  cin >> N;
  cin >> M;

  repPer(nums);
  return 0;
}

 

중복을 허용하기에, numStatus를 없애고 그냥 i = 0부터 N - 1까지 for문 돌면서 재귀를 불러주면 된다.

 

// 7번. 중복 순열.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M, k;
vector<int> numbers, nums;

void permutation(vector<int> nums, int depth)
{
  if (nums.size() == M)
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = depth; N > i; i++)
  {
    nums.push_back(numbers[i]);
    permutation(nums, depth);
    nums.pop_back();
  }
}

int main(void)
{
  cin >> N;
  cin >> M;

  for (int i = 0; N > i; i++)
  {
    cin >> k;
    numbers.push_back(k);
  }

  sort(numbers.begin(), numbers.end());

  permutation(nums, 0);

  return 0;
}

depth를 파라미터로 사용하였는데, 없어도 상관이 없다.

 

 

// 11번 문제.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> nums, number;

void permutation(vector<int> nums)
{
  int prevNum; // 이전 숫자를 저장하는 변수를 선언.

  if (nums.size() == M)
  {
    for (auto num : nums)
      cout << num << ' ';
    cout << '\n';
    return;
  }

  for (int i = 0; N > i; i++)
  {
    if (i != 0)
      if (prevNum == number[i])
        continue;

    nums.push_back(number[i]);

    permutation(nums);

    nums.pop_back();
    prevNum = number[i];
  }
}

int main(void)
{
  int k;

  cin >> N;
  cin >> M;

  for (int i = 0; N > i; i++)
  {
    cin >> k;
    number.push_back(k);
  }

  sort(number.begin(), number.end());

  permutation(nums);
  return 0;
}