순열/조합 (완전탐색)
1. 완전탐색(Brute-force)?
: 모든 경우의 수를 탐색하여 문제를 푸는 방식. 대표적인 예로 순열, 조합이 있음
2. 순열(Permutation, nPk)
: n개의 요소들 중 k개를 뽑아 '정렬'할 수 있는 경우의 수
(1) 전통적인 순열 구하는 방법
- k개의 자리에 올 수 있는 요소의 개수를 세는 방식
- n x (n-1) x (n-2) x ... x (n-k+1) = n! / (n-k) !
- 단, 위의 수식은 단순히 "개수"를 구하는 방법일 뿐 완전탐색에 조건을 적용하기엔 부족함
(2) 순열 알고리즘 : 0~k번째에 수를 고정시킨다.
[과정]
① depth번째 수 고정
- 방법1) 첫번째 수와의 swap을 통해 지정
- 방법2) 고정여부를 담은 visited배열(n과 같은 길이)에 표현
② 나머지 수에 대해서 perm 재귀호출(단, depth를 1 증가시켜 고정 자리 이후부터)
③ depth와 k가 같아지면 Int 형태로 ArrayList/HashSet에 넣기
(사실상 HashSet이 더 적절 : 중복되는 숫자가 없게 저장 가능)
[방법1 - 코드]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Permutation {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int[] numList = new int[input.length];
for(int i = 0; i < input.length; i++) {
numList[i] = Integer.parseInt(input[i]);
}
HashSet<Integer> result = new HashSet<>();
int size = numList.length;
for(int i = 1; i <= size; i++) { //각 k에 대한 결과들 (nP0, nP1, ... )
perm(numList, 0, size, i, result);
}
Iterator<Integer> itr = result.iterator();
while(itr.hasNext()) {
System.out.println(itr.next());
}
}
//방법1 : swap 이용
public static void perm(int[] arr, int depth, int n, int k, HashSet<Integer> result) {
if(depth == k) {
String s = "";
for(int i = 0; i < k; i++) {
s += arr[i];
}
result.add(Integer.parseInt(s));
}
else {
for(int i = depth; i < n; i++) {
swap(arr, depth, i);
perm(arr, depth+1, n, k, result);
swap(arr, depth, i);
}
}
}
//swap 함수 : arr의 a번 요소와 b번 요소를 뒤바꿈
public static void swap(int[] arr, int a, int b) { //call by value여서 arr에 반영 가능
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
[방법2 - 코드]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Permutation {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int[] numList = new int[input.length];
for(int i = 0; i < input.length; i++) {
numList[i] = Integer.parseInt(input[i]);
}
HashSet<Integer> result = new HashSet<>();
int size = numList.length;
boolean[] visited = new boolean[size];
for(int i = 1; i <= size; i++) { //각 k에 대한 결과들 (nP0, nP1, ... )
perm2(numList, visited, "", 0, size, i, result);
}
Iterator<Integer> itr = result.iterator();
while(itr.hasNext()) {
System.out.println(itr.next());
}
}
//방법2 : visited 배열 이용
public static void perm2(int[] arr, boolean[] visited, String output, int depth, int n, int k, HashSet<Integer> result) {
if(depth == k) {
result.add(Integer.parseInt(output));
}
else {
for(int i = 0; i < n; i++) {
if(!visited[i]) {
output += arr[i];
visited[i] = true;
perm2(arr, visited, output, depth+1, n, k, result);
output = output.substring(0, output.length()-1);
visited[i] = false;
}
}
}
}
}
3. 조합(Combination, nCk)
: n개의 요소들 중 k개를 뽑는 경우의 수
(1) 전통적인 조합 구하는 방법
- k개의 자리에 올 수 있는 요소의 개수를 세는 방식 & 중복되는 경우 제외(순서만 다른 것은 같은 것으로 취급)
- n x (n-1) x (n-2) x ... x (n-k+1) / k x (k-1) x ... x 1 = n! / (n-k) ! x k!
- 단, 위의 수식은 단순히 "개수"를 구하는 방법일 뿐 완전탐색에 조건을 적용하기엔 부족함
(2) 조합 알고리즘 : 각 숫자의 선택여부를 표현
[과정]
① target번째 수의 선택 여부 결정 (단, target의 index가 n보다 작을 때까지만...)
- 선택한다면? : visited[i] = true
② target을 옮겨서 comb 재귀 호출 (조합이므로 더이상 앞의 수들은 고려X - 이미 선택여부가 끝난것!!)
- 선택 X : comb(arr, visited, n, k, target+1, result) --- target move
- 선택 : comb(arr, visited, n, k-1, target+1, result) --- target move + visited 표시(①), k-1(선택할 수 있는 숫자의 개수)
③ k가 0이 되면, int형태로 ArrayList, HashSet에 넣기
[코드]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Combination {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int[] numList = new int[input.length];
for(int i = 0; i < input.length; i++) {
numList[i] = Integer.parseInt(input[i]);
}
int size = numList.length;
boolean[] visited = new boolean[size];
HashSet<Integer> result = new HashSet<>();
for(int i = 1; i <= size; i++) { //각 k에 대한 결과들 (nC0, nC1, ... )
comb(numList, visited, size, i, 0, result);
}
Iterator<Integer> itr = result.iterator();
while(itr.hasNext()) {
System.out.println(itr.next());
}
}
public static void comb(int[] arr, boolean[] visited, int n, int k, int target, HashSet<Integer> result) {
if(k == 0) {
String s = "";
for(int i = 0; i < n; i++) {
if(visited[i]) s += arr[i];
}
result.add(Integer.parseInt(s));
}
else {
if(target < n) {
comb(arr, visited, n, k, target+1, result);
visited[target] = true;
comb(arr, visited, n, k-1, target+1, result);
visited[target] = false;
}
}
}
}
(3) 모든 조합을 구하는 경우 : 비트마스크와 반복문을 이용해 구할 수 있다.
[과정]
- n = 원소의 개수
① 전체 가능한 조합의 개수 : 1 << n (2^n)
② 각 조합에 해당하는 원소 저장(출력) : & 연산을 통해 자릿수가 일치하는지 확인
→ i & (1 << j) (i : target, j : 자릿수)
ex> {2,3,4}의 포함 여부를 나타낸 배열 {1,0,1} → 101에서 1에 해당하는 원소만 출력
1. index 0 : 101 & (1 << 0) = 101 & 1 = 001
→ 0보다 크기 때문에 0번 index는 포함
2. index 1 : 101 & (1 << 1) = 101 & 10 = 000
→ 0이므로 1번 index는 포함X
3. index 2 : 101 & (1 << 2) = 101 & 100 = 100
→ 0보다 크기 때문에 2번 index는 포함
▶ {4, 2}
[코드]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Combination2 {
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int[] numList = new int[input.length];
for(int i = 0; i < input.length; i++) {
numList[i] = Integer.parseInt(input[i]);
}
int size = numList.length;
boolean[] visited = new boolean[size];
HashSet<Integer> result = new HashSet<>();
result = comb(numList, size);
Iterator<Integer> itr = result.iterator();
while(itr.hasNext()) {
System.out.println(itr.next());
}
}
public static HashSet<Integer> comb(int[] arr, int n) {
HashSet<Integer> result = new HashSet<>();
for(int i = 0 ; i < (1<<n); i++) {
String s = "";
for(int j = 0; j < n; j++) {
if((i & (1 << j)) > 0) {
s += arr[j];
}
}
if(s.length() > 0) result.add(Integer.parseInt(s));
}
return result;
}
}