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

go_go_·2022년 7월 15일
3

알고리즘

목록 보기
2/12
post-thumbnail

✔ 목차

  1. 완전탐색이란?
  2. 단순 Brute-Force
  3. 비트마스크
  4. 재귀함수
  5. 순열
  6. 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보다 검색 속도 느림
    • 재귀함수 사용하여 구현

BFS / DFS 자세히 알아보기


참고사이트

profile
개발도 하고 싶은 클라우드 엔지니어

0개의 댓글