[알고리즘은 처음이라] 지피지기 백전백승! 2.완전탐색

알고리즘을 공부하는 가장 큰 이유는 코딩 테스트이기 때문에  이론적으로 알고리즘을 공부하는 것도 필요하겠지만 문제를 잘 풀기 위한 공부가 필요하다는 걸 알고리즘 공부를 하면서 많이 느끼게 되었다🙄🙄🙄

 

그래서 문제 푸는데 필요한 내용을 중심으로 알고리즘을 정리해보려고 한다

첫 번째로 소개할 알고리즘은 완전탐색! 

 

 

 

순열 기본 코드

import java.util.Arrays;

public class PremMain {
	static int N=4, R=3, C;
	static int[] a = {1,2,3,4}, // 입력으로 들어오는 배열 
				 b = new int[R]; // R개만 뽑는다 -> R개만 생성 (입력에서 R개만 가져온다)
	static boolean[] v = new boolean[N]; // 입력으로 들어온 수가 사용됬는지 확인 ->N개 생성
	
	public static void main(String[] args) {
		C = 0;
		perm(0);
		System.out.println(C);
	}
	
	static void perm(int cnt) {
		if(cnt == R) { // R개 뽑는 순열이 완성
			System.out.println(Arrays.toString(b));
			C++;
            
            // 완성된 순열을 가지고 여기서 더 작업을 진행할 수 있음!
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(v[i]) continue;
			v[i] = true;
			b[cnt] = a[i];
			perm(cnt+1);
			v[i] = false;
		}
	}

}

 

 

조합 기본 코드

import java.util.Arrays;

public class PremMain {
	static int N=4, R=3, C;
	static int[] a = {1,2,3,4}, // 입력으로 들어오는 배열 
				 b = new int[R]; // R개만 뽑는다 -> R개만 생성 (입력에서 R개만 가져온다)
	static boolean[] v = new boolean[N]; // 입력으로 들어온 수가 사용됬는지 확인 ->N개 생성
	
	public static void main(String[] args) {
		C = 0;
		comb(0,0); //nCr 4C3 조합 : 순서 무관 (123 == 321)
		System.out.println(C);
	}
	
	static void comb(int cnt, int start) {
		if(cnt == R) { // R개 뽑는 조합이 완성
			System.out.println(Arrays.toString(b));
			C++;
            
            // 완성된 조합을 가지고 여기서 작업을 더 할 수도 있음
			return;
		}
		
		for(int i=start; i<N; i++) { // 내 뒤에 있는 것부터 뽑음! -> 순서에 중복이 사라짐
									// 순서가 없음 -> 어떤게 선택되었는지 확인할 필요가 x
			b[cnt] = a[i];
			comb(cnt+1, i+1);
		}
	}

}

 

 

 

부분집합 기본 코드

import java.util.Scanner;

public class SubsetTest {
	static int N, totalCnt;
	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];
		isSelected= new boolean[N];
		
		for(int i=0; i<N; i++) {
			input[i] = sc.nextInt();
		}
		generateSubset(0);
		System.out.println(totalCnt);
	}
	
	static void generateSubset(int cnt) { // cnt : 직전까지 고려된 원소 수
		if(cnt == N) { // 부분집합 완성
			totalCnt++;
			for(int i=0; i<N; i++) {
				System.out.print((isSelected[i] ? input[i] : "x") + "\t"); 
			}
			System.out.println();
            
            // 완성된 부분집합으로 여기서 더 작업할 수 있음
			return;
		}
		// 현재 원소를 부분 집합의 구성에 포함
		isSelected[cnt] = true;
		generateSubset(cnt+1);
		
		// 현재 원소를 부분 집합의 구성에 비포함
		isSelected[cnt] = false;
		generateSubset(cnt+1);
	}

}