시간은 정직하게 흐른다. 곧 A형의 시간이 다가오고 있는데, 나는 BFS 및 DFS, 기타 자료구조 및 알고리즘 까먹어버린 사람. 자격증 공부도 해야하고 자소서도 써야하고 와우~,,, 하지만 이것들 중 가장 재밌는 알고리즘을 하는게 나을 것 같다. 일단 하나하나씩 끝내서 불안 줄이기..
가장 중요한 테크닉 중 하나인 (사실 못 외우면 못 푸는) 부분집합, 조합 순열부터 다시 알아볼 필요가 있다. 추가적으로 나는 백트래킹을 사용한 이것들의 사용방식을 선호한다. 정의를 간단하게 알아보고, 이에 대한 예시 구문을 작성하는 시간을 가진다.
부분집합
주어진 집합의 모든 가능한 부분 집합을 의미한다.
예를 들어, 집합 {1, 2, 3}의 부분집합은 {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}입니다.
import java.util.Arrays;
public class 부분집합 {
public static String[] 재료 = {"오이","우엉","햄","참치"};
public static int N=4;
//처음에 False로 초기화
public static boolean[] sel = new boolean[N];
public static void main(String[] args) {
powerset(0);
}
//idx : 해당 번째 위치 판단
public static void powerset(int idx) {
// 재귀함수는 기저파트와 재귀파트로 분류
// 기저파트 : 내가 이 재귀를 끝내는 부분
if(idx==N) { //모든 가능한 수를 다 판단했다. (넣을지 말지)
for(int i=0; i<N; i++) {
if(sel[i]) {
System.out.print(재료[i]);
}
}
System.out.println();
return;
}
// 재귀파트 : 계속해서 나를 호출하는 곳이 있다.
sel[idx] = false;
powerset(idx+1);
sel[idx] = true;
powerset(idx+1);
}
}조합
집합에서 일부 원소를 취해 만들 수 있는 모든 조합을 의미한다. 순서를 고려하지 않음!! 그렇기에, 전체 개수와, 조합할 숫자의 개수가 필요하다.
예를 들어, {1, 2, 3}에서 2개를 선택하는 조합은 {1, 2}, {1, 3}, {2, 3}이다.
import java.util.Arrays;
public class 조합 {
public static String[] 토핑 = {"상추", "패티", "토마토","치즈","새우"};
public static int N = 5;
public static int R = 2; //문제에서 판단할 수 있는 부분들
public static String[] sel = new String[R]; //내가 선택한 토핑
public static void main(String[] args) {
combination(0,0);
}
//idx : 토핑의 시작 index, sidx는 sel의 index
public static void combination(int idx, int sidx) {
//기저파트
if(sidx == R) {
System.out.println(Arrays.toString(sel));
return;
}
//경계설정
for(int i=idx; i<N-R+sidx; i++) {
sel[sidx] = 토핑[i];
combination(i+1, sidx+1);
}
}
}
// 사실 조합은 잘 이해가 안간다.순열
집합에서 일부 또는 모든 원소를 취해 만들 수 있는 모든 배열을 의미한다.
순서를 고려함.
예를 들어, {1, 2, 3}의 모든 순열은 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}입니다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class 백트래킹_03_순열3 {
public static int[] nums; //배열 저장을 할거구
public static int N; //원소 수
public static int[] result;
public static boolean[] visited;
public static void main(String[] args) {
nums = new int[] {0,1,2};
N = nums.length;
result = new int[N];
visited = new boolean[N];
}
//idx : 현재 판단 위치
public static void perm(int idx) {
if(idx == N) {
System.out.println(Arrays.toString(result));
return;
}
//사용할 수 있는 모든 원소를 체크
for(int i=0; i<N; i++) {
if(visited[i]) continue; //이미 사용한 원소라면 (True라면 쳐내기)
result[idx] = nums[i]; //해당 i번째의 원소를 저장
visited[i] = true; //i번째 원소 사용했다고 표시
perm(idx+1);
visited[i] = false; //i번째 원상복구
}
}
}조합과 순열의 차이점
: 조합은 원소들의 순서를 고려하지 않는다. 즉 {A,B}와 {B,A}는 같은 조합으로 간주된다.
하지만 순열은 원소들의 순서를 고려한다. 즉, {A, B}와 {B, A}는 서로 다른 순열로 간주된다.
예전에 완벽하게 이해하고 외웠다고 생각해서, 친구를 혼내면서 가르쳤는데,,, 이제 보니 나도 다 까먹었다................ 나 다시 시작할 수 있을까?
