combination

🙋‍♂️ 들어가며

조합을 볼까?

아래 Java 코드는 back-tracking 관점에서 접근한 핵심 풀이입니다. 입력 조건과 시간·공간 복잡도를 함께 고려하여 불필요한 연산을 줄이는 방향으로 설계했습니다.

n = 10
r = 5

위 구현은 combination의 제약 조건을 만족하도록 자료구조 선택과 반복 범위를 최적화한 결과입니다.

${}{n}C{r}$ = 252

여기서 조합을 구현할 수 있는 방법은 다음과 같다

1. 백트랙킹
2. 비스마스킹

그런데 2개는 연산횟수의 차이가 있다.

백트랙킹의 경우 252가지

비트마스킹은 $2^{10}$ -> 1024

그래서 백트랙킹 조합이 훨씬 낫다.

백트랙킹 조합 작동방식

이런식으로 조합의 갯수를 구한다.

✅ 코드

package boj;

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

import java.util.Arrays;


public class Main {
	static int n;
	static int r;
	static int[] possible_code; 
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = 10;
		r = 5;
		possible_code = new int[r];
		
		comb(1,0);
	}
	
	
	static void comb(int start, int depth) {
		// 최대 깊이 도달시
		if (depth == r) {
			System.out.println(Arrays.toString(possible_code));
			return;
		}
		
		// 아직 못 도달했다면
		for (int i = start; i < n+1; i++) {
			possible_code[depth] = i;
			comb(i+1, depth+1);
		}
		
	}
	
		
	
}

이 코드를 보고 이해가 안간다면 아래 글을 참고하자

arr[0] = 7

여기서부터 사실상 나가리 -> 다 조합해도 5개가 안된다

그 외에 arr[0] = 10인 경우에는

comb(11, 1) 인데 다음 재귀부터는

for (int 11 = start, i < 11; i++)

이라서 사실상 arr[1]부터는 들어올 수가 없다