[알고리즘 개념] 순열 조합 부분집합(순조부~)

자바로 알고리즘을 풀면서 순조부에 대해서 깊게 공부해야했습니다... (파이썬은 api가 있지만 자바는 없기 때문에)

순조부를 공부하면서 자신이 없던 재귀도 공부하구,,, 의외로 문제 풀때 개념이 많이 쓰이더군용.. 그런 문제만 풀어서 그른가

아무튼 핵심 개념에 대해서 글을 써보겠습니다.

 

순열(Permutation)

서로 다른 n개 원소 중 r개를 뽑아서 한 줄로 나열하는 것. nPr

쉽게 예제를 통해 말하면

3명 중에서 회장 1명, 부회장 1명을 뽑는다면

(a,b)  (a,c)

(b,a)  (b,c)

(c,a)  (c,b)

 

이런 식으로 뽑을 수 있는데 중요한 포인트는 a,b != b,a 입니다. (조합과 다른 큰 특징)

예시 코드

private static void permutation(int cnt) {
		// TODO Auto-generated method stub
		if(cnt==N) {
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}

		for (int i=1 ; i<=6 ; i++) {
			// 중복 체크
			if(isSelected[i]) continue;

			numbers[cnt] = i;
			isSelected[i]=true;

			permutation(cnt+1);
			isSelected[i] =false;
		}
}

 

조합(Combination)

서로 다른 n개의 원소 중 r개를 고르는 것 nCr

위와 같은 예시로 들면 3명 중에서 임원 2명을 고른다면

(a,b) 

(b,c) 

(a,c)

3개 나오고 뽑기만 하면 되니까 a,b = b,a 같은걸로 보는게 핵심!!

 

private static void combination(int cnt,int start) {
		// TODO Auto-generated method stub
		if(cnt==N) {
			totalCnt++;
			System.out.println(Arrays.toString(numbers));
			return;
		}

		for (int i=start ; i<=6 ; i++) {
			// 중복 체크
			numbers[cnt]=i;
			combination(cnt+1, i+1);
		}
}

부분집합(PowerSet 또는 SubSet)

집합에 포함된 원소를 선택하는 것,,, 2^n개가 나올 수 있습니다.

예시로는 3명 중에서 노래자랑에 참가 할 사람을 고른다면

(공집합)

(a) , (b) , (c)

(a,b),(b,c) ,(a,c)

(a,b,c)

모두 다 참여해도 되고,, 참여안해도 되고,,, 자기 마음대로 이므로 8개인 상황이 나옵니다.

private static void generateSubSet(int cnt) {
		if(cnt ==N) {
			// 부분집합 완성
			totalCnt++;
			for (int i = 0; i < N; i++) {
				System.out.print((isSelected[i]?input[i]:"X")+" ");
			}
			System.out.println();
			return;
		}
		
		// 현재 원소를 부분집합에 넣기
		isSelected[cnt] = true;
		generateSubSet(cnt+1);
		// 현재 원소를 부분집합에 넣지 않기
		isSelected[cnt]= false;
		generateSubSet(cnt+1);
}