[알고리즘] : 브루트 포스(C)

브루트 포스에 대해서 알아보자.

알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.

브루트 포스란?

• 완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

• 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다.

  • 선형 구조를 전체적으로 탐색하는 순차 탐색,

  • 비선형 구조를 전체적으로 탐색하는

    • 깊이 우선 탐색(DFS, Depth FirstSearch)
    • 너비 우선 탐색(BFS, breadth first search)이 가장 기본적인 도구이다.

KEY

• 주어진 문제를 선형 구조로 구조화한다.
• 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.
• 구성된 해를 정리한다.

예제1) 10의 약수의 합을 구하기

10의 약수가 될 수 있는 모든 자연수를 구조화 하자.

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10} → 문제의 해가 될 수 있는 자료를 선형으로 구성하였다.

구조화된 자료가 선형 구조이므로 순차 탐색을 활용하여 첫 번째 원소부터 마지막 원소까지 탐색한다.

탐색하면서 10의 약수가 되는 값만 남겨두고 10의 약수가 될 수 없는 값을 배제한다.

위의 과정을 거치면 집합은 다음과 같이 정리된다.

{1, 2, 5, 10}

마지막으로 탐색결과를 정리하여 최종 해를 구한다.

1 + 2 + 5 + 10 = 18

위 문제를 알고리즘으로 표현해보자

int sum = 0;
   for(int i = 1; i <= n; i = i + 1)
      if(n % i == 0)
         sum = sum + i;

예제2) 거스름돈을 지불할 수 있는 방법의 수와 최소 동전의 개수 구하기

10원과 50원으로 120원을 지불할 수 있는 모든 방법의 수와 최소 동전의 개수를 구해보자. 주어진 동전의 종류가 2가지이므로 2차원 즉 행렬의 형태로 구조화하여 일반적 방법으로 해결할 수 있다.행을 50원, 열을 10원으로 생각하고 구조화해보자.

위 행렬에서 행렬(0, 0)은 50원 동전 0개, 10원 동전은 0개를 지불하는 방법으로 생각할 수 있다.

따라서 행렬(1, 7)은 50원 동전 1개, 10원 동전 7개로 120원을 지불하는 방법이 된다.

구조화하고 행렬을 2차원으로 탐색하여 120을 이루는 모든 경우의 수를 조사하여, 구한 값들 중 행의 값 + 열의 값 합의 최솟값을 찾으면 최소 동전의 수가 된다.

■ 120원을 지불할 수 있는 모든 경우의 수 : 3가지, 최소 지불 동전의 수 : 4개

int change = 120, ways = 0, min = INF;
   for(i = 0; i * 50 <= change; i = i + 1)
      for(j = 0; j * 10 <= change; j = j + 1)
         if( (i * 50) + (j * 10) = change)
            ways = ways + 1;
            if(min > i+j)
               min = i+j;

문자열 브루트-포스법

텍스트 "ABACDEFGHA"에서 패턴 "ABC"를 브루트-포스법을 사용해 검색할수 있다.

1. 텍스트의 첫 문자 'A'부터 시작하는 3개의 문자와 "ABC"가 일치하는지 비교
2. 2-3번은 'A' , 'B'는 일치하고 'C'가 다르다.
3. 패턴을 1칸 뒤로 옮긴다. (패턴의 3번째 문자가 다른 경우)
4. 이번엔 'A'와 'B'가 다르다.
5. 패턴을 다시 1칸 뒤로 옮긴다. 
6. 'A', 'B', 'C' 모두 일치한다.

<문자열 검색 브루트-포스 코드>

#include <stdio.h>
#include <string.h>

int bf_match(const char txt[], const char pat[])
{
	int pt = 0;
	int pp = 0;
	while (txt[pt] != '\0' && pat[pp] != '\0')
	{
		if (txt[pt] == pat[pp])
		{
			pt++;
			pp++;
		}
		else
		{
			pt = pt - pp + 1;
			pp = 0;
		}
	}
	if (pat[pp] == '\0')
		return pt - pp;
	return -1;

}

int main() {
	int idx;
	char s1[256]; // 텍스트
	char s2[256]; // 패턴
	puts("브루트 포스법");
	printf("텍스트 : ");
	scanf_s("%s", s1, 256);
	printf("패턴 : ");
	scanf_s("%s", s2, 256);

	idx = bf_match(s1, s2);
	if (idx == -1)
		puts("텍스트에 패턴이 없습니다.");
	else
		printf("%d번째 문자부터 match합니다.\n", idx + 1);

	return 0;
}

<핵심코드1>

int bf_match(const char txt[], const char pat[])
{
	int pt = 0;
	int pp = 0;
	while (txt[pt] != '\0' && pat[pp] != '\0')
	{
		if (txt[pt] == pat[pp])
		{
			pt++;
			pp++;
		}
		else
		{
			pt = pt - pp + 1; 
			pp = 0;
		}
	}
	if (pat[pp] == '\0')
		return pt - pp;
	return -1;

}

//필자가 몰랐던 부분은 
- 첫 번째 if문 
ㅁㅁㅁㅁㅁ(텍스트)
ㅁㅁㅁ(패턴) ---> 오케이 성공!

- 두 번째 if문 (패턴과 vs 텍스트가 다르다)
ㅁㅁㅁㅁㅁ
ㅁㅁㅁ 
여기서 pt = pt - pp + 1;이 의미 == 뒤로 한칸 가는 것
뒤에 pp = 0으로 초기화 시키는 이유는 
패턴 값을 다시 비교해야 되기 떄문에 인덱스를 0으로 두는 것.

- 세 번째 if문 (값 자체를 찾지 못하는 경우) -1 리턴

• 텍스트에서 패턴을 검색 -> 텍스트의 위치를 반환
• 텍스트에 패턴이 여러 개 있는 경우 앞쪽에 위치한 텍스트의 인덱스 반환
• 텍스트를 스캔하기 위한 변수로 pt 사용 / 패턴을 스캔하기 위한 변수로 pp
• 스캔하거나 패턴을 옮길 때 업데이트한다.