Algorithm[Java] | 완전탐색 - 조합

오늘은 조합적 문제에서 활용할 수 있는 순열,조합,부분집합 중 조합에 대해서 알아보겠습니다.

조합

▪️ 서로 다른 n개의 원소 중 r개를 순서 없이 골라내는 것
▪️ nCr = n-1Cr-1 + n-1Cr
▪️ nC0 = 1

💡 중복 조합, 조합 구현

조합

1. 재귀 활용하는 방법

⭐️ 중복 순열 코드에서 재귀 매개변수로 start를 넣어주고, for문에서 i=start 부터 시작해주면서 재귀 호출시 start 매개변수에 i+1을 넘겨주면 조합 코드가 됩니다!
⚠️ 재귀 호출시 i+1을 넘겨줘야하는데 start를 넘기는 실수 ❌

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class CombinationTest {

	public static int n,r;
	public static int [] picked; // 뽑힌 값들 저장할 배열 
	public static int [] arr;

	public static void combination(int cnt,int start) { 
		// 기저조건 : cnt==r
		if(cnt==r) {
			System.out.println(Arrays.toString(picked));
			return;
		}

		for(int i=start;i<n;i++) { // start 매개변수를 기준으로 start 보다 작으면 뽑을 후보에서 제외 
			picked[cnt]=arr[i]; //i번째 원소를 cnt번째에 넣음 -> picked[cnt]에 넣음 
			combination(cnt+1,i+1); // 다음 cnt+1번째 선택하기 위해 재귀 호출 진행 
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		arr = new int [] {1,2,3,4,5,6};
		n = arr.length; // 배열의 길이가 n 
		r = Integer.parseInt(br.readLine()); // n개 중 뽑아야할 개수 r개 
		picked = new int[r]; // r개 뽑아야 하므로 r개로 초기화 

		// nCr 시작! 
		combination(0,0);
	}

}

넥퍼를 활용하는 방법

package Combination정리;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class CombinationNPTest {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int arr[] = new int [] {1,2,3,4,5,6};
		int n = arr.length;
		int R = Integer.parseInt(br.readLine()); // 몇개를 뽑을 거니?
		int p[] = new int[n];
		
		int cnt = 0;
		while(++cnt <= R) p[n-cnt]=1; // 뒤에서부터 1 채우기
		
		do {
			// p 배열을 이용한 조합 확인
			for (int i = 0; i < n; i++) {
				if(p[i]==0) continue;
				System.out.print(arr[i] + "\t");
			}
			System.out.println();
		}while(np(p));
		
	}
	
	public static boolean np(int[] p) { // p : 다음 순열을 원하는 기존 순열의 배열
		//1. 맨뒤쪽부터 탐색하며 꼭대기 찾기
		int n = p.length;
		int i = n-1; // 맨 뒤에서 찾음 
		while(i>0 && p[i-1]>=p[i]) --i;
		
		if(i==0) return false; // 다음 순열은 없음(가장 큰 순열의 형태)
		
		// 2. 꼭대기 직전(i-1) 위치에 교환할 한단계 큰 수 뒤쪽부터 찾기
		int j=n-1; // 맨 뒤에서 찾음 
		while(p[i-1] >= p[j]) --j;
		
		// 3. 꼭대기 직전(i-1) 위치의 수와 한 단계 큰 수를 교환하기
		swap(p,i-1,j);
		
		// 4. 꼭대기 자리 부터 맨 뒤까지의 수를 오름차순의 형태로 바꿈
		int k = n-1; // 맨 뒤에서 찾음 
		while(i<k) {
			swap(p,i++,k--);
		}
		return true; // 순열 완성했다고 말해줌.
	}
	
	public static void swap(int[] p, int a, int b) {
		int temp = p[a];
		p[a]=p[b];
		p[b]=temp;
	}
}

중복 조합

⭐️ 조합 코드에서 재귀 호출시 start 매개변수에 i+1 대신 i를 넘겨주면 중복 조합 코드가 됩니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class CombinationTest {

	public static int n,r;
	public static int [] picked; // 뽑힌 값들 저장할 배열 
	public static int [] arr;

	public static void combination(int cnt,int start) { 
		// 기저조건 : cnt==r
		if(cnt==r) {
			System.out.println(Arrays.toString(picked));
			return;
		}

		for(int i=start;i<n;i++) { // start 매개변수를 기준으로 start 보다 작으면 뽑을 후보에서 제외 
			picked[cnt]=arr[i]; //i번째 원소를 cnt번째에 넣음 -> picked[cnt]에 넣음 
			combination(cnt+1,i); // 다음 cnt+1번째 선택하기 위해 재귀 호출 진행 
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		arr = new int [] {1,2,3,4,5,6};
		n = arr.length; // 배열의 길이가 n 
		r = Integer.parseInt(br.readLine()); // n개 중 뽑아야할 개수 r개 
		picked = new int[r]; // r개 뽑아야 하므로 r개로 초기화 

		// nCr 시작! 
		combination(0,0);
	}
}