1. 완전 탐색이란?
완전 탐색은 컴퓨터의 계산 능력을 이용하여 가능한 모든 경우의 수를 테스트해봄으로써 답을 찾는 방법을 의미합니다.
예를 들어 친구의 생일을 맞추는 프로그램을 짠다면, 친구의 생일에 대해 아무런 정보가 없다는 가정하에 1월 1일부터 12월 31일까지 모든 날짜가 같은 확률로 생일일 수 있습니다. 이런 문제는 결국 1월 1일부터 12월 31일까지 모든 경우의 수를 테스트해보는 것이 가장 좋다는 것이죠.
무식하게 처음부터 끝까지 모두 테스트해보기 때문에 알고리즘도 이해하기 쉽고, 결괏값을 정확하게 얻어내기도 쉽습니다.
하지만 모든 경우의 수를 탐색하는 완전 탐색의 특성상, 답이 될 수 있는 경우의 수가 너무 많은 경우에는 사용하기 힘듭니다. 특히 코딩 테스트나 백준 문제에서 무턱대고 완전 탐색을 사용한다면 시간 초과를 받게 되겠죠. 그래서 문제를 잘 읽어보고 완전 탐색을 사용할 수밖에 없는지 잘 생각해본 뒤 신중하게 사용해야 합니다. 백트래킹이나 다이나믹 프로그래밍으로 풀 수 있는 문제라면 완전 탐색으로 풀어서는 효율성을 장담할 수 없습니다.
백트래킹과 다이나믹 프로그래밍에 대해서는 아래의 링크에서 더 자세히 알아볼 수 있습니다.
https://jooona.tistory.com/116?category=842609
[알고리즘] 백트래킹
1. 백트래킹(Backtracking) 가장 대표적으로 알고 있는 완전 탐색 알고리즘으로는 DFS를 꼽을 수 있습니다. 하지만 DFS는 정말 완전히 모든 경로를 탐색하므로, 때때로 비효율적일 수 있습니다. 여기서
jooona.tistory.com
https://jooona.tistory.com/58?category=842609
[알고리즘] 다이나믹 프로그래밍
다이나믹 프로그래밍(Dynamic Programming)은, 핵심부터 설명하자면, 한 번 수행한 연산을 저장시켜두어, 다음에 해당 연산을 또 해야 할 때 기존의 연산 결과를 이용함으로써, 연산의 중복 수행을 막
jooona.tistory.com
2. 완전 탐색 기법
1. 브루트 포스
반복문, 조건문 등을 이용해 단순하게 모든 방법을 다 테스트해보는 경우를 의미합니다. 위에서 예시로 들었듯이 생일을 찾는다던가, 자물쇠의 비밀 번호를 찾는다던가 하는 예시에서 사용할 수 있습니다.
생일을 찾는 프로그램을 만든다면 for문과 if문을 이용해 다음과 같이 코드를 작성할 수 있겠네요. 월은 1월부터 12월까지를, 일은 1일부터 31일까지를 모두 탐색하면서 정답을 찾아내는 방법입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class Main {
public static void main(String[] args) {
int birthday_month = 9; // 정답 월
int birthday_date = 21; // 정답 일
for (int month = 1; month <= 12; month++) {
for (int date = 1; date <= 31; date++) {
if (month == birthday_month && date == birthday_date){
System.out.println("Your Birthday is " + month + "/" + date + " !!");
}
}
}
}
}
|
cs |
2. 재귀
재귀 함수는 자기 자신을 연속적으로 호출하여 연산을 진행하는 방법입니다. 재귀를 이용하여 완전 탐색을 할 수 있어야 dfs, 백트래킹 등의 발전된 알고리즘을 조금 더 쉽게 배울 수 있습니다.
그렇다면 재귀 함수는 언제 사용할까요? 우선 피보나치수열을 구하는 문제처럼 재귀를 사용하는 것이 알고리즘적으로 자연스러운 예시들이 있습니다. 또한, 일반적으로 재귀 함수는 함수를 단순하게 만들어주고, 변수 사용을 줄임으로써 프로그램에 오류가 생길 가능성을 줄여주게 됩니다. 10번의 반복을 해야 하는 프로그램에서 10중 for문을 만들어주는 것보다는 재귀를 통해 10번 호출하는 것이 프로그램 코드를 훨씬 깨끗하게, 그리고 이해하기 쉽게 만들어줍니다.
하지만 종료 조건을 제대로 명시해주지 않으면 무한하게 자기 자신이 호출되어 Stackoverflow와 같은 에러를 유발할 수도 있으니 설계를 잘해주어야 합니다.
아래 예시는 재귀의 가장 기본적인 예시인 피보나치수열의 재귀를 이용한 구현입니다. (굉장히 많은 반복적인 연산이 발생하기 때문에 가장 이상적인 풀이는 아닙니다. 그냥 보기 좋은 예시를 사용하기 위해 작성하였습니다.)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public class Main {
public static int fibonacci(int n) {
if (n <= 1)
return n;
else
return fibonacci(n - 2) + fibonacci(n - 1);
}
public static void main(String[] args) {
for (int i = 1; i <= 10; i++) {
System.out.println(fibonacci(i));
}
}
}
|
cs |
3. 순열
순열은 임의의 순열이 주어졌을 때 이 순열을 서로 다른 순서로 연산하는 방법입니다. 순서가 달라짐에 따라 결과가 다르게 나온다면 모든 순서의 경우의 수를 따져봐야겠죠?
예를 들어, 1 2 3을 모든 순서에 대해 순열을 만든다면 6가지 순열을 만들 수 있습니다.
123
132
213
231
312
321
모든 순열에 대해 첫 번째 요소에는 2를 곱하고, 두 번째 요소에는 3을 곱하고, 세 번째 요소에는 4를 곱해서 결과가 12가 나오는 순서를 찾아라! 와 같은 문제가 나오면 각각의 순서를 모두 따져보아야 하기 때문에 위와 같이 순열을 이용해 완전 탐색을 해야 합니다.
이러한 순열의 경우 N개의 요소를 서로 다른 순열로 나열하는 경우의 수가 N! 개가 되고, N이 커지면 굉장히 많은 탐색을 해야 하기 때문에 N의 크기가 충분히 작아야 사용할 수 있습니다.
N이 11개만 돼도 3900만 번의 연산이 필요하고 12개가 되면 4억 번이 넘어가기 때문에 10개만 넘어가도 사용하기가 어렵습니다.
예시로는 위에서 1 2 3의 순열을 만들어보는 코드를 만들어보았습니다. 물론 여러 방법이 있겠지만, 저는 visit라는 방문 여부에 대한 배열과 위에서 살펴본 재귀를 사용하여 구현을 했습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
public class Main {
static int[] arr = {1, 2, 3}; // 입력
static int[] result = new int[3]; // 결과를 담을 배열
static boolean[] visit = new boolean[4]; // 방문 여부
public static void recur(int cnt) {
if (cnt == 3) { // 종료조건: 3개의 요소를 모두 채워 넣었을 때.
for (int i = 0; i < 3; i++) {
System.out.print(result[i]);
}
System.out.println();
return;
}
for (int i = 0; i < 3; i++) {
if (visit[arr[i]] == false) { // 아직 사용하지 않은 요소에 대하여
visit[arr[i]] = true;
result[cnt] = arr[i];
recur(cnt + 1); // 재귀 실행
visit[arr[i]] = false;
}
}
}
public static void main(String[] args) {
recur(0);
}
}
|
cs |
4. dfs, bfs
그래프에서 완전 탐색을 하는 가장 대표적인 방법이 dfs와 bfs를 사용하는 것입니다.
dfs는 스택 또는 재귀를 이용하여 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 다른 정점을 탐색하는 방법이고, bfs는 큐를 이용하여 최대한 넓게 탐색한 다음, 더 이상 탐색할 노드가 없을 때 아래로 이동하며 탐색하는 방법입니다.
dfs와 bfs를 자세하게 설명하면 너무 길어질 것 같아 백준 문제 풀이 글로 대신하겠습니다.
DFS
[BOJ] 1303 - 전쟁 - 전투
-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다
jooona.tistory.com
BFS
[BOJ] 7576 - 토마토
-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N
jooona.tistory.com
'전공공부 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| [알고리즘] 코사라주 알고리즘 (0) | 2021.12.29 |
|---|---|
| [알고리즘] 백트래킹 (0) | 2021.03.09 |
| [알고리즘] 다익스트라 알고리즘 (0) | 2021.03.03 |
| [알고리즘] KMP 알고리즘 (0) | 2021.02.25 |
| [알고리즘] 다이나믹 프로그래밍 (0) | 2021.02.04 |