전체탐색

전체탐색법은 모든 문제해결의 기초가 되는 설계법으로,

주어진 문제 상황에 대해서 해가 될 수 있는 모든 경우를 검사해 답을 구한다.

이러한 특성 때문에, 항상 정확한 결과를 얻을 수 있지만, 탐색할 경우의 수가 

많아지면, 제한 시간 이내에 해결 할 수 없게 되버린다.

전체 탐색법은 선형/비선형구조의 탐색을 기반으로 문제를 해결한다.

선형구조의 전체 탐색:

반복실행 구조를 이용해 간단히 구현할 수 있는데, 1차원도 2차원도 결국 선형구

조이므로, 다차원 구조도 선형으로 간주한다.

비선형구조의 전체탐색:

재귀함수를 이용한 백트래킹이다.

전체 탐색법을 활용한 예시:

#include <stdio.h>
 
int f(int n, int d);
 
int main(void)
{
    int n;
    int sum = 0;
 
    scanf("%d", &n);
    sum = f(n, 1);
    printf("%d", sum);
    
}
 
int f(int n, int d)
{
    if (n == d)
        return n;
    else
    {
        if (n % d == 0)
        {
            return d + f(n, d+1);
        }
        else
            f(n, d + 1);
    }
}

약수의 합 구하기.

#include <stdio.h>
 
void input(int arr[9][9]);
 
void find(int arr[9][9], int *x, int *y, int *max);
 
int main(void)
{
    int arr[9][9];
    int max = 0x80000000;
    int x, y;
 
    input(arr);
    find(arr, &x, &y, &max);
    printf("%d\n%d %d\n", max, x, y);
}
 
 
void input(int arr[9][9])
{
    int i, j;
    for (i = 0; i < 9; i++)
    {
        for (j = 0; j < 9; j++)
        {
            scanf("%s", &arr[i][j]);
        }
    }
}
 
 
void find(int arr[9][9], int *x, int *y, int *max)
{
    int i;
    int j;
 
    for (i = 0; i < 9; i++)
    {
        for (j = 0; j < 9; j++)
        {
            if (*max < arr[i][j])
            {
                *x = i + 1;
                *y = j + 1;
                *max = arr[i][j];
            }
        }
    }
}

정리:

전체 탐색법은 모든 경우를 조사하는 방법으로, 가장 간단하다.

기본적인 전체탐색은 반복실행으로 모든경우에 대해 검사한다.