완전 탐색 Exhaustive Search

이번 글에서는 완전 탐색에 대한 내용을 다루겠습니다.

프로그래머스에서 코딩 테스트 연습에 완전 탐색 카테고리가 있는데

문제를 풀기 전에 개념을 확실히 짚고 넘어가는게 좋을 것 같아 정리했습니다.

---

재귀함수 Recursion Function

완전 탐색 알고리즘에서는 재귀 함수가 주로 사용되기 때문에 먼저 알아보았습니다.

재귀란, 컴퓨터 과학에서 자기 자신을 재참조하는 방법을 의미합니다. 

재귀 함수는 함수 내에서 자기 자신을 다시 호출하는 함수를 말합니다. 

즉, 자신이 수행할 작업이 일정한 패턴을 가지고 반복된다면, 패턴의 한 조각을 수행하는 함수를 만들고, 그 함수가 다시 자기 자신을 호출해서 해당 함수를 반복 실행할 수 있도록 하는 것입니다. 

 

• base case

그렇다면 이렇게 무한히 자기 자신을 호출하는 함수라면 영원히 끝이 나지 않는 상태에 빠질 수 있다는 문제가 있습니다. 이러한 문제를 해소하기 위해 재귀함수 내에는 반드시 base case 가 존재해야 합니다. 

base case 는 재귀 호출을 통한 반복에서 빠져나가기 위한 조건입니다. 

즉, 작게 분해된 작업을 수행하고, 재귀호출되면 return 되는 값이 이 조건을 만족하는지 확인한 후, 만족하지 않는다면 자기 자신을 반복 수행하고, 만족한다면 재귀 호출을 하지 않고, return 하는 것입니다. 

base case 가 없으면 재귀 함수가 영원히 끝나지 않게 되어서 반드시 함수 내에 존재해야 합니다! 

• example

def Recursion(count):
	# base case - 파라미터로 전달한 count 값이 0이면 재귀함수 종료 
	if count == 0:
    	return
        
    # recursive (count) 를 출력하는 하나의 작업     
    print("recursive", count)
    count -= 1
    
    # 재귀 호출 
    hello(count)
    
hello(5)

---

완전 탐색 Exhaustive Search 

• 완전 탐색의 개념

완전 탐색은 Brute Force 알고리즘이라고도 불립니다. 번역하면 '무식한 힘'이라는 뜻을 가진 이름인데요. 이런 이름이 붙은 까닭은 이 알고리즘은 모든 경우의 수를 전부 (무식하게) 찾아내서 답을 찾는 알고리즘이기 때문입니다. 

가능한 모든 경우의 수를 다 시도해서 답을 찾기 때문에 정확도가 매우 높지만 시도 횟수가 최대인만큼 시간이 가장 오래 걸리는 탐색 기법입니다. 

예를들어 하나의 출발점과 도착점에 대해 경로가 여러 개인 경우에 가장 짧은 경로를 찾고 싶을 때, 모든 경로의 시간을 측정해서 그 중 가장 짧은 시간이 걸리는 경로를 답으로 내놓는 것입니다. 

• 완전 탐색 기법의 종류 

이번 글에서는 무엇이 있는지만 간략이 소개하고, 각 기법을 하나의 주제로 추후 글을 작성하겠습니다. 완전 탐색 기법의 종류는 다음과 같습니다. 

• Brute Force

for문과 if문을 이용하여 처음부터 끝까지 모든 경우의 수를 탐색하는 방법 

• 비트마스크

이진수 표현을 자료구조로 사용하는 방법으로 0 또는 1 (True or False)만을 값으로 가지며, AND, OR, XOR, NOT, SHIFT 연산으로 제어합니다. 

• 재귀 함수

위 설명을 참고하시면 되겠습니다. 

• 순열

순열(permutation)은 n개의 서로 다른 원소 중 r개를 골라 순서를 고려하여 나열한 모든 경우의 수를 말합니다.  

nPr = n! / (n-r)!

• BFS, DFS

BFS는 너비우선탐색, DFS는 깊이우선탐색으로 그래프에서 아주 중요한 기법입니다. 간단히 소개하자면 깊이우선탐색은 재귀호출을 이용하여 시작 노드에서 한 방향으로 갈 수 있을 때까지 탐색하다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와 다시 다른 방향으로 분기에서 탐색을 시작하는 과정을 반복하는 것입니다. 너비우선탐색은 시작 노드에서 탐색 방향과 상관없이 인접한 노드를 먼저 탐색하는 기법입니다. 

---

 

완전 탐색 기법은 문제 해결의 기초가 되는 알고리즘이기 때문에 탄탄하게 익혀두어야 한다고 합니다. 

저도 이제 프로그래머스에서 배운 개념을 상기하면서 직접 구현해보며 연습해야겠습니다 ㅎㅎ 

프로그래머스

감사합니다 :) 

---

References

• brenden.tistory.com/10
• dojang.io/mod/page/view.php?id=2352
• velog.io/@sungjun-jin/%EC%99%84%EC%A0%84%ED%83%90%EC%83%89