완전탐색 알고리즘

완전탐색 알고리즘 종류

1. Brute Force 기법 : 반복/조건문을 활용해 모두 테스트하는 방법
   ex) 자물쇠 번호

2. 순열 - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
   ex) 시간복잡도 ㅣ O(N!),재귀함수 이용

3. 재귀 호출
   ex) 각 원소가 두 가지 선택지를 가질 때 유용하게 사용, 시간복잡도 O(N)

4. 비트마스크

5. BFS,DFS를 활용하는방법
   ex) 너비우선 탐색(Breadth-Frist Search ) 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문(큐)
   깊이우선 탐색(Depth-Firsth Search): 트리의 한 요소를 방문하고 그 다음 수준의 자식 노드를 따라가는 방향으로 탐색(재귀호출)

6. 조합과 순열
   5C2= 4C2(저차원에서 생각하면 12345에서 1234/5 를 구분하고 1234에서 2개를 뽑고 5를 뽑는 경우
   5를 선택햇을때(1234를 선택완료로 가정) 1234/5 -> 4C2
   5를 선택하지 않앗을때(1234는 선택완료로 가정) 1234에서 3개뽑기 -> 4C3 + = 5C3

📔 문제 설명(순열)

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

📝 문제 풀이

💡 내 코드

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

public class Main {

    static int[] arr;
    static int[] result;
    static int N,level;
    static boolean visited[]; //전역변수로 

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // static으로 선언했으면 타입 설정 안해도됨
        level = Integer.parseInt(st.nextToken()); //1개
        arr = new int[N]; 	
        result = new int[level]; 						
        visited = new boolean[arr.length];//

        for (int i = 0; i <arr.length; i++) {
            arr[i]=i+1;	
        }
        recur(0);	
    }

    private static void recur(int deapth) {
        if(deapth==level) {
            for (int i :result) {
                System.out.print(i+" ");		
            }
            System.out.println();
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if(visited[i]==false) {
                result[deapth]= arr[i];
                visited[i] =true;
                recur(deapth+1);
                visited[i] =false;					
            }

        }

    }
}

중복 배제하고 원소 {1,2,3} 순열

// 중복배제

public class 경우의수2 {
	static int[] arr; //원소
	static int n ; // 답의 길이 ,깊이
	static boolean[] visited; //사용여부
	static int[] result; //답 저장배열
	public static void main(String[] args) {
		// 원소 {1,2,3} 에 대한 모든 숫자 조합
		
		arr = new int[] {1,2,3};  //반복 할 숫자
		n = 3; //출력할 숫자 조합 길이
		result = new int[n]; //정답 저장할 배열
		
		visited = new boolean[arr.length]; 
		recur(0); //깊이 0을 전달
		
	}
	private static void recur(int depth) {
		//종료조건
		if(depth==n) { //깊이와 답 길이가 동일하면
		printResult(); //result 값 출력
		return; //else안쓰려고 return을 씀
	}
		//처리코드(result에 숫자 누적)
		for (int i = 0; i < arr.length; i++) {
			if(visited[i]==false) // arr[i]의 숫자가 미 사용인 경우에만 사용
			visited[i]=true;
			result[depth] =arr[i]; //깊이 자리에 i번째 숫자저장
			recur(depth+1); // 깊이증가 후 재귀호출
			visited[i]=false;
		}
		
		
		}
	//답 출력
	private static void printResult() {
		for (int i : result) { //result에서 순서대로 추출
			System.out.print(i);	//붙여서 출력
			 
		}
		System.out.println();
		
	}
		
	
}