오늘은 조합 (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)를 호출하는 것은
동일하나 이후 메커니즘에서 이전에 뽑은 부품을 처리하는 방법에 있어서 차이가 있습니다.
직접 스택형태의 구조를 그려 이해해보시는 것을 추천드립니다!
읽어주셔서 감사합니다.
'알고리즘 > 개념정복' 카테고리의 다른 글
프림, 다익스트라 알고리즘에 대하여.java (0) | 2024.03.28 |
---|---|
분할정복(Divide and Conquer) 알고리즘에 대하여.java (0) | 2024.03.04 |
부분집합(Powerset)에 대하여.java (0) | 2024.03.02 |
백트래킹(backtracking)에 대하여 (N-Queen).Java (0) | 2024.02.29 |
완전탐색의 한 종류 BFS에 대하여 (0) | 2024.02.19 |