완전탐색 - 순열, 조합, 부분 집합
2021. 9. 6. 22:34ㆍ알고리즘(Algorithm)
- 생각할 수 있는 모든 경우의 수를 구하다.
- 상대적으로 빠른 시간에 문제 해결을 할 수 있다.
- Brute-force 또는 Generate - and - test 기법이다.
순열(Permutation)
- 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것
- 서로 다른 n개 중 r개를 택하는 순열 : nPr = n*(n-1)*(n-2)*---*(n-r+1)
- 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련
- N개의 요소들에 대해서 N!개의 순열들이 존재
- 알고리즘
n개 숫자에 대해서 시도, 앞에서 선택된 수는 배제, 해당 개수의 수 선택
import java.util.Scanner;
public class Permutation {
static int[] numbers, result; // 숫자들의 배열, 결과를 담을 배열
static boolean[] check; //방문 여부를 확인하는 배열
static int n, r; //전체 n개 중, r개를 선택
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
r = scanner.nextInt();
//numbers값도 채우고 등등
perm(0);
}
//cnt: 현재 몇개 까지 선택했는지를 나타냄.
private static void perm(int cnt) {
if(cnt == r) {//r개를 모두 다 선택했다면 재귀함수를 종료
//이 안에서 조합의 경우를 가지고 하고싶은거 다해~
return;
}
for(int i = 0; i<numbers.length; i++) {
if(check[i]) continue; //이미 선택했다면 그만
result[cnt] = numbers[i]; //결과에 numbers[i]를 넣음(혹은 그냥 인덱스만 넣어도 된다)
check[i] = true; //방문 처리를 한다.
perm(cnt+1); // 재귀적으로 그 다음을 부른다.
check[i] = false; //재귀 함수가 끝나면 또 다른 재귀에서 사용해야 하니 false로 바꾼다(반납)
}
}
}
조합(Combination)
- 서로 다른 n개 중 r개를 순서 없이 뽑는다.
- nCr = nPr / r! = n*(n-1)*(n-2)*---*(n-r+1) / r*(r-1)*(r-2)*(r-3)*---2*1
- 알고리즘
n개의 숫자 중, r개를 선택한다. 그때, 중복을 제거하기 위해 나 이후 것만 선택한다.
import java.util.Scanner;
public class Combination {
static int[] numbers, result; // 숫자들의 배열, 결과를 담을 배열
static int n, r; //전체 n개 중, r개를 선택
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
r = scanner.nextInt();
//numbers값도 채우고 등등
comb(0,0);
}
//cnt: 현재 몇개 까지 선택했는지를 나타냄.
//start: 시작 인덱스를 나타냄. 방문 여부 확인을 안하고 그냥 뒤에부터 선택하기 위해서
private static void comb(int cnt, int start) {
if(cnt == r) {//원하는 개수 만큼 뽑았다면
//하고싶은거 다해
return;
}
for(int i = start; i<numbers.length; i++) {
result[cnt] = numbers[i]; // 직접 값을 넣어도 되고, 아니면 인덱스만 넣어도 된다.
comb(cnt+1, i); //선택한 개수(cnt)를 하나 증가, start는 나 부터 시작
}
}
}
부분 집합(Subset)
- 한 원소에 대해서 포함을 하거나(선택을 하거나), 포함을 하지 않는다(선택을 하지 않는다).
- 즉, 한 원소 당 2가지의 경우의 수가 있다.
- 집합에 포함된 원소들을 선택하는 것
- 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것
- 알고리즘
한 원소에 대해서 이를 포함 하거나, 포함하지 않는 경우 모두를 생각한다.
import java.util.Scanner;
public class Subset {
static int[] numbers; // 숫자들의 배열
static boolean[] check; //방문했는가를 체크하는 배열, numbers와 같은 크기(부분신 느낌)
static int n; //전체 n개
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
//numbers값도 채우고 등등
}
//cnt: 현재 몇개 까지 뽑을 지, 안뽑을지 결정했는지를 나타냄.
private static void subset(int cnt) {
if(cnt == n) {//전체 원소의 개수 만큼 결정했다면
for(int i = 0; i<check.length; i++) {
if(check[i]) {//포함된 것들만 뽑는다. - subset들
//여기서 생성된 subset들 가지고 하고싶은거 다해!!
}
}
return;
}
//해당 원소는 포함하는 경우
check[cnt] = true;
subset(cnt+1);
//해당원소는 포함하지 않는 경우
check[cnt] = false;
subset(cnt+1);
}
}
'알고리즘(Algorithm)' 카테고리의 다른 글
Next Permutation (0) | 2021.11.16 |
---|---|
최소 신장 트리(MST) - Kruskal 알고리즘 / Prim 알고리즘 (0) | 2021.09.21 |
피보나치수열_Fibonacci Sequence (0) | 2021.08.11 |
Binary Search_이진탐색 (0) | 2021.08.10 |
Insertion Sort(삽입 정렬) (0) | 2021.08.05 |