알고리즘은 순조부 .. Java로 구현해보자 !

순조부

순조부가 싫었던 지난날의 나 .. 구글에 고양이짤 치면 나옴

순조부란 순열, 조합, 부분집합을 의미하는데 대다수의 알고리즘의 풀이는

순열, 조합과 부분조합으로 가능하다 !

 

본 게시글은 이전의 파이썬으로 알고리즘을 정리하던 것과 달리 자바를 기준으로 코드 예시를 들려고 한다 ! 

주언어를 드디어 .. 자바로 바꾸었기 때문이다 후후

---

순열  nPr 

서로 다른 n개 중에 순서를 고려하여 r 개를 뽑는 것으로

 예시로는 반장과 부반장 뽑기, 1,2,3 등 선물 추첨하기, 급식 받는 순서 정하기 등이 있다

순열은 순서를 고려하기 때문에 숫자를 사용하기 전에 해당 숫자가 사용된 적 있는지에 대한 확인이 필요하다 !

//순열 : 1부터 n 까지 순서를 고려하여 r 개를 뽑는 경우
public class Permutation {
	static int N, R;
	static int[] numbers;
	static boolean[] isSelected;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		R = sc.nextInt();
		
		numbers = new int[R]; // 순열로 뽑아진 숫자를 저장할 배열
		isSelected = new boolean[N+1]; // 1부터 해당 숫자가 사용중인지 .. 중복 확인하는 배열
		
		perm(0);
	}

	private static void perm(int cnt) { //cnt 현재까지 뽑은 순열의 개수를 매개변수로 !
		if(cnt==R) { // n 개 중 r 개를 다 뽑았다면
			System.out.println(Arrays.toString(numbers)); // 출력 !
			return;
		}
		
		for(int i=1;i<=N;i++) { // 1부터 N까지 모든 가능한 경우에 대해 시도
			if(!isSelected[i]) { // 사용하려는 수가 사용되었는지 아닌지 확인
				// 사용한 적 없는 수라면 해당 수를 사용한다
				isSelected[i] = true;
				numbers[cnt] = i;
				
				perm(cnt+1); // 다음 자리수를 뽑으러 이동
				isSelected[i] = false; // 재사용을 위해 ..
				
			}
		}
	}
}

숫자를 입력 받아  뽑는 순열은 아래 코드를 참고 !

// 순열 : n 개의 입력받은 숫자 중 순서를 고려하여 r개 뽑는 경우
public class PermTest {
	static int n,r;
	static int[] input, numbers;
	static boolean[] isSelected;

	public static void main(String[] args) {
		Scanner sc = new Scanner(new InputStreamReader(System.in));
		n = sc.nextInt(); // 서로 다른 n 개를 입력받아서
		r = sc.nextInt(); // 순서를 고려하여 r 개를 고르는 순열 !
		
		input = new int[n];
		numbers = new int[r];
		
		isSelected = new boolean[n+1];
		
		for(int i=0;i<n;i++) {
			input[i] = sc.nextInt();
		} // 입력 완료
		
		perm(0);
	}

	private static void perm(int cnt) {
		if(cnt ==r) {
			for(int i=0;i<r;i++) {
				System.out.print(numbers[i]+" ");
			}System.out.println();
			return;
		}
		
		for(int i=0;i<n;i++) {
			if(!isSelected[i]) {
				// 사용되지 않는 수면 사용
				numbers[cnt] = input[i];
				isSelected[i] = true;
				
				perm(cnt+1); // 다음 자리수로 넘어감
				isSelected[i] = false; // 다음 사용을 위해
			}
		}
	}

}

---

조합

서로 다른 n 개의 순서를 고려하지 않고 r개 뽑는 경우로

n개 중에 종류 상관없이  과자 r 개 고르기,  r명의 급식 당번 정하기 등으로 이해하면 좋다

 

조합은 순서를 고려하지 않기 때문에 따로 중복을 확인할 필요가 없다

숫자를 뽑고 그 다음 자리 숫자를 뽑기만 하면 된다 !

//조합 : 서로 다른  n 개에서 순서를 고려하지않고 r 개를 모두 뽑는 것
public class Finalcomb{
	static int N, R;
	static int[] input, numbers;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		R = sc.nextInt();
		
		input = new int[N]; // 입력받을 N 개의 수
		numbers = new int[R]; // 만들어질 조합
		
		for(int i=0;i<N;i++) {
			input[i] = sc.nextInt();
		} // N 개의 수를 입력받기
		
		comb(0, 0); // 시작위치와 시도한 조합의 수
	}

	private static void comb(int cnt, int start) { // N 개의 입력받은 수 중 R 개의 조합 찾기
		if(cnt==R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for(int i=start;i<N;i++) {
			numbers[cnt] = input[i]; // 해당 숫자를 고르고
			comb(cnt+1, i+1); // 다음 자리 수로 이동 !
		}
	}
}

---

부분집합

부분집합은 A 라는 집합에서 N (0<=N<=A) 개를 뽑아 나열한 경우로

예시로 N 개의 정수가 존재할 때  숫자의 합이 최대가 되는 숫자들의 조합을 구하는 경우나
민지를 포함해 조원을 구성하는 방법 등으로 이해하면 좋다

//N개의 수를 입력 받고 가능한 모든 부분집합 생성
public class Subset {
	static int N;
	static int[] input;
	static boolean[] isSelected;
	
	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		N = sc.nextInt();
		
		input = new int[N]; // N 개의 수를 입력받을 배열
		isSelected = new boolean[N];
		
		for(int i=0;i<N;i++) {
			input[i] = sc.nextInt();
		} // 입력
		
		subset(0);
	}

	private static void subset(int idx) {
		if(idx==N) { // 더이상 고려할 원소가 없다면
			for(int i=0;i<N;i++) {
				if(isSelected[i]) {
					System.out.print(input[i]+" ");
				}
			}System.out.println();
			return;
		}
		
		// 선택하는 경우
		isSelected[idx] = true;
		subset(idx+1);
		
		// 미선택하는 경우
		isSelected[idx] = false;
		subset(idx+1);
	}
}