순열/조합/부분집합

줄여서 순조부라고 한다.

대부분 코테를 준비할 때 처음 마주하게 되는 영역이다. 

출제비중이 그리 높진 않지만 이 개념을 모르고 구현도 못하는 상태로 코테를 보면 떨어질 것이다.  뿐만 아니라 이 개념을 알고 있으면 사고의 범위가 확장되고 문제를 풀 수 있는 카드가 하나 더 생긴다.

 

순열(Permutaition)

순서를 고려해서 나열할 수 있는 모든 경우의 수를 구하는 것이 순열이다.

순열은  n팩토리얼의 경우의 수를 가진다.

 

예를 들어

A,B,C가 있다고 가정하면 이를 나열 할 수 있는 경우는

ABC

ACB

BAC
BCA
CAB
CBA

6가지가 나온다. 즉 3! 이다.

보통 n이 11일때까지 4천만개정도의 경우로 시간 복잡도를 구할 수 있고 12부터는 4억을 초과하기때문에 다른 풀이를 고려해 봐야한다.

 

https://www.acmicpc.net/problem/10974

10974번: 모든 순열

순열에 관한 간단한 문제이다.

package practice2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class boj10974 {
	static int N;
	static boolean[] used;
	static int[] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(in.readLine());
		used= new boolean[N+1];
		arr= new int[N+1];
		permutation(0);
	}

	private static void permutation(int cnt) {
		if (cnt == N) {
			for (int i = 0; i < N; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}

		for (int i = 1; i <= N; i++) {
			if (used[i])
				continue;
			used[i] = true;
			arr[cnt] = i;
			permutation(cnt + 1);
			used[i] = false;
		}
	}
}

 

조합(Combination)

n개의 원소 중에서 r개를 뽑는 경우의 수이다. 그리고조합은 순서를 고려하지 않는다. 따라서

ABC

ACB

BAC
BCA
CAB
CBA

이 모든 경우를 싸그리 묶어서 하나의 경우로 생각한다.

조합 공식은 

nCr = n!/r!(n-r)! 이다.

이걸 계산할려면 팩토리얼 계산이 오래걸리니까 직접계산은 비추천이다.

대신 느낌을 잘 파악하면 된다. 

n개중에서 r개를 뽑는 경우의 수를 구하라는 느낌이 난다면 조합으로 풀면된다.

https://www.acmicpc.net/problem/2407

2407번: 조합

조합에 관한 문제이다.

 

 

package practice2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class boj1759 {
	static int N, M;
	static boolean[] used, alphabet;
	static char[] arr, password;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		alphabet = new boolean[26];
		alphabet[0] = true;
		alphabet[4] = true;
		alphabet[8] = true;
		alphabet[14] = true;
		alphabet[20] = true;
		// 모음 자리는 다 트루 표시

		String[] s = in.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		arr = new char[M];
		password = new char[M];
		s = in.readLine().split(" ");
		for (int i = 0; i < M; i++)
			arr[i] = s[i].charAt(0);
		Arrays.sort(arr);

		comb(0, 0, 0, 0);
	}

	private static void comb(int start, int cnt, int mCnt, int jCnt) {
		if (cnt > N)
			return;
		if (cnt == N && mCnt > 0 && jCnt > 1) {
			for (int i = 0; i < N; i++)
				System.out.print(password[i]);
			System.out.println();
		} else {
			for (int i = start; i < M; i++) {
				password[cnt] = arr[i];
				if (alphabet[arr[i] - 'a'])
					comb(i + 1, cnt + 1, mCnt + 1, jCnt);
				else
					comb(i + 1, cnt + 1, mCnt, jCnt + 1);
			}
		}
	}
}

 

부분집합 (subset)

부분집합은 부분적으로 집합을 만드는 것이다.

A,B,C가 있으면

{0},{A},{B},{C},{A,B},{A,C},{B,C},{A,B,C}가 된다.

부분 집합을 구성하는 경우의 수는 2의 n승 이다.

n개가 있으면 포함시키거나/포함시키지 않거나라는 2가지 경우를 각 n개 만큼 가진다고 볼 수 있다.

 

https://www.acmicpc.net/problem/1182

1182번: 부분수열의 합

부분집합 문제다.

package practice2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class boj1182 {
	static int N , M, answer;
	static int arr[];
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String[] s = in.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);
		s = in.readLine().split(" ");
		arr = new int[N];
		for(int i =0; i<s.length;i++)arr[i] = Integer.parseInt(s[i]);
		ArrayList<Integer>list = new ArrayList<>();
		subset(0,0,false);
		
		System.out.println(answer);
	}
	private static void subset(int cnt,int sum , boolean flag) {
		if(sum==M && flag ==true)answer++;
		if(cnt>=N)return;
		subset(cnt+1,sum,false);//현재 안 더한거
		subset(cnt+1,sum+arr[cnt],true);//현재 값 더한거
	}
}