본문 바로가기
Algorithm

[Java] 조합 Combination

by 건복치 2020. 5. 12.
반응형

조합

조합이란 n 개의 숫자 중에서 r 개의 수를 순서 없이 뽑는 경우를 말한다.

 

(위키백과 - 수학에서 은 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. 그 경우의 수는 이항 계수이다.)

 

예를 들어 [1, 2, 3] 배열에서의 조합은 아래와 같이 나온다.

 

[1, 2]
[1, 3]
[2, 3]

참고

순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다.

말 그대로, 순서가 존재하는 열이라는 것이다.

즉 순열에서 { 1, 2, 3 }과 { 1, 3, 2 } , { 2, 1, 3 } 등 모두 다른 결과를 가져온다. 순서가 다르기 때문이다.

 

조합은 순서가 상관이 없는 모임을 의미한다.

순서가 상관없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은 것으로 취급을 한다.

즉 1, 2, 3 이라는 3개의 숫자로 이루어져 있다는 점에서 똑같은 취급을 하는 것이 조합이다.

설명

조합은 기호 nCr로 나타내며

nCr = n-1Cr-1 + n-1Cr로 나타낼 수 있다.

조합은 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우 이 둘의 합을 나타낸다.

 

예를 들어 (1, 2, 3) 중에서 2개를 뽑는 조합이라고 생각해보면 -> 3C2

  • (1, X) - 1을 뽑는 경우(하나의 원소를 선택할 경우)
  • (X, X) - 1을 뽑지 않는 경우(하나의 원소를 선택하지 않는 경우) 

이처럼 2가지로 나뉠 수 있다.

 

  • 1을 뽑은 경우 나머지 (2, 3) 중 1개를 선택해야 함. (총 2개의 경우 (1, 2) (1, 3)) -> 2C1
  • 1을 뽑지 않은 경우 (2, 3) 모두 선택해야 한다. (총 1개의 경우 (2, 3)) -> 2C2

(1, 2, 3)에서 2개를 뽑는 조합은 둘을 합해 (1, 2) (1, 3), (2, 3) 총 3가지가 된다.

 

이게 이해가 잘 가지 않는 다면 수학에서의 예를 들어보겠다.

 

사과 5개가 있고 각 사과에 1, 2, 3, 4, 5 번호가 적혀있다.

그중에서 3개를 뽑을 것이다.

사과3을 무조건 포함하고 나머지 2개를 뽑으면 4C2일 것이다.

그리고 사과 3을 포함하지 않고 뽑으면 4C3이다.

두 경우를 합하면 결국 사과 5개 중에서 3개를 뽑는 것이 된다. 5C3

(전체에서 - 3이 있는 경우 = 3이 없는 경우 이렇게 생각하면 또 이해하기 쉬워진다!)

 

자 이게 조합의 기본 원리이고 특징이다!

이를 바탕으로 결국 더 이상 쪼개지지 않을 때까지 즉, nC0 = 1이 될 때까지 구한다면 nCr을 구할 수 있게 되는 것이다.

 

이를 코딩으로 구해보자!


1. 조합 경우의 수 구하기

위의 설명을 바탕으로 nCr을 구해보자.

 

3개 중에서 2개를 뽑는 경우를 예를 들어보자.

3C2 = 2C1 + 2C2 >... > 3C0 = 1이 될 때까지 재귀 호출을 통해 구현한다.

 

  • 재귀를 통해 호출을 하다 r == 0이 될 경우, 즉 r개를 다 뽑은 경우는 더 이상 선택의 여지가 없으므로 1을 리턴.
  • 전체 개수n이 뽑아야 할 개수 r과 같아졌다면 역시 다 뽑는 것 말고 선택의 여지가 없으므로 1을 리턴한다.
  • 그 이외에는 원소를 선택할 경우 + 선택하지 않을 경우 둘의 합을 계속 재귀로 호출하면 되는 것이다.

 

public class Combination {

	public static void main(String[] args) {
		System.out.println(combination(3, 2)); //3개중에서 2개를 뽑는 조합의 경우의 수
	}

	public static int combination(int n, int r) {
		if(n == r || r == 0) 
			return 1; 
		else 
			return combination(n - 1, r - 1) + combination(n - 1, r); 
	}
}

2. 조합 구하기(진짜 뽑아진 애들)

이제 조합의 경우의 수 말고 진짜 뽑아져 나온 조합들을 구해보자.

 

조합을 구하는 방법은 배열의 처음부터 마지막까지 돌며

  1. 현재 인덱스를 선택하는 경우
  2. 현재 인덱스를 선택하지 않는 경우

이렇게 두가지로 모든 경우를 완전 탐색하는 것이다.

 

  • arr : 조합을 뽑아낼 배열
  • r : 조합의 길이(뽑을 개수)
  • visited : 조합에 뽑혔는지를 확인하기 위한 배열 

순열과 달리 조합은 r을 유지할 필요가 없으므로 숫자를 하나 뽑을때마다 하나씩 줄여준다.

r == 0 일 때가 r 개의 숫자를 뽑은 경우이다.

 

반복문을 통해 1개부터 배열의 크기까지 돌며 r개를 뽑는다.

 

백트래킹의 방법, 재귀의 방법 두 가지 방법으로 구현하는 법을 알아보자!

 

int[] arr = {1, 2, 3}; //조합을 만들 배열 
boolean[] visited = new boolean[arr.length]; //조합에 뽑혔는지를 확인하기 위한 배열 
 
//1. 백트래킹을 이용해 구현
for(int r = 1; r <= arr.length; r++) { //반복문을 통해 1개부터 배열의 크기 까지 r개를 뽑는다
	comb1(arr, visited, 0, r);
}
        
//2. 재귀를 이용해 구현     
for(int r = 1; r <= arr.length ; r++) {;
       comb2(arr, visited, 0, r);
}

 


2-1. 백트래킹 이용해 구현

start 변수는 기준이다.

start를 기준으로 start 보다 작으면 뽑을 후보에서 제외, start  보다 크면 뽑을 후보가 된다.

 

예를 들어 [1, 2, 3] 배열이 있고 start  0부터 시작한다.

조합을 뽑는 comb 함수에 들어오면 먼저 i 정점부터 시작하는 for 문에 들어간다.

 

만약 0 인덱스에 있는 값 1을 뽑는다면 visited [i]는 true가 되고, 뽑지 않는다면 visited[i] 는 false가 된다.

즉, 1을 선택한 경우(visited[i] = true)와 선택하지 않은 경우(visited[i] = false) 둘 다 봐야 한다.

 

하지만 더 이상 1은 고려 대상이 아니기 때문에 다음 for 문은 2부터 즉, i + 1부터 시작해주어야 한다.

 

static void comb1(int[] arr, boolean[] visited, int start, int n, int r) {
	if(r == 0) {
		print(arr, visited, n);
		return;
	} else {
		for(int i = start; i < n; i++) {
			visited[i] = true;
			comb1(arr, visited, i + 1, n, r - 1);
			visited[i] = false;
		}
	}
}

2-2. 재귀 이용해 구현

depth 변수는 현재 인덱스. 0부터 시작한다.

 

현재 인덱스를 뽑는다면 = true, 뽑지 않는다면 visited[depth] = false로 진행한다.

 

마찬가지로 뽑은 경우와 뽑지 않은 경우 모두 봐야 하고, 그때 이전에 본 값들은 더 이상 고려 대상이 아니기 때문에 depth 은 무조건 1 씩 증가한다.

 

depth == n 이 되면 모든 인덱스를 다 보았으므로(배열의 끝에 도착 -> 조합 만들 수 X) 재귀를 종료한다.

 

또한 r == 0이 되면 뽑을 개수를 다 뽑아 조합이 완성되으니 재귀를 종료한다.

 

 

 

//2. 재귀 사용해 구현 
    static void comb2(int[] arr, boolean[] visited, int depth, int n, int r) {
        if(r == 0) {
            print(arr, visited, n);
            return;
        }
        if(depth == n) {
            return;
        } else {
            visited[depth] = true;
            comb2(arr, visited, depth + 1, n, r - 1);
 
            visited[depth] = false;
            comb2(arr, visited, depth + 1, n, r);
        }
    }

2-1, 2-2 전체 코드

public class Combination {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3}; //조합을 만들 배열 
        boolean[] visited = new boolean[arr.length];
 
        //1. 백트래킹을 이용해 구현
        System.out.println("-------- 1. 백트래킹 ---------");
    
        for(int r = 1; r <= arr.length; r++) {
        	System.out.println("\n" + arr.length + "개 중에 " + r  + "개 뽑음");
            comb1(arr, visited, 0, r);
        }
        
        //2. 재귀를 이용해 구현
        System.out.println("\n---------- 2. 재귀 ----------");
        
        for(int r = 1; r <= arr.length ; r++) {
        	System.out.println("\n" + arr.length + "개 중에 " + r  + "개 뽑음");
            comb2(arr, visited, 0, r);
        }
    }
 
    //1. 백트래킹을 이용해 구현
    static void comb1(int[] arr, boolean[] visited, int start, int r) {
        if(r == 0) {
            print(arr, visited);
            return;
        } else {
            for(int i = start; i < arr.length; i++) {
                visited[i] = true;
                comb1(arr, visited, i + 1, r - 1);
                visited[i] = false;
            }
        }
    }
 
    //2. 재귀를 이용해 구현
    static void comb2(int[] arr, boolean[] visited, int depth, int r) {
        if(r == 0) {
            print(arr, visited);
            return;
        }
        if(depth == arr.length) {
            return;
        } else {
            visited[depth] = true;
            comb2(arr, visited, depth + 1, r - 1);
 
            visited[depth] = false;
            comb2(arr, visited, depth + 1, r);
        }
    }
 
    // 배열 출력
    static void print(int[] arr, boolean[] visited) {
        for(int i = 0; i < arr.length; i++) {
            if(visited[i] == true)
                System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

}

출력

-------- 1. 백트래킹 ---------

3개 중에 1개 뽑음
1 
2 
3 

3개 중에 2개 뽑음
1 2 
1 3 
2 3 

3개 중에 3개 뽑음
1 2 3 

---------- 2. 재귀 ----------

3개 중에 1개 뽑음
1 
2 
3 

3개 중에 2개 뽑음
1 2 
1 3 
2 3 

3개 중에 3개 뽑음
1 2 3 

2-3. 번외 - visited 배열을 쓰지 않고 정수 변수 index로 판별해 구해보기

이 방법은 0~n까지 숫자의 조합을 구하는 방법이다.

그래서 배열은 사이즈 n만큼 그냥 0부터 n까지 채워진다.

코드는 0, 1, 2 3개의 원소에서 2개의 조합을 구한다.

 

index변수는 0부터 시작해 배열의 인덱스를 증가시키면서 해당 인덱스를 뽑을지 안 뽑을지를 결정해 조합을 만들기 위한 변수이다.

(뽑는다면 index + 1, r - 1 / 안 뽑는다면 index 그대로, r 그대로) 

 

target 변수는 0~n까지 나열된 원소 배열 안에서 어떤 숫자를 타깃으로 해 배열에 집어넣을지 고를 때 쓰인다.

combination() 함수가 실행될 때마다 항상 +1씩 해 판별한다.

index 변수에 따라 target에 있는 숫자가 뽑힐지 안 뽑힐지가 결정된다.

target+1이 nCr에서 n-1 -> n-2 -> n-3 ->... -> 1까지 가는 역할을 수행한다.

 

재귀와 그에 대한 종료 조건은 2-2와 같은 방식이다.

 

 

 

public class Combination2 { 
	public static void main(String[] args) { 
		int[] arr = new int[3]; 
		combination(arr, 0, 3, 2, 0);
	} 
	public static void combination(int[] arr, int index, int n, int r, int target) { 
		if (r == 0) 
			print(arr, index); 
		else if (target == n) 
			return; 
		else { 
			arr[index] = target;
			combination(arr, index + 1, n, r - 1, target + 1); 
			combination(arr, index, n, r, target + 1); 
		} 
	}
	
	//배열 출력 
	public static void print(int[] arr, int length) {
		for (int i = 0; i < length; i++) 
			System.out.print(arr[i] + " ");
		System.out.println(""); 
	} 
}

코멘트

구현하는 2-1, 2-2, 2-3번은 원리가 똑같은 다 비슷한 코드이다.

정리하면서 여러 가지 방법들을 써놓은 것이다.

그래서 세 개다 비슷한 말을 좀 다르게 하는 것인데,

나는 이렇게 3개의 다른 코드들을 적어보고 디버그 해보면서 조합에 대해 더 확실히 알 수 있어서 이렇게 정리한다!


연습문제

www.acmicpc.net/problem/2309


GITHUB

github.com/KwonMinha/Algorithm/blob/master/Permutaion_Combination/src/Combination.java

 

KwonMinha/Algorithm

Contribute to KwonMinha/Algorithm development by creating an account on GitHub.

github.com

관련 포스트

[Java] 순열 Permutation

추천 포스트

Java로 작성된 조합, 중복 조합, 순열, 중복 순열과 관련된 포스트이다.

LinkedList 사용해 구현되었고 리스트 안에 n까지 값이 순서대로 주어진다.

예를 들어  input : 3 2 라면

(0, 1, 2) 3개의 리스트가 생성되고, 그중 2개를 뽑아 조합, 중복 조합, 순열, 중복 순열을 만든다.

 

limkydev.tistory.com/178 [[Java] 조합, 중복 조합, 순열, 중복순열 소스]
import java.util.LinkedList;
import java.util.Scanner;
 
public class PerComb {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //숫자 개수 
        int r = sc.nextInt(); //뽑을 개수 
        
        System.out.println("원소 개수 : " + n + ", 뽑을 개수 : " + r);
        System.out.print("( ");
        for(int i = 0; i < n; i++) {
        	System.out.print(i + " ");
        }
        System.out.println(")");
         
        //순열 (순서있게 배열)
        System.out.println("\n순열");
        LinkedList<Integer> perArr = new LinkedList<Integer>(); 
        int[] perCheck = new int[n];
        permutation(n, r, perArr, perCheck);
        
        //중복순열 (순서있게 배열 + 자기 자신도 포함)
        System.out.println("\n중복순열");
        LinkedList<Integer> rePerArr = new LinkedList<Integer>();   
        rePermutation(n, r, perArr);
         
        //조합 (순서 관심 없고 뽑은 유무만 생각)
        System.out.println("\n조합");
        int[] comArr = new int[r];
        combination(comArr, n, r, 0, 0);
        
        //중복 조합 (순서 관심 없고 뽑은 유무만 생각 + 자기 자신도 포함)
        System.out.println("\n중복조합");
        int[] reComArr = new int[r];
        reCombination(reComArr, n, r, 0, 0);
    }
    
    //순열(순서있게 배열)
    private static void permutation(int n, int r, LinkedList<Integer> perArr, int[] perCheck) {
        if(perArr.size() == r){
            for(int i : perArr){
                System.out.print(i+" ");
            }
            System.out.println();
            return;
        }
        for(int i=0; i<n; i++){
            if(perCheck[i] == 0){
                perArr.add(i); //값을 넣는 부분 
                perCheck[i] = 1;
                permutation(n, r, perArr, perCheck);
                perCheck[i] = 0;
                perArr.removeLast();
            }
        } 
    }
    
    //중복순열 (순서있게 배열 + 자기 자신도 포함)
    private static void rePermutation(int n, int r, LinkedList<Integer> rePerArr) {
        if(rePerArr.size() == r){
            for(int i : rePerArr){
                System.out.print(i+" ");
            }
            System.out.println();
            return;
        }
         
        for(int i=0; i<n; i++){  
            rePerArr.add(i);
            rePermutation(n, r, rePerArr);
            rePerArr.removeLast();
        } 
    }
    
    //조합 (순서 관심 없고 뽑은 유무만 생각)
    private static void combination(int[] comArr, int n, int r, int index, int target) {
        if(r==0){
            for(int i : comArr){
                System.out.print(i+" ");
            }
            System.out.println();
            return;
        }
        if(target == n)return;
         
        comArr[index] = target;
        combination(comArr, n, r-1, index+1, target+1); //뽑는 경우
        combination(comArr, n, r, index, target+1); //안 뽑는 경우   
    }
    
    //중복 조합 (순서 관심 없고 뽑은 유무만 생각 + 자기 자신도 포함)
    private static void reCombination(int[] reComArr, int n, int r, int index, int target) {
        if(r==0){
            for(int i : reComArr){
                System.out.print(i+" ");
            }
            System.out.println();
            return;
        }       
        if(target == n)return;
         
        reComArr[index] = target;
        reCombination(reComArr, n, r-1, index+1, target);//뽑는 경우
        reCombination(reComArr, n, r, index, target+1);//안 뽑는 경우
    }
 
}

참고

 [조합 Combination (Java)]
gorakgarak.tistory.com/523 [조합 Combination 알고리즘]
woongsios.tistory.com/179 [Combination 조합]
반응형

댓글