[알고리즘]2. 완전 탐색

완전 탐색은 무엇인가?

여러 알고리즘들이 있지만 가장 원초적이고 간단한 방법은 무식하게 하나하나 살펴보는 방법이다.

인간의 기준에서 보았을 때, 수백 개나 수천 개에 해당하는 호출은 매우 많은 양이지만 컴퓨터의 빠른 계산 능력에 있어서는 1초도 걸리지 않는 작업일 것이다. (어쩌면 컴퓨터의 장점을 가장 잘 이용한 방법이지 않나 싶다.)

그렇다면 해당 방법은 현명하지 못한 방법일까?

당연히 아니라고 자부할 수 있다.

이렇게 가능한 경우를 전부 만들어 탐색하는 방법을 완전 탐색이라고 한다.

완전 탐색은 최단 경로를 찾는 등, 하나하나 찾아보는 것이 효율적인 문제에는 가장 적합하다고 할 수 있다.

또한 첫번째 줄에서 언급하였듯이, 가장 원초적인 방법이기에 알고리즘의 기초이기에 무시할 수 없다는 것이다.

 

재귀 호출은 또 무엇인가?

재귀 호출과 완전 탐색은 땔려야 땔 수 없는 사이이다.

완전 탐색을 할 때, 주로 재귀 호출을 통하여 모든 경우를 탐색하는 경우가 대부분이기 때문이다.

그렇다면 재귀 호출은 무엇일까?

우리가 탐색하려는 범위가 작아지면 작아질수록 각각의 형태가 유사해지는 작업이 많다.

완전히 같은 코드를 반복한다면 반목문을 사용하는 되겠지만 유사해지는 것이기 때문에 반복문을 사용할 수는 없고 재귀 호출을 사용하여야 한다.

이처럼 함수 내에서 동일한 함수를 호출하는 것을 재귀 호출이라고 하고 이를 통하여 유용하게 작업을 처리할 수 있다.

또한 재귀 호출을 통해 호출된 함수를 재귀 함수라고 한다.

재귀 함수는 자신이 수행할 작업을 유사한 형태의 여러 조각으로 나눈 후, 그 중 한 조각을 수행하고 나머지를 자기 자신이 호출(재귀 호출)을 해서 실행한다.

재귀 호출도 완전 탐색과 마찬가지로 다양한 알고리즘을 구현하는 데 있어서 매우 중요한 개념이기 때문에 꼭 개념을 이해할 필요가 있다. (대표적인 예로 팩토리얼을 구현하는 함수가 있어염.)

하지만 재귀 호출의 경우, 반복문(while)과 동일하게 탈출하는 조건이 없으면 무한으로 재귀 호출되기 때문에 탈출하는 조건을 걸어두어야 한다는 점을 잊지 말자.