1)순열
import java.util.*;
public class Main {
public static void solution(char []item, char []bucket, int k) {
if( k == 0 ) { //다 뽑았으면 출력
for(int i=0; i<bucket.length; i++ ) {
System.out.print( bucket[i] + " " );
}
System.out.println();
return;
}
int lastIndex = bucket.length - k - 1; //현재 bucket에 들어있는 원소의 개수 - 1
for(int i=0; i<item.length; i++ ) {
int flag = 0;
for(int j=0; j<=lastIndex; j++) {
if( item[i] == bucket[j] ) { //이미 버켓에 들어있으면 뽑지 않음
flag = 1;
break;
}
}
if( flag == 1 ) continue;
bucket[lastIndex+1] = item[i];//마지막으로 담은 인덱스 다음에 새로운 원소 추가
solution(item,bucket,k-1);
}
}
public static void main(String[] args) {
char []item = { 'a', 'b', 'c', 'd', 'e' };
char []bucket = new char[item.length];
solution( item, bucket, item.length);
}
}
시간복잡도: O(n!)
2) 조합
백트래킹을 이용하는 방법과 재귀를 이용하는 방법이 있음
현재 원소를 뽑는 경우 + 현재 원소를 뽑지 않는 경우
import java.util.*;
public class Main {
//백트래킹을 이용한 방법
static void comb1(char[] arr, boolean[] picked, int start, int n, int r) {
if(r == 0) {
print(arr, picked, n);
return;
}
for(int i=start; i<n; i++) {
picked[i] = true;
comb1(arr, picked, i + 1, n, r - 1);
picked[i] = false;
}
}
//재귀를 이용한 방법
static void comb2(char[] arr, boolean[] picked, int depth, int n, int r) {
if (r == 0) {
print(arr, picked, n);
return;
}
if (depth == n) {
return;
}
picked[depth] = true;
comb(arr, picked, depth + 1, n, r - 1);
picked[depth] = false;
comb(arr, picked, depth + 1, n, r);
}
public static void print(char[] arr, boolean[] picked, int n) {
for(int i=0; i<n; i++)
if(visited[i])
System.out.print(arr[i]);
System.out.println();
}
public static void main(String[] args) {
char []item = { 'a', 'b', 'c' };
boolean []pick = new boolean[item.length];
combination(item, pick, 0, 3, 2);
com(item, pick, 0, 3, 2);
}
}
시간복잡도: O(2^n)
'프로그래밍 > 알고리즘' 카테고리의 다른 글
유클리드 호제법 (1) | 2024.10.12 |
---|---|
비트마스크 알고리즘/ 집합 구현 (0) | 2024.01.28 |
동적계획법/다이나믹 프로그래밍(Dynamic Programming) (0) | 2022.11.09 |
멱집합(PowerSet) (0) | 2022.10.12 |
Counting Cells in Blob(Blob 셀 수 세기) (0) | 2022.10.12 |