[Algorithm] 완전탐색 & 재귀

01 완전 탐색

---

✔️ 완전 탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 어떻게 보면 무식한 방법이라 할 수 있다.

이 방법은 무식하게 한다는 의미로 “Brute Force (순전한 힘)”라고도 불리며, 직관적이여서 이해하기 쉽고 문제의 정확한 결과를 얻어 낼 수 있는 가장 확실하며 기초적인 방법이다.

예를 들어 4자리 비밀번호를 알아내고 싶다면 생년월일, 기념일 등으로 유추해보는 것이 아닌 0000부터 9999까지의 모든 경우의 수를 전부 대입해보는 것이다.

완전 탐색 구현 방법

1. for/while loop
2. 재귀함수

보통 간단한 문제는 for/while문을, 어려운 문제는 재귀함수를 사용한다고 생각하면 된다.

 

02 재귀

---

✔️ 재귀는 하나의 함수에서 자기 자신을 호출해 작업을 수행하는 알고리즘이다.

재귀의 가장 큰 특징은 다음과 같다.

1. 재귀가 종료되는 조건과 자기 자신을 호출하는 파트로 나뉘어져 있다.
2. 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다. (base condition)
3. 모든 입력은 base condition으로 수렴한다.

간단한 예를 들어 보자면,

const sampleCode = () => {
        if ( X == 1 ) {
                return 1;
        } else {
                return ( x * factorial(x-1) );
        }
}

위의 함수는 입력받은 수의 팩토리얼을 계산하는 함수이다.

if ( X == 0 ) { return 1 } 이 base condition 즉 종료 조건이다.

그 아래 부분이 자기 자신을 호출하는 부분이고 n이 1씩 줄어들면서 base condition인 n == 0으로 수렴하고 있다. 모든 재귀가 이 형식을 따른다.

이처럼 함수 내부에서 자기 자신을 계속 호출하는 함수를 재귀함수라고 하며, 특정 조건이 만족 될 경우 차례로 그 결과가 반환되는 방식으로

작동한다.

 

실제로 재귀 함수를 많이 활용할까?

결론 : 그렇지 않다.

Stack Overflow의 답변인데 요약해보면

재귀함수는 실무에서 쓸수 없는 방식이 아니다. 단지, 선택지 중 하나이다. 트리 구조나 같은 로직을 계속해서 반복해야 할 때 쓰기 좋다. 그러나 오버플로가 생길 수 있다. 너무 큰 데이터를 사용하지 않도록 주의하세요!

이처럼 실무에서는 큰 데이터를 많이 이용하기 때문에 재귀함수를 잘 활용하지 않는다고 생각한다.

대부분 재귀함수 대신 stack을 직접 구현하여 쓰는 경우가 더 효율적이다.

 

✔️ 재귀는 또 다음과 같은 특징을 가지고 있다.

• 모든 재귀 함수는 재귀 구조 없이 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
• 재귀는 적재적소에 사용하면 코드가 간결해지지만 함수 호출이 꽤 비용이 큰 연산이기 때문에 메모리와 시간에서 손해를 본다. 그렇기 때문에 굳이 재귀를 쓰지 않아도 구현에 큰 어려움이 없으면 재귀 대신 반복문으로 코드를 짜는것도 좋다.

 

피보나치 수열을 구하는 코드를 재귀로 구현하기 

const fibonacci = (N) => {
		if( N == 0 ) { 
			return 1;
		} else if ( N == 1 ) { 
			return 1;
		} else {
			return fibonacci(N-1) + fibonacci(N-2);
		}
}//fibonacci

//출력
fibonacci(10);