[Algorithm] 조합(Combination)

개요

 

◎ 조합이란?

◎ 구현코드 (Java)

◎ 시간 복잡도

 

 

 

안녕하세요. J4J입니다.

 

이번 포스팅은 조합에 대해 적어보는 시간을 가져보려고 합니다.

 

 

조합이란?

 

조합은 고등학교 수학 시간에 배웠던 것으로 개념을 정의해보면 서로 다른 n개 중에서 순서를 생각하지 않고 r개를 택하는 경우의 수를 의미합니다.

 

대표적으로 4명의 학생 중 2명의 회장을 뽑는 회장 뽑기 문제가 있습니다. (1명은 회장, 1명은 부회장이면 순열)

 ※ 순열에 대해 궁금하시면? [Algorithm] 순열(Permutation)

 

4명의 학생을 각각 A, B, C, D라고 가정할 때 2명의 회장이 뽑히는 경우를 구해보면 다음과 같습니다.

1. A, B

2. A, C

3. A, D

4. B, C

5. B, D

6. C, D

 

순열을 구하는 공식도 다음과 같이 있습니다.

 

 

위의 예시를 공식에 대입을 해보면 4! / (4-2)!x2! 이므로 결과값이 6이 나오게 됩니다.

 

직접 경우를 구해본 것과 동일한 결과값이 나온다는 것을 확인할 수 있습니다.

 

위의 예제를 코드로 구현해보겠습니다.

 

728x90

 

구현코드 (Java)

 

package math;

import java.util.Arrays;

public class Combination {
	static int count;
	
	public static void main(String[] args) {
		String[] stringArray = new String[]{"A", "B", "C", "D"};
		
		int n = stringArray.length;
		int r = 2; // r값을 조정하여 다른 결과값 만들기
		String[] combArray = new String[r];
		
		combination(n, r, stringArray, combArray);
		
		System.out.println("총 갯수: " + count); // 총 갯수: 6

	}
	
	public static void combination(int n, int r, String[] stringArray, String[] combArray) {
		if(r <= 0) { // combArray에 저장 종료
			System.out.println(Arrays.toString(combArray)); // [C, D]
											   // [B, D]
											   // [A, D]
											   // [B, C]
											   // [A, C]
											   // [A, B]
			
			count++;
			return;
		} else if(n < r) { // 알맞은 조합 만들기 불가
			return;
		} else {
			combArray[r-1] = stringArray[n-1];
			combination(n-1, r-1, stringArray, combArray);
			combination(n-1, r, stringArray, combArray);
		}
	}
}

 

참고적으로 코드를 보시면 재귀 함수 부분에 n값과 r값을 각각 순서대로 (n-1, r-1), (n-1, r)을 집어넣는 것을 확인하실 수 있습니다.

 

그리고 수학시간에 배웠던 조합과 관련되어 이런 공식도 있었습니다.

 

 

 

시간 복잡도

 

조합의 시간 복잡도는 n값에 대한 모든 경우의 수를 구했을 때 O(2^N)을 가집니다.

 

구하는 방법은 다음과 같습니다.

 

 

값을 모두 더했을 때 2^N이 나오는 이유는 너무 수학 시간인것 같아 생략하도록 하겠습니다. (너무 궁금하시면 구글 검색 해주세요.)

 

이처럼 조합은 적지 않은 시간이 걸리기에 n값이 조금이라도 커지면 실행시키기 위해 매우 오랜 시간이 걸릴 수 있다는 점을 알고 계셔야 됩니다.

 

 

정리

 

● 조합은 서로 다른 n개중 순서를 생각하지 않고 r개를 택하는 경우의 수를 의미

● O(2^N) 이라는 적지 않은 시간 복잡도를 가짐

● 수학 시간인지 코딩하는 시간인지 잠시 헷갈릴 뻔

 

이상으로 조합에 대해 간단하게 알아보는 시간이었습니다.

 

읽어주셔서 감사합니다.