[알고리즘/Java] 순열과 조합

순열과 조합에서 사용되는 재귀의 개념에 대해 간단히 정리하고 시작하겠다.

재귀란?

어떤 개념이나 문제에 대한 정의를 그 개념이나 문제를 포함하는 작은 개념이나 부분문제로 나타내고

더 이상 작은 개념, 부분문제가 없을 때 재귀의 끝으로 설정하는 것

 

재귀 함수 작성시 주의 할점

• 함수에 대한 정의를 명확하게!
• 함수 수행에 필요한 결정적 요인, 값 설계
• 재귀 종료조건 따지기

 

함수 호출은 프로그램 메모리 구조에서 스택을 사용한다.

 

순열과 조합

순열(Permutation)

nPr n개의 숫자 중에서 r개를 뽑는데 순서를 고려하여 나열하는 경우의 수를 뜻한다.

 

즉 순서와 각 자리의 의미가 있다면 순열, 해당 조건이 의미가 없다면 조합으로 분류한다.

조합에서는 1, 2, 3과 3, 2, 1이 다른 경우의 수로 처리되지만 순열에서는 같은 것으로 분류된다는 뜻이다.

 

예를 들기 위해서 주사위를 3번 던져서 나올 수 있는 경우의 수를 구한다고 가정한다.

 

static void dice1(int cnt) { 
	if(cnt == N) { //N번 던졌기 때문에 재귀의 종료
		System.out.println(Arrays.toString(numbers));
		return;
	}
	for(int i = 1; i <= 6; i++) {
		numbers[cnt] = i;
		dice1(cnt + 1); //다음 숫자 고르러 감
	}
}

 

위 코드에서 N은 몇번 던질 것인지에 대한 변수로 3번 던진다면 N=3이 될것이다.

numbers는 뽑은 주사위의 숫자가 저장될 배열이다.

주사위의 눈은 1부터 6까지 있기 때문에 for문으로 1~6이라는 경우의 수를 모두 넣는 것이다.

이의 경우 중복 순열로 만약 이전에 뽑은 수와 같은 수가 나온다면 다시 주사위를 굴린다는 조건을 추가한다면?

static void dice2(int cnt) {
	if(cnt == N) {
		System.out.println(Arrays.toString(numbers));
		return;
	}
	for(int i = 1; i <= 6; i++) {
		if(!isSelected[i]) {
			numbers[cnt] = i;
			isSelected[i] = true;
			dice2(cnt + 1);
			isSelected[i] = false;
		}
	}
}

 

앞선 코드와 다르게 isSelected 배열이 추가 되었다.

이미 이 수가 선택된 상태라면 건너뛰고 다음 경우의 수를 고려한다.

재귀를 부른 후 다시 돌아왔을 때 isSelected를 false로 바꿔주는 이유는

다음 경우의 수를 계산할 때 다른 칸에는 해당 숫자가 들어올 수 있기 때문이다.

 

조합(Combination)

nCr n개의 숫자 중에서 r개를 뽑는 경우의 수를 뜻한다.

조합은 순열과 달리 순서를 고려하기 때문에 1, 2, 3과 3, 2, 1은 같은 경우로 분류가된다.

위의 예시에 이어서 계속 코드를 작성해보겠다.

static void dice3(int cnt, int start) {
	if(cnt == N) {
		System.out.println(Arrays.toString(numbers));
		return;
	}
	//시작점부터 가능한 끝가지 선택하는 시도
	for(int i = start; i <= 6; i++) {
		numbers[cnt] = i; //선택한 수 저장
		dice3(cnt + 1, i); //현재 선택한수부터 선택하도록 시작점 주기
	}
}

 

중복 조합에 대한 코드로 순열과 달리 start라는 인자가 추가 되었다.

앞서 말했듯 순서가 고려되지 않기 때문에 앞에서 고른 수는 선택 되면 안된다.

따라서 현재까지 선택한 수가 어디까지였는지 함께 전달할 필요가 있다.

 

private static void dice4(int cnt, int start) {
	if(cnt == N) {
		System.out.println(Arrays.toString(numbers));
		return;
	}
	//시작점부터 가능한 끝가지 선택하는 시도
	for(int i = start; i <= 6; i++) {
		numbers[cnt] = i; //선택한 수 저장
		dice4(cnt + 1, i + 1); //현재 선택한수의 다음 부터 선택하도록 시작점 주기
	}
}

 

중복조합과 달리 앞에서 1이 선택되었다면 다음 수는 1을 제외한 나머지 수가 선택되어야 하므로 재귀를 부를때 i+1과 같이 인자를 넘겨주게된다.

조합의 점화식

6C3을 구해야할 때

마지막 데이터 한개 선택 여부에 따라 경우의 수를 계산한다.

위 그림 같은 경우 빈칸에 마지막 데이터 6이 들어간다면

6을 제외한 나머지 1, 2의 경우 빨간색으로 표시한 부분의 5개 데이터 중 2개를 선택하는 경우가 된다.

 

하지만 빈칸에 마지막 데이터 6이 아니라 1, 2, 3, 4, 5중 하나를 넣는다면

5개 데이터 중 3개를 선택하는 경우가 된다.

이를 식으로 표현하게되면

 

6C3 = 5C2 + 5C3과 같은 상태가 된다.

 

점화식으로 표현하면

nCr = n-1Cr-1 + n-1Cr

로 나타낼 수 있다.

+로 알아두면 좋은 개념

nC1 = n

nC0 = 1

nCn = 1

 

위 개념으로 (N+1) * (N+1) 2차원 배열을 생성해 모든 조합의 수를 저장하고

dp문제를 풀때 활용할 수 있다.

for(int i = 0; i <= N; i++) {
	dp[i][0] = 1; //nC0 = 1개
	dp[i][1] = i; //nC1 = n개
	dp[i][i] = 1; //nCr(n==r) = 1개
}
for(int i = 2; i <= N; i++) {
	for(int j = 1; j <= i; j++) {
		dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
		dp[i][j] = dp[i][j];
	}
}

 

결과는 위와같은 배열이 생성된다. 회색 부분은 총 개수보다 선택 수가 더 클 수 없기 때문에 처리되지 않는 부분이다.