조합

구현 방식

조합 구현 방식은 크게 2가지가 있습니다. 

 

1. 재귀만 쓰는 방식

private static void comb1(int selectIdx, int elementIdx) {
    if(selectIdx == m) {
        for(int num : select) {
            sb.append(num).append(" ");
        }
        sb.append("\n");
        return;
    }
	
    // 재귀만 쓰는 방식
    if(elementIdx == n+1) return;

    // 선택하고 넘어감
    select[selectIdx] = elementIdx;
    comb1(selectIdx+1,elementIdx+1);

    // 선택 안하고 넘어감
    select[selectIdx] = -1;
    comb1(selectIdx,elementIdx+1);		
}

 

2. 반복문에 재귀를 쓰는 방식

private static void comb2(int selectIdx, int elementIdx) {
    if(selectIdx == m) {
        for(int num : select) {
            sb.append(num).append(" ");
        }
        sb.append("\n");
        return;
    }
	
    // 반복문에 재귀를 쓰는 방식
    for(int i=elementIdx;i<=n;i++) {
        select[selectIdx] = i;
        comb2(selectIdx+1,i+1);
    }

}

 

---

성능 비교

20C10인 경우를 아래와 같이 시간을 측정하는 코드를 추가하여 비교해보았습니다.

 

public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    n = Integer.parseInt(br.readLine()); // 요소 개수
    m = Integer.parseInt(br.readLine()); // 뽑는 개수
    int k = Integer.parseInt(br.readLine()); // 종류
    select = new int[m];
    visited = new boolean[n+1];
	
    long startTime = System.nanoTime(); // 시작 시각
    
    // 조합
    switch(k) {
    case 1:
        comb1(0,1);
        break;
    case 2:
        comb2(0,1);
        break;
    default:
        break;
    }

    long endTime = System.nanoTime(); // 끝 시각
    long duration = endTime - startTime; // 함수 실행 시간

    // 출력
    System.out.println(sb);
    System.out.println(duration);
    br.close();
}

 

실행 결과

• 1. 재귀만 쓰는 방식 : 65958200
• 2. 반복문에 재귀를 쓰는 방식 : 56975400

 

유의미한 차이가 발생합니다. 왜 그럴까요?

 

---

원인 분석

• 1번 방식 : 범위 밖 까지 탐색한 뒤, 범위 밖이라는 것을 판단하고 return을 하는 방식입니다. 
• 2번 방식 :  for문으로 범위를 지정했기 때문에 범위 밖은 탐색하지 않습니다. 

---

결론

조합을 쓸 때에는 2번 방식(반복문에 재귀를 쓰는 방식)을 사용합시다.

private static void comb2(int selectIdx, int elementIdx) {
    if(selectIdx == m) {
        for(int num : select) {
            sb.append(num).append(" ");
        }
        sb.append("\n");
        return;
    }
	
    // 반복문에 재귀를 쓰는 방식
    for(int i=elementIdx;i<=n;i++) {
        select[selectIdx] = i;
        comb2(selectIdx+1,i+1);
    }

}