조합?

조합의 알고리즘은 이전에 설명했던 순열과는 다르지만 알고리즘 문제에 굉장히 많이 나오는 유형중의 하나이다. 거의 공식같이 사용되기 때문에 잘 이해햐두고 변행해서 쓰면 알고리즘 풀이에 유용할 듯하다.

조합은 Combination으로 5개중 3개를 선택하되 중복을 허락하지 않는 것을 의미한다. 중학교인가 고등학교 수학시간에 배웠던 것 같은 기억이 나는데 수학적인 계산 법은 아래와 같다.

5 X 4 X 3 / 3 X 2 X 1 = 10 가지, 그래서 5개중 3개를 선택하되 중복되지 않는 경우는 10가지 이다. 근데 중복되는게 어떤건지 햇갈리다면 다시 한번 봐보자.

 

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 4 5

2 3 5

3 4 5

 

눈치챗을지 모르지만, 1 2 3 과 2 3 1, 3 2 1 은 5개중 3개를 선택할때 1과 2와 3을 선택하는 동일한 경우로 되기 때문에 중복처리하는게 포인트다. 기존에 순열에 대해서 글을 작성했는데 이 경우는 1 2 3, 2 3 1, 3 2 1 은 각각 다른 경우라고 판단하는 것과 가장 큰 차이점이다. 알고리즘 문제에서는 이런식으로 나올 수 있다.

 

ex) 나무 10개중 3개를 선택하는 경우

10개의 나무중 3개를 골라 각각 재단한다고 한다. 3개를 고른뒤 몇센치씩 자르면 이익이 최대화 되는가?

=> 이경우는 무엇에 해달될까? 바로 조합이다. 왜냐면 1번 나무 2번 나무 3번 나무 선택한 것과 3번나무 2번 나무 1번 나무를 선택한 경우는 같기 때문이다.

 

알고리즘 문제를 풀때, 문제를 잘 읽어야 하는데 그안에 풀이 방법이 숨어있기 때문이다. 위의 경우 조합으로 우선 잡고 그 뒤에 목재 재단 하는 계산을 넣으면 풀리게 된다.

그럼, 실제 코드를 살펴보자. 순열의 경우는 다른 글에서 설명했으니 별도로 설명하진 않고, 조합처리하는 부분의 코드를 우선 보자.

}
 if (index == r) {
  printAll(r);
  return;
 }

 if (i >= n) return;
 result[index] = data[i];
 combi(n, r, index+1, i+1);
 combi(n, r, index, i+1);
}

 

combi의 함수를 보면 파라메터로 n, r, index, i 가 정해져있다. n은 토탈 갯수이고, r은 그중에 선택해야하는 개수(ex 5개중 3개)그리고 index, i가 여기서 핵심이다. index의 경우 r 개가 선택되면 출력되도록 하기 위해서 새로운 array인 result에 답는 index로 쓰이며 i는 실제 data라는 배열에 이미 저장되어 있는 숫자의 index이다. 그리고 i >=n 일 경우 리턴처리하는 이유는 당연히 data가 n-1까지 밖에 없기 때문이다.(0부터 시작하므로). 마지막으로 index와 i를 각각 증가시키고 return이 되면 i 만 증가시켜서 1 2 3, 1 2 4 , 1 2 5 그리고 1 3 4 가 되도록하는게 핵심포인트이다.

 

다시말해서 루프의 시퀀스를 보면,

1 2 3 => 출력, i 증가

1 2 4 => 출력, i 증가 

1 2 5 => 출력, i 증가, return, return, depth 증가, i 증가

1 3 4 => 출력, i 증가

1 3 5 => 출력, i 증가, return return, depth 증가, i 증가

 

실제 전체 코드를 살펴보자. 비교를 위해 순열(perm 함수랑 같이 작성해 두었다.)

#include <stdio.h>
#define MAX 5

int data[MAX+1];
int visited[MAX + 1];
int permIdx;
int result[MAX + 1];
int gCount;

 

void printAll(int r) {
 for (int i = 0; i < r; ++i){
  printf("%d ", result[i]);
 }
 gCount++;
 printf("\n");
}

void combi(int n, int r, int index, int i) {
 if (index == r) {
  printAll(r);
  return;
 }

 if (i >= n) return;
 result[index] = data[i];
 combi(n, r, index+1, i+1);
 combi(n, r, index, i+1);
}

void perm(int depth, int n, int r) {
 if (depth == r) {
  printAll(r);
  return;
 }

 for (int i = 0; i < n; ++i) {
  if (visited[i] == 0) {
   visited[i] = 1;
   result[permIdx++] = data[i];
   perm(depth + 1, n, r);
   visited[i] = 0;
   permIdx--;
   result[permIdx] = 0;
  }
 }
}

int main(void)
{
 for (int i = 0; i < MAX; ++i) {
  data[i] = i + 1;
 }
 int r = 0;
 scanf("%d", &r);
 //조합
 combi(MAX, r, 0, 0);

 //순열
 //perm(0, MAX, r);

 printf("Total : %d\n", gCount);
 return 0;
}

 

 

순열과, 조합은 알고리즘의 기본이기 때문에 공식처럼 코드를 암기하는 것도 알고리즘 문제를 풀고 발전해나가는 한가지 방법이 될 듯하다.