[알고리즘/Java] 완전탐색

go_go_·2022년 7월 15일

알고리즘

목록 보기

2/12

✔ 목차

완전탐색이란?
단순 Brute-Force
비트마스크
재귀함수
순열
BFS / DFS

🔎 완전탐색이란?

모든 경우의 수를 시도하여 정답을 찾는 방법이다. 무식하게 푼다는 의미로 Brute Force라고도 한다. 상대적으로 간단한 방법이지만 경우의 수가 많아지면 시간이 오래걸린다는 단점이 있다.

예시
4자리 번호로 된 자물쇠를 풀기 위해서 각 자리에 0~9 번호를 넣어보는 것이다. 즉, 0000부터 9999까지 해보는 것이다. 이 때 경우의 수는 10^4 = 10,000이다.

완전탐색 기법 종류
- Brute Force
- 비트마스크
- 재귀함수
- 순열
- BFS/DFS

🔎 단순 Brute-Force

특별한 기법 없이 for문과 if문으로 모든 경우의 수를 체크하여 답을 구함
이 방법으로 해결 할 수 있는 문제가 많지 않음
문제 일부분 해결할 때 사용

🔎 비트마스크(Bitmask)

각 원소를 두 가지 상태로 분류할 수 있을 때 사용
ex) 모든 경우의 수에서 각각의 원소가 포함되거나 포함되지 않는 경우
예시
원소 n개인 집합의 부분집합 구하기

🔎 재귀함수

재귀(Recursion)은 자기 자신을 호출한다는 뜻이다. 뜻에서 알 수 있듯이 재귀함수는 자기 자신 함수를 호출하여 작업을 수행한다.

재귀함수: 자기 자신을 호출
호출된 함수 스택에 저장, 호출 완료 시 스택에서 삭제
for, while같은 반복 코드를 간결하게 짤 수 있음
재귀함수 작성 시 주의 사항: 사이클 발생하지 않아야 함
- 재귀 탈출 조건이 없는 경우 재귀함수는 계속하여 자기 자신을 호출하는 무한 루프에 갇히고 스택 오버플로우가 일어난다.
- 재귀 탈출 조건을 적어주거나 재귀 발생 횟수를 정해줘야 한다.

🔎 순열

서로 다른 n개를 일렬로 나열하는 경우의 수(순서 o)
=> n!
서로 다른 n개중 r개를 뽑아 일렬로 나열하는 경우의 수(순서 o)
=> n!/(r-1)! = nPr
시간 복잡도: O(n!)
시간 복잡도가 높은 편이라 n이 한 자리 수 경우일 때 고려
c++에서 순열을 구하는 next_permutation() 함수가 있지만 자바에는 따로 없음 -> 직접 구현해야 함

java로 구현한 순열 - 재귀함수 사용

public class PermutationMain {
	
    //순열 구하기
	public static void Permutation(String[] arr, int start, int end) {
		if(start == end) {
			for(String i : arr) {
				System.out.print(i+" ");
			}
			System.out.println("");
		}
		else {
			for(int i = start; i <= end; ++i) {
				swap(arr, start, i);
				Permutation(arr, start+1,end);
				swap(arr, start, i);
			}
		}
	}
	
    //인덱스 원소 바꾸기
	public static void swap(String[] arr, int a, int b) {
		String temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
		
	}
	
	//예시) arr = ["A", "B", "C"] 순열 출력
	 public static void main(String[] args) {
			String[] arr = new String[] {
				"A", "B", "C"	
			};
			Permutation(arr, 0, arr.length-1);
		}
    
}
    
    출력
	A B C 
	A C B 
	B A C 
	B C A 
	C B A 
	C A B 

}

작동원리 그림

🔎 BFS / DFS

너비 우선 탐색(BFS, Breadth-First Search)
- 하나 노드 방문 후 인접한 모든 노드 우선 방문
- 두 노드 사이 최단 경로 구할 시 자주 사용
- 큐 사용하여 구현
깊이 우선 탐색(DFS, Depth-Fist Search)
- 하나 노드 방문 후 그 노드의 모든 자식 노드 우선 방문
- BFS보다 검색 속도 느림
- 재귀함수 사용하여 구현