Algorithm paradigm 1. 재귀와 완전탐색

재귀와 완전탐색

우선 재귀 함수에 대해 설명하기 전에 두 코드를 비교해보자.

1. 반복문을 통한 1 부터 n 까지의 합

int sum(int n) {
   int ret=0,i;
   for(int i=1; i <= n; i++)
      ret += i;
   return ret;
}

2. 재귀 함수를 통한 1 부터 n 까지의 합

int recursiveSum(int n) {
   if (n==1) return 1; //더 이상 쪼개지지 않을 때
   return n + recursiveSum(n-1);
}

모든 재귀함수는 위와 같이 더 이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야한다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례라고 한다.

재귀호출은 1번과 같은 반복문과 그리 큰 차이는 없지만 코딩을 훨씬 간편하게 해줄 수 있다.

재귀 함수는 완전 탐색이라는 무식하게 모두 세는 방식을 사용하여 알고리즘을 짤 때 좋다.

처음에 문제를 파악한 뒤 재귀 함수를 써야한다면 기저 사례를 선택해야한다. 여기서 팁이 있다면, 입력이 잘못되었거나 범위에서 벗어난 경우도 기저 사례로 택해서 처음에 처리하면 함수 호출 과정에서 오류 검사를 할 필요가 없어지기 때문에 속도가 빨라진다.

많이 등장하는 완전 탐색 유형

1. 모든 순열 만들기

서로 다른 N 개의 원소를 일렬로 줄 세운 것을 순열이라고 한다.

int factorial(int n)
{
if (n <= 1) return 1; //위에서 본 기저 사례
return n*factorial(n - 1);
}

2. 모든 조합 만들기

서로 다른 N 개의 원소 중에서 R 개를 순서 없이 골라낸 것을 조합이라고 한다.

int binco(int n, int k)
{
if (k == 0 || n == k) return 1; //위에서 본 기저 사례
else return binco(n - 1, k - 1) + binco(n - 1, k);
}

int main()
{
int n, k;
scanf_s("%d %d", &n, &k);
if (!(0 <= k && k <= n) || (n < 0)) return 0;
printf("%d", binco(n, k));
}

3. 2^n 가지 경우의 수 만들기

n 개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수는 2^n가지이다.

출처 : 알고리즘 문제해결 전략