완전탐색

완전 탐색이란?

 

완전 탐색은 컴퓨터의 빠른 계산 능력을 이용한 알고리즘으로, '모든 경우의 수를 통해 답을 찾는 알고리즘' 입니다.

 

그리고 완전 탐색 기법의 종류는 다음과 같습니다.

 

1. 재귀 함수

2. 브루트 포스법

3. 비트마스크

4. 순열

5. 깊이우선탐색(DFS), 너비우선탐색(BFS)

6. 백트래킹

 

완전 탐색을 구현하기 위해 보통 재귀 함수를 많이 사용합니다.

 

 

1. 재귀 함수

 

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 합니다. 즉, 되부름이라 할 수 있습니다. 재귀를 효과적으로 사용하면 프로그램을 간결하게 할 수 있지만 잘못 사용하면 무한 루프를 돌 수도 있습니다. 

 

재귀함수의 기초적인 예로는 팩토리얼, 피보나치가 있습니다. 

 

jinijiniblog.tistory.com/64

[백준 1003] 피보나치 함수 - 자바(java)

 

 

 

2. 브루트 포스법

 

브루트-포스법은 선형 검색을 확장한 알고리즘으로 단순법, 소박법이라고도 합니다. 단순하게 처음부터 끝까지 탐색하는 방법으로 for문과 if문을 이용하면 됩니다. 브루트-포스법은 검사를 진행한 위치를 기억하지 못하므로 효육이 좋지 않다고 할 수 있습니다.

 

브루트-포스법과 관련된 문제는 다음과 같습니다. 

 

jinijiniblog.tistory.com/37

[백준 2798] 블랙잭 - 자바

 

 

 

3. 비트마스크

 

비트마스크에서 비트는 이진수의 bit를 의미합니다. 즉, 비트마스크는 정수의 이진표현을 활용한 기법을 말합니다.

 

비트마스크를 이용하기 위해서는 비트 연산자를 사용합니다. 비트 연산자에는 AND, OR, XOR, NOT, SHIFT 연산 등이 있습니다.

 

(문제 예시는 나중에 업로드할 예정입니다.)

 

 

 

4. 순열

 

순서가 부여된 임의의 집합입니다. 여기서 '순서'에 중점을 두어야 합니다. ABCD와 ABDC, ADCB와 같이 같은 영단어를 사용해도 다른 순열이 됩니다. 

 

순열을 생성하는 방법으로는 for문, 재귀 함수, 비트마스크 등이 있습니다.

 

(나중에 업로드될 예정입니다.)

 

 

 

5. 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

이 두가지 개념을 알기 위해서는 트리의 개념을 먼저 알아야 합니다. 

 

출처: 나무위키

 

위와 같은 자료구조 형태를 트리라고 합니다. 트리의 가장 윗부분에 있는 A가 루트(root)가 되고, 트리의 가장 아랫부분에 위치하는 노드인 H, I, E, F, G가 리프가 됩니다.

 

 

깊이 우선 탐색: 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법입니다. 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게 돌아갑니다.

 

너비 우선 탐색: 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려갑니다.

 

jinijiniblog.tistory.com/51

[백준 15649] N과 M (1) - 자바(java)

 

 

 

6. 백트래킹

 

앞에서 나온 깊이 우선 탐색, 너비 우선 탐색의 경우 모든 곳을 방문하면서 찾기 때문에 비효율적입니다.

그래서 나온 방식이 백트래킹 알고리즘입니다. 간단하게 '가치치기' 라고 생각하면 쉽습니다.

나무에 비유하자면 자라나는 가지들 중에서 시들시들해 더 이상 자라지 못할 것 같은 가지를 제거하는 것과 비슷합니다.

백트래킹은 노드의 유망성을 점검하고 유망하지 않다면 뒤로 되돌아간 후 다른 노드를 탐색하는 방법입니다. 이를 통해 좀 더 효율적으로 탐색을 할 수 있습니다. 

 

jinijiniblog.tistory.com/51

[백준 15649] N과 M (1) - 자바(java)

 

 

 

 

 

 

#혹시 개념상 오류가 있거나 추가적인 설명을 하고 싶은 분은 댓글 남겨주시면 감사하겠습니다!