순열, 조합, 부분집합

순열, 조합, 부분집합

• 순열: 서로 다른 n개 중 r개를 ‘순서 있게’ 뽑아 나열
• nPr

import java.util.Arrays;
import java.util.Scanner;

public class PermutationTest {

	private static int N, R;
	private static int[] input, numbers;
	private static boolean[] isSelected;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		R = scanner.nextInt();
		
		input = new int[N];
		numbers = new int[R];
		isSelected = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			input[i] = scanner.nextInt(); 
		}
		
		permutation(0);
		
		scanner.close();
	}
	
	private static void permutation(int count) {
		if (count == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if (!isSelected[i]) {
				isSelected[i] = true; 
				numbers[count] = input[i];
				permutation(count + 1);
				isSelected[i] = false;
			}
		}
	}
	
}

• 조합: 서로 다른 n개 중 r개를 ‘순서 무관하게’ 뽑아 나열
• nCr = nPr / r!

import java.util.Arrays;
import java.util.Scanner;

public class CombinationTest {

	private static int N, R;
	private static int[] input, numbers;
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		N = scanner.nextInt();
		R = scanner.nextInt();
		
		input = new int[N];
		numbers = new int[R];
		
		for (int i = 0; i < N; i++) {
			input[i] = scanner.nextInt(); 
		}
		
		permutation(0, 0);
		
		scanner.close();
	}
	
	private static void permutation(int count, int start) {
		if (count == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = start; i < N; i++) {
			numbers[count] = input[i];
			permutation(count + 1, i + 1);
		}
	}
	
}

• 부분집합: 집합에 포함된 원소들을 선택
• 부분집합의 수(공집합 포함): 원소의 수가 n개일 때, 2^n

스택

• 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조
• 선형 자료구조로, 자료 간 관계가 일대일
• JVM의 메서드 스택에서 사용되는 방식
• LIFO