1. 조합(Combination)
서로 다른 n개의 원소에서 r개의 중복없이, 순서를 고려하지 않고 선택
* 현재 수보다 큰수는 앞에 안나옴!!!!
[1, 2, 3] 이란 숫자 배열에서 2개의 수를 순서 없이 뽑으면
[1, 2] [1, 3] [2, 3]
=> 순열과 다르게 [2, 1] [3, 1] [3, 2] 은 중복
- 재귀를 이용한 조합 알고리즘
import java.util.Scanner;
public class CombinationTest1 {
static int n; // 입력된 n의 크기
static int r; // 조합에서 뽑을 수의 개수
static int[] numbers; // 뽑은 r개의 수를 저장할 배열
static int[] input; // 입력된 n개의 데이터
static int testcase; // 조합의 개수를 세는 변수
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
// 입력 받기
n = scan.nextInt();
r = scan.nextInt();
input = new int[n];
numbers = new int[r];
// 입력된 값들 배열에 저장
for (int i = 0; i < n; i++) {
input[i] = scan.nextInt();
}
// 조합 생성 시작
combi(0, 0);
// 조합의 개수 출력
System.out.println(testcase);
}
/**
* r개의 조합을 생성하는 메서드
* @param depth 현재까지 뽑은 수의 개수
* @param start 뽑을 수의 시작 인덱스
*/
private static void combi(int depth, int start) {
if (depth == r) { // r개를 다 뽑았다면
testcase++;
return;
}
for (int i = start; i < n; i++) {
numbers[depth] = input[i];
combi(depth + 1, i + 1); // 다음 수를 뽑기 위해 재귀 호출
}
}
}
2. 순열
-서로 다른 n개의 원소에서 r개를 순서를 고려해서 선택(나열)하는 것을 순열이라한다.
* for 문을 이용한 순열 표현
import java.util.Scanner;
public class Permutation_for {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
// 원소 수 입력
int N = scan.nextInt();
int[] data = new int[N];
// 데이터 입력
for (int i = 0; i < N; i++) {
data[i] = scan.nextInt();
}
// 중복 순열 (nπr) 계산
int cnt = 0;
System.out.println("중복 순열 (nπr) 결과:");
for (int i = 0; i < N; i++) { // 첫 번째 원소 반복
for (int j = 0; j < N; j++) { // 두 번째 원소 반복
for (int k = 0; k < N; k++) { // 세 번째 원소 반복
cnt++;
System.out.printf("%d %d %d%n", data[i], data[j], data[k]);
}
}
}
System.out.printf("%dT3 중복 순열의 개수: %d%n", N, cnt);
System.out.println("----------------------------");
// 순열 (중복 없이 원소 선택) 계산
cnt = 0;
System.out.println("순열 (중복 없이 원소 선택) 결과:");
for (int i = 0; i < N; i++) { // 첫 번째 원소 반복
for (int j = 0; j < N; j++) { // 두 번째 원소 반복
if (i != j) { // 두 번째 원소는 첫 번째와 같으면 안 됨
for (int k = 0; k < N; k++) { // 세 번째 원소 반복
if (i != k && j != k) { // 세 번째 원소는 첫 번째, 두 번째와 같으면 안 됨
cnt++;
System.out.printf("%d %d %d%n", data[i], data[j], data[k]);
}
}
}
}
}
System.out.printf("%dP3 순열의 개수: %d%n", N, cnt);
}
}
* 재귀 함수를 통한 중복 순열 표현
package permutation;
import java.util.Arrays;
public class Permutation_nTTr {
static int N; //원소 개수
static int R; //뽑을 개수
static int[] input; //입력 데이타
static int[] numbers; //뽑은 순열을 담을 배열
static int tc;
public static void main(String[] args) {
input = new int[] {1,2,3,4};
N = input.length;
R = 3;
numbers = new int[R];
perm(0);
System.out.printf("%dTT%d 중복 순열 개수:%d%n", N,R, tc );
}
public static void perm(int depth) {
/*
* 배열은 0부터 시작하므로 R-1의 위치까지가 모든 원소를 뽑은 상황
* depth가 R과 동일한 상황은 하나의 순열에서 모든 원소를 다 뽑은 상황이므로 종료
*/
if(depth==R) {
tc++;
System.out.println(Arrays.toString(numbers));
return;
}
//depth번째의 원소를 선택해야 한다.
for (int i = 0; i < N; i++) {
numbers[depth] = input[i];
perm(depth+1);
}
}
}- 순열은 재귀를 통해서 표현 // R개 가 되었을 때 종료
- 순열의 경우 1 , 2 , 3번째 depth 에 대하여 R개가 되었을 때 종료
* 중복된 경우의 continue로 다시 올라감;
public static void permutation(int depth) {
count++;
//배열은 0부터 시작이므로 R-1개가 모두 뽑은 상황. idx가 R과 동일한 상황은 순열을 다 뽑은 상황
if(depth == R) {
tc++;
//순열을 뽑은 이후의 task를 작성
// System.out.println(Arrays.toString(numbers));
return ;
}
top:
for (int i = 0; i < N; i++) {
//중복 검사
for (int j = 0; j <depth; j++) {
if(numbers[j]== input[i]) { //중복 된 경우
continue top;
}
}
numbers[depth] = input[i];
permutation(depth+1);
}
}
중복된 경우에 는 비교!! 0 ,R-1만큼의 합의 시간이 걸림 nⁿ n² // 시간 복잡도 너무 커!!
boolean 배열을 사용하여!!! 값이 없으면 사용 있으면 다음
배열에 들어가서 확인만 하고 나와서 중복 검사를 할 필요가 없음!!! N의 r번만 하는 게 중복 순열
*bollean을 통한 순열 표현
package permutation;
import java.util.Arrays;
public class Permutation2_nPr2_flag {
static long tc; // 순열 개수
static long count; // 반복 횟수
static int R; // 뽑을 개수
static int N; // 원소의 개수
static int[] numbers; // 순열을 담은 배열
static int[] input; // 입력된 데이터
static boolean[] isSelected; // 원소가 사용되었는지 여부를 체크하는 배열
/**
* 순열을 구하는 메서드
* @param depth 현재 뽑은 원소의 개수
*/
public static void permutation(int depth) {
count++; // 순열 생성 시마다 반복 횟수 증가
// R개의 원소를 모두 뽑은 경우, 순열을 완성한 상태
if(depth == R) {
tc++; // 순열 개수 증가
return;
}
// 모든 원소에 대해 순열을 생성
for (int i = 0; i < N; i++) {
// 중복 검사: 이미 사용한 원소는 제외
if(isSelected[i]) continue;
// 원소 사용
numbers[depth] = input[i];
isSelected[i] = true; // 해당 원소를 사용했다고 표시
// 재귀 호출하여 다음 원소를 뽑음
permutation(depth + 1);
// 재귀 호출 후 원소 사용 표시를 초기화
isSelected[i] = false;
}
}
public static void main(String[] args) {
// 입력 데이터 초기화
input = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 예시로 1부터 10까지의 원소 사용
N = input.length; // 원소의 개수
R = input.length; // 뽑을 개수 (전체 원소를 다 뽑음)
// 순열을 담을 배열과 사용 여부를 표시할 배열 초기화
numbers = new int[R];
isSelected = new boolean[N];
// 순열 구하기
permutation(0);
}
}
n의 r승에 중복된 것 뺀 값 //시간이 그렇게 빠르지 않음
*비트마스터를 통하여 중복원소 체크하기
* a&=b; //0000 1이었던 비트가 0으로 masking
* a|=b; //1010 0이었던 비트가 1으로 masking
비트마스크 핵심 개념
- 특정 비트가 1인지 0인지 확인하기
- flag & (1 << k)
- k번째 비트가 1이면 결과는 0이 아님, 아니면 0.
- flag & (1 << k)
- 특정 비트에 1 추가하기
- flag |= (1 << k)
- k번째 비트를 1로 설정
- flag |= (1 << k)
package permutation;
import java.util.Arrays;
public class Permutation2_nPr3_bit {
static long tc; // 순열 개수
static long count; // 반복 횟수
static int R; // 뽑을 개수
static int N; // 원소의 개수
static int[] numbers; // 순열을 담은 배열
static int[] input; // 입력된 데이터
/**
* 순열을 구하는 메서드
* @param depth 현재 뽑은 원소의 개수
* @param flag 원소의 중복 체크를 위한 비트마스크
*/
public static void permutation(int depth, int flag) {
// R개를 모두 뽑았으면 순열이 완성된 상태
if (depth == R) {
tc++; // 순열 개수 증가
return;
}
// 모든 원소에 대해 순열을 생성
for (int i = 0; i < N; i++) {
// 중복 검사: 비트마스크를 이용해 해당 원소가 사용되었는지 체크
if ((flag & (1 << i)) != 0) continue; // 이미 사용된 원소는 건너뜀
numbers[depth] = input[i]; // 원소 사용
permutation(depth + 1, flag | (1 << i)); // 다음 원소를 뽑음
}
}
public static void main(String[] args) {
// 입력 데이터 초기화 (예시로 1부터 10까지의 원소 사용)
input = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
N = input.length; // 원소의 개수
R = input.length; // 뽑을 개수 (전체 원소를 다 뽑음)
// 순열을 담을 배열 초기화
numbers = new int[R];
// 순열 구하기
permutation(0, 0);
}
}
*Sawp 순열
- 배열의 첫 값부터 순서대로 하나씩 바꾸며 모든 값을 한번씩 swap 한다.
- depth를 기준 인덱스로 하여 depth 보다 인덱스가 작은 값들은 그대로 고정하고
depth 이상의 인덱스들만 swap을 진행한다.
- 순열을 따로 구하지 않아도 된다
- nPn, nPr 모두 됨. 단 nPr시 전체 배열에서 앞에 r개만 사용
- n! 시간복잡도
- 0번째 인덱스 원소를 0번째 부터 n-1번째까지 위치를 바꾼다 (ABC, BAC, CBA)
- 1번 과정을 진행해서 나온 경우들을, 1번째 인덱스 원소를 1번째부터 n-1번째까지 위치를 바꾼다
- 이러한 과정을 n-1번 반복한다
- R-1은 내자신으로 0~R-2번째 까지 반복
나부터 바꾸고
//123 에 대하여
123
=> 123 132
213
=> 213 231
321
=> 321 312
public class Permutation2_nPr4_swap {
static long tc; // 순열 개수
static long count, swcnt; // 반복 횟수
static int R; // 뽑을 개수
static int N; // 원소의 개수
static int[] input; // 입력된 데이터
/**
* @param depth swap할 대상
*/
public static void permutation(int depth) {
// 배열은 0부터 시작이므로 R-1개가 모두 뽑은 상황.
//idx가 R과 동일한 상황은 순열을 다 뽑은 상황
if(depth == R-1) { // 순열이 완성됨 스압 순열은 R-2까지 스왑하면 순열이 결정된다.
tc++;
return;
}
for (int i = depth; i < N; i++) { // 현재 들어온 depth부터
// 두 수를 swap해서 순열을 만들기
swap(i, depth);
permutation(depth + 1);
// 다음 순열을 만들기 위해서 원복하기
swap(i, depth);
}
}
private static void swap(int i, int j) {
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
public static void main(String[] args) {
input = new int[] {1, 2, 3};
N = input.length;
R = input.length;
permutation(0); // 0번부터 순열 뽑기
}
}
'Cs기본지식 > 알고리즘' 카테고리의 다른 글
| 자바 자료구조 / Graph ,Tree 알아보기 (1) | 2025.02.19 |
|---|---|
| 자바 알고리즘 Subset 알아보기 (0) | 2025.02.18 |
| 정렬 알고리즘 이해하기 : 기본 구조 및 종류 (0) | 2025.02.17 |
| 자바 알고리즘 Datastructure (0) | 2025.02.17 |
| 자바 알고리즘 / 재귀 함수(Recursion Function) /백준 17478번 (0) | 2025.02.12 |