[삼성 알고리즘] 순열과 조합

안녕하세요 Blue-Moon 입니다. 다시 알고리즘 공부를 시작하면서 블로그 포스팅을 진행하게 되었습니다~!

이번 포스팅 내용은 기본적인 알고리즘 순열과 조합입니다.

 

     1. 조합

기본적으로 조합의 모든 경우의 수를 출력 하는 함수는 O(n^2) 재귀를 이용해야 함.

추가적으로 조합의 개수 즉 nCr이 값만 아는 방법은 조합 공식을 이용 함.

nCr = n-1Cr-1 + n-1Cr

해당 알고리즘을 통해 개수를 구할 수 있음.

 

• 조합의 개수 c++ 코드

 

#include "Combination.h"

 

int main(void) {

 cout << combination(5, 2) << endl;

 return 0;

}

 

//nCr = (n-1)C(r-1) + (n-1)C(r)

int combination(int n,int r) {

 if (n == r)

  return 1;

 else if (r == 1)

  return n;

 else

  return combination(n - 1, r - 1) + combination(n - 1, r);

}

 

 

     2. 순열

순열의 경우 기본적으로 O(n^2) 재귀를 이용하며 다음 순열 알고리즘을 통해 O(n)으로 현재 주어진 값의 다음 순열을 구할 수 있음(앞에서부터 뒤로 가는 방향을 기준으로 다음 순열)

 

다음 순열 알고리즘의 원리는 뒤에서부터 이웃한 값을 비교함으로써 뒤의 숫자(i번째)가 바로 앞의 숫자(i-1번째)보다 더 큰경우 자리를 바꿔주고 i번째부터 마지막까지 오름차순 정렬을 해주면 된다.

<이 때 i번째 숫자가 i-1번째보다 큰 이웃한 값이 없다면 해당 순열이 마지막 순열이다.>

 

• 다음 순열

#include "Permutation.h"

 

int main(void) {

 int arr[] = { 6,2,4,3};

 int size = 4;

 if (permutation(arr, size) == -1) {

  cout << "There is no next permutation" << endl;

 } else {

  for (int i = 0; i < size; i++) {

  cout << arr[i] << endl;

   }

 }

 return 0;

}

 

int permutation(int* arr, int size) {

 int buf;

 

 for (int i = size-1; i > 0; i--) {

  if (arr[i] > arr[i-1]) {

   buf = arr[i];

   arr[i] = arr[i - 1];

   arr[i - 1] = buf;

   sort(arr + i, arr + size);

   return 0;

  }

 }

 return -1;

}