안녕하세요 이번 시간에는 순열과 조합에 대해 알아보는 시간을 갖도록 하겠습니다.
n개의 수 중 r개를 뽑는 순열과 조합은 수학적으로 다음과 같습니다.
순열 nPr = n!/(n-r)!
조합 nCr = n!/((n-r)! x r!)
순열을 구현하는 방법을 백준 1722(순열의 순서) 문제를 통해 구현해보겠습니다. 임의의 순열이 주어졌을 때 몇 번째 순열인지 구하고, 순서가 주어졌을 때 그 순열을 출력하는 문제입니다.
먼저 1부터 채워지는 순열의 크기가 N이라고 할 때 K번째 수열을 출력해보겠습니다. 수열을 구하는 프로세스는 다음과 같습니다.
- 순열의 각 자릿수에 따른 경우의 수를 저장합니다
--> 가장 앞 순열의 경우 자기 자신을 제외한 N-1개의 수들을 정렬하는 경우의 수이기 때문에 N-1!, 가장 마지막 순열의 경우 앞에서 모든 수가 결정되므로 1 - 현재 수열의 위치에서 만들 수 있는 수열의 개수를 K에서 빼주면서 K가 만들 수 있는 수열 개수보다 작아졌을 때의 인덱스 값을 수열에 값으로 설정
--> 가장 앞 수가 만들 수 있는 수열의 개수는 N-1!이므로 cnt만큼 N-1!을 K에서 빼주면 현재 자리 수보다 작은 수들이 만들 수 있는 수열의 개수를 빼주기 때문에 이렇게 뺀 K값이 빼준 횟수 x 각 수가 만들 수 있는 수열 개수보다 작다면 현재 자리는 K값이 빼준 횟수를 값으로 가지게 됨 - 현재 자릿수 계산을 완료한 후 check를 true로 처리합니다.
--> 이미 체크가 되어 있는 경우 해당 숫자를 수열에서 사용한 것이기 때문에 cnt를 증가시키지 않습니다. - 모든 자릿수에 대해 반복한 후 완성된 수열을 출력합니다.
순열이 주어졌을 때 이 순열이 몇 번째 순서를 가지는지는 위의 방법을 역으로 진행하면 됩니다.
- 이전 자리 수에 존재할 수 있는 순열의 개수를 K에 지속적으로 더해줍니다.
--> 입력된 수열의 가장 앞 자리의 수보다 작은 수로 시작하는 수열이 각각 N-1!개 만큼 존재, 즉 현재 자리수보다 작은 수의 개수 x 각 수가 만들 수 있는 수열 개수를 지속적으로 더해줍니다. - 현재 자릿수 계산을 완료한 후 check를 true로 처리합니다.
- 모든 자릿수에 대해 반복한 후 K를 출력합니다.
import java.util.*;
import java.io.*;
class Main{
static int N,Q;
static long[] F = new long[21];
static int[] S = new int[21];
static boolean[] check = new boolean[21];
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
F[0] = 1;
for(int i=1;i<=N;i++) F[i] = F[i-1]*i;
Q = Integer.parseInt(st.nextToken());
if(Q == 1){
long K = Long.parseLong(st.nextToken());
for(int i=1;i<=N;i++){
for(int j=1, cnt=1; j<=N;j++){
if(check[j]) continue;
if(K <= cnt * F[N-i]){
K -= ((cnt-1)*F[N-i]);
S[i] = j;
check[j] = true;
break;
}
cnt++;
}
}
for(int i=1;i<=N;i++) System.out.print(S[i]+" ");
}
else{
long K = 1;
for(int i=1;i<=N;i++){
S[i] = Integer.parseInt(st.nextToken());
long cnt = 0;
for(int j=1;j<S[i];j++) if(!check[j]) cnt++;
K += cnt*F[N-i];
check[S[i]] = true;
}
System.out.println(K);
}
}
}완전 순열, 즉 N개의 원소의 집합에서 원소들을 재배열할 때 이전과 같은 위치에 배치되는 원소가 1개도 없는 경우일 때 다음의 점화식을 통해 값을 유추할 수 있습니다.
dp[N] = (N-1) x (dp[N-2] + dp[N-1])
백준 1947(선물 전달) 문제를 통해 완전 순열을 구현해보겠습니다. 모든 사람들이 각자 선물을 준비했을 떄 선물을 나누는 경우의 수를 구하는 문제입니다. 여기서 주의할 점은 dp 배열의 크기를 N+1이 아닌 N의 최대 범위값으로 설정해야 합니다.
import java.util.*;
import java.io.*;
class Main{
static long MOD = 1000000000;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long[] dp = new long[1000001];
dp[1] = 0;
dp[2] = 1;
for(int i=3;i<=N;i++) dp[i] = (i-1)*(dp[i-2]+dp[i-1])%MOD;
System.out.println(dp[N]);
}
}조합의 경우 다음의 점화식으로 표현 가능합니다.
dp[N][R] = dp[N-1][R] + dp[N-1][R-1]
이 때 dp[i][1] = i, dp[i][0] = 1, dp[i][i] = 1로 초기값을 정의합니다.
백준 11051(이항 계수 2) 문제를 통해 조합을 구현해보겠습니다. 자연수 N과 정수 K가 주어졌을 때 이항계수를 구하는 문제로, 이항 계수를 조합으로 표현할 수 있기 때문에 조합을 구하는 문제와 같습니다. 배열은 N+1, N+1의 크기로 초기화한 후 i는 2부터 N까지, j는 1부터 i보다 작을때까지 반복하여 dp[i][j]를 채웁니다.
import java.util.*;
import java.io.*;
class Main{
static int[][] dp;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
dp = new int[N+1][N+1];
for(int i=1;i<=N;i++){
dp[i][0] = 1;
dp[i][1] = i;
dp[i][i] = 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])%10007;
}
}
System.out.println(dp[N][K]);
}
}