조합(Combination)에 대하여.java

오늘은 조합 (Combination)에 대해 포스팅하도록 하겠습니다.

 

학창시절 순열과 조합시간에 배우셨겠지만

개념을 한 번 더 짚고 넘어가볼게요.

 

#조합 📝

nCr : 서로 다른 N개 중 순서의 관계없이 r개를 뽑는 경우의 수

 

뽑는 순서의 관계없다는 것은, 뽑힌 두 원소들의 위치가 구분되지 않는다는 뜻입니다.

이는 순열과는 구분되는 조합의 중요한 특성입니다.

 

그럼 재귀함수를 활용한 구현 코드를 볼까요?

 

#구현_재귀함수1 💻

함수호출 부분 N-R+sidx를 통해 sidx에 따른 반복문의 구간을 변경시키는 것이 핵심 로직입니다.

import java.util.Arrays;

public class 조합1재귀함수 {
	// 데이터 배열
	static String[] 자동차부품 = {"토크컨버터","터보자처부품","도어모듈","브레이크패드"};
	static int N, R;
	static String[] selected;
	public static void main(String[] args) {
		N = 4;
		R = 2;
		selected = new String[R]; //뽑을 갯수만큼의 배열 크기 할당하기
		combination(0,0);
	}
	
	//idx : 현재 내가 판단할 부품
	//sidx : 조합할 부품의 인덱스, R개일때까지 확인하기
	public static void combination(int idx, int sidx) {
		//기저조건
		if(sidx >= R) {
			System.out.println(Arrays.toString(selected));
			return;
		}
		//함수호출하기
		for(int i = idx; i<= N-R+sidx; i++) { //sidx로 뽑을 범위를 조절하여, 효율적인 조합 구현
			selected[sidx] = 자동차부품[i]; //부품 뽑아보자
			combination(i+1, sidx+1);
		}
	}

}

 

 

#구현_재귀함수2 💻

다음으로

함수를 연속으로 호출하여, 구현하는 방법입니다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 조합2재귀함수반복문 {
	// 데이터 배열
	static String[] 자동차부품 = {"토크컨버터","터보자처부품","도어모듈","브레이크패드"};
	static int N, R;
	 static String[] selected;
	static List<String[]> list = new ArrayList<>();
	public static void main(String[] args) {
		N = 4;
		R = 2;
		selected = new String[R];
		combination(0,0);
		System.out.println("------------------");
		for(String[] s : list) { //리스트에 담아서 출력하기
			System.out.println(Arrays.toString(s));
		}
	}
	//idx : 현재 내가 판단할 재료
	//sidx : 조합할 재료의 인덱스
	public static void combination(int idx, int sidx) {
		//base case
		if(sidx >= R) {// 원하는 만큼 뽑았어!
			String[] tmp = new String[R]; //기저조건마다 tmp의 값이 달라짐
			for(int i = 0 ; i<R; i++) {
				tmp[i] = selected[i];
			}
			System.out.println(Arrays.toString(selected)); //selected가 매번 바뀌니,
			// 모든 경우의 수 보고 싶을 땐 기저조건마다 출력하기!
			list.add(tmp); // list에 담아서, 원소로 넣고 싶을 땐 이렇게 !
			return;
		}
		if(idx == N) { //부품 전부 확인했어
			return;
		}
		//recursive case
		selected[sidx] = 자동차부품[idx];
		combination(idx+1, sidx+1); //해당 idx번째 부품 sidx 위치에 넣기
		combination(idx+1, sidx); //해당 idx번째 재료 sidx 위치에 넣기
		
	}
}

 

 

두 구현 모두  메서드 combination(idx+1, sidx+1)를 호출하는 것은

동일하나 이후 메커니즘에서 이전에 뽑은 부품을 처리하는 방법에 있어서 차이가 있습니다.

 

직접 스택형태의 구조를 그려 이해해보시는 것을 추천드립니다!

 

읽어주셔서 감사합니다.