오늘은 코딩테스트에서 자주 마주치는 순열과 조합에 대해서 정리해보려한다.
순열
순열은 서로다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것이다.
이를 식으로 나타내면
nPn=n!(Factorial)
으로 나타낼 수 있다.
예시로 nP3을 구현해보자면, 순열의 반복적인 일은 숫자를 한개씩 뽑는일이다.
가능한 모든 수를 시도하면서 기존 수와 중복되지 않게 하나의 수를 선택한다.
이는 3중 for문을 사용해서 구현할 수 있다.
하지만 3처럼 숫자가 정해지지 않는다면, for문의 갯수를 알 수 없으므로 구현할 수 없다.
이 상황에서는 재귀를 사용해서 순열을 구현한다.
- 재귀로 구현하기
p메소드에서는 순열에 포함될 수를 하나씩 뽑는다.
p메소드에서 해야될 일을 다음과 같다.
1. 가능한 모든 수를 시도
2. 다음수 뽑으러가기 ->여기서 재귀호출 일어남
달라지는 부분은 이 재귀의 결정요인 값이다. 즉, 이는 파라미터로 사용한다.
뽑힌 수가 저장될 자리(뽑는 순서)
i는 뽑을 숫자이고, cnt는 현재 뽑은 숫자의 갯수이다.
슈도 코드로 정리하면 아래와 같다.
numbers[] //순열 저장 배열
isSelected[] //인덱스에 해당하는 숫자가 사용 중인지 저장하는 배열perm(cnt) //cnt-현재까지 뽑은 순열 수의 개수
if cnt == 3
순열 생성 완료
else
for i from 1 to 3
if isSelected[i] == true then continue //다음 i로 감 다른 숫자 뽑아
numbers[cnt] <- i //몇번째 수 뽑을건지. 현재 뽑은 수를 사용해서 인덱스로 활용해서 숫자 뽑기
isSelected[i]<-true //이수 뽑았어요
perm(cnt+1) //재귀호출. 여기까지 뽑았어요
isSelected[i]<-false // 초기화
end forpackage algorithm;
import java.util.Arrays;
import java.util.Scanner;
public class PermutationTest1 {
static int N,R, totalCnt;
static int[] numbers;
static boolean[] isSelected;
//nPn: 1부터 n까지의 수중에 n개를 모두 뽑아 순서적으로 나열한 것
//nPr: 1부터 n까지의 수중에 r개를 모두 뽑아 순서적으로 나열한 것(1<=r<=n)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
R = sc.nextInt();
totalCnt=0;
numbers = new int[R];//뽑힌애들
isSelected = new boolean[N+1]; //수가 1부터 시작해서 인덱스도 1부터 논리적 매칭 사용
perm(0);
System.out.println("총 경우의 수:"+totalCnt);
}
private static void perm(int cnt) {
// cnt: 직전까지 뽑은 순열에 포함된 수의 개수, cnt+1 번째 해당하는 수를 뽑기
//가능한 모든 수에 대해 시도
if(cnt==R) {
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
for(int i=1; i<=N; i++) {
//시도하는 수가 선택되었는지 판단
if(isSelected[i]) continue;
//선택되지 않았다면 수를 사용
numbers[cnt]=i;
isSelected[i]=true;
//다음수 뽑으러 가기
perm(cnt+1);
//사용했던 수에 대한 선택 되돌리기
isSelected[i]=false;
}
}
}import java.util.Arrays;
import java.util.Scanner;
public class PermutationTest2 {
static int N,R, totalCnt;
static int[] numbers, input;
static boolean[] isSelected;
//nPn: n개의 입력받은 수중에 n개를 모두 뽑아 순서적으로 나열한 것(입력수 1~100000)
//nPr: n개의 입력받은 수중에 r개를 모두 뽑아 순서적으로 나열한 것(1<=r<=n)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
R = sc.nextInt();
totalCnt=0;
input = new int[N];
numbers = new int[R];//뽑힌애들
isSelected = new boolean\[N\];
for (int i = 0; i <N; i++) {
input[i]=sc.nextInt();
}
perm(0);
System.out.println("총 경우의 수:"+totalCnt);
}
private static void perm(int cnt) {
// cnt: 직전까지 뽑은 순열에 포함된 수의 개수, cnt+1 번째 해당하는 수를 뽑기
//가능한 모든 수에 대해 시도
if(cnt==R) {
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
//
for(int i=0; i<N; i++) {
//시도하는 수가 선택되었는지 판단
if(isSelected[i]) continue;
//선택되지 않았다면 수를 사용
numbers[cnt]=input[i];
isSelected[i]=true;
//다음수 뽑으러 가기
perm(cnt+1);
//사용했던 수에 대한 선택 되돌리기
isSelected[i]=false;
}
}
}순열로 문제를 풀기 위해서는 10!정도 까지만 가능하다.
n의 크기가 10정도 일때까지 가능하다.
그거보다 크다면 순열로 푸는 문제가 아닐 가능성이 높다.
순열과 같이 나오는 개념에는 조합이 있다.
조합
서로다른 n개의 원소 중 r개를 순서 없이 골라낸 것
nCn/2개의 경우의 수가 가장 크다.
N->30, R->5정도면 조합으로 풀 수없다.
nCr=n-1Cr-1+n-1Cr
nCr=n! / r!(n-r)!
->n부터 1씩 줄어들면서 r개를 곱함/1부터 1씩 늘어나면서 r개를 곱함
슈도코드로 나타내면 아래와 같다.
for i from 1 to 4
for j from i+1 to 4
for k from j+1 to 4
print i,j,k
end for
end for
end forinput[] : n개의 원소를 가지고 있는 배열
numbers[] : r개의 크기의 배열, 조합이 저장될 배열
comb(cnt, start)
if cnt == r
조합 생성 완료
else
for i from start to n-1 //이전 수 다음부터
numbers[cnt]<-input[i];
comb(cnt+1, i+1);
end forpackage algorithm;
import java.util.Arrays;
import java.util.Scanner;
public class CombinationTest {
static int N,R, totalCnt;
static int[] numbers, input;
//nCr: n개의 입력받은 수중에 r개를 모두 뽑아 순서없이 나열한 것(1<=r<=n)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
R = sc.nextInt();
totalCnt=0;
input = new int[N];
numbers = new int[R];//뽑힌애들
for (int i = 0; i <N; i++) {
input[i]=sc.nextInt();
}
comb(0,0);
System.out.println("총 경우의 수:"+totalCnt);
}
//cnt+1번째 해당하는 조합에 포함도리 수를 뽑기
private static void comb(int cnt,int start) {
// cnt: 직전까지 뽑은 순열에 포함된 수의 개수, start: 시도할 수의 시작 위치
if(cnt==R) {
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
//가능한 모든 수에 대해 시도(input배열의 가능한 수 시도)
//start부터 처리시 중복 수 추출 방지 및 순서가 다른 조합 추출 방지
for(int i=start; i<N; i++) { //선택지
//start위치부터 처리했으므로 중복체크 필요없음!!
//선택되지 않았다면 수를 사용
numbers[cnt]=input[i];
//다음수 뽑으러 가기
comb(cnt+1, i+1);
}
}
}중복 관련 로직이 다 사라짐
그렇다면 순열과 조합의 차이는 무엇일까?
- 순열, 조합 차이
순서가 있나?
있다->순열
없다->조합
활용
주사위던지기
-주사위를 3번 던져서 나올 수 있는 모든 경우
순서고려 중복순열. 6ㅠ3
-주사위를 3번 던져서 모두 다른 수가 나올 수 있는 모든 경우
단, 123 132 다른경우
순서고려 순열 6P3
-주사위를 3번 던져서 중복되는 경우 제외하고 나올수 있는 모든 경우
중복되는 경우, 112,121,211 ->순서 무관
중복조합
nHr
6H3=6+3-1C3=3C3
-주사위를 3번 던져서 모두 다른수가 나올 수 있는 모든 경우
단,123,132,321은 중복되는 경우이다.
조합
6C3
package algorithm;
import java.util.Arrays;
import java.util.Scanner;
public class Ex_DiceTest {
static int N, totalCnt;
static int[] numbers;
static boolean[] isSelected;
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
N=sc.nextInt();//던지는 주사위 수
int mode = sc.nextInt();//던지기 모드
totalCnt=0;
numbers = new int[N];
switch (mode) {
case 1:
dice1(0); //중복 순열
break;
case 2:
isSelected = new boolean[7]; //1~6 주사위눈 선택여부
dice2(0); //순열
break;
case 3:
dice3(0,1); //중복조합
break;
case 4:
dice4(0,1); //조합
break;
default:
System.out.println("잘못된 입력");
return;
}
System.out.println("총 경우의 수"+totalCnt);
}
//중복순열
private static void dice1(int cnt) {
if(cnt==N) {
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
//가능한 모든 수 시도
for(int i=1; i<=6; i++) {
//수의 중복 선택이 가능하므로 중복 체크 필요 없음!
//해당 수 선택
numbers[cnt]=i;
//다음 주사위 던지러 가기
dice1(cnt+1);
}
}
//순열
private static void dice2(int cnt) {
if(cnt==N) {
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
//가능한 모든 수 시도
for(int i=1; i<=6; i++) {
//중복 체크 필요!
if(isSelected[i]) continue;
//해당 수 선택
numbers[cnt]=i;
isSelected[i]=true;
//다음 주사위 던지러 가기
dice2(cnt+1);
isSelected[i]=false;
}
}
//중복조합
private static void dice3(int cnt,int start) {
if(cnt==N) {
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
for(int i=start; i<=6; i++) {
numbers[cnt]=i;
dice3(cnt+1,i);
}
}
//조합
private static void dice4(int cnt, int start) {
if(cnt==N) {
totalCnt++;
System.out.println(Arrays.toString(numbers));
return;
}
for(int i=start; i<=6; i++) {
numbers[cnt]=i;
dice4(cnt+1,i+1);
}
}
}
부분집합
다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분집합을 찾는 것이다.
시간복잡도는 2의 n승. n이 30정도면 10억,,택도 없다
선택한 후 다음원소로 가기 (재귀)
선택안한 후 다음 원소로 가기 (재귀)
input[]
inSelected[]
generateSubset(cnt)
if(cnt==N)
부분집합 완성
else
isSelected[cnt]<-true
generateSubSet(cnt+1)
isSelected[cnt]<-false
generateSubSet(cnt+1)package algorithm;
import java.util.Scanner;
//n개의 수를 입력받고 가능한 모든 부분집합 생성
public class SubSetTest {
static int N,totalCnt;
static int[] input;
static boolean[] isSelected;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N=sc.nextInt();
totalCnt = 0;
input=new int[N];
isSelected = new boolean[N];
for(int i=0; i<N; i++) {
input[i] = sc.nextInt();
}
subset(0);
System.out.println("총 경우의 수:"+totalCnt);
}
private static void subset(int index) { //cnt: 직전까지 고려한 원소 수
if(index==N) { //더이상 고려한 원소가 없다면 부분집합의 구성이 완성
totalCnt++;
for(int i=0; i<N; i++) {
System.out.print(isSelected[i]? input[i]:"x");
System.out.print("\t");
}
System.out.println();
return;
}
//원소 선택
isSelected[index]=true;
subset(index+1);
//원소 미선택
isSelected[index]=false;
subset(index+1);
}
}위 코드는 부분집합에서 원소를 모두 더한 값이 0이 되는 경우가 있는지 알아낼 때 활용될 수 있다.
댓글