[알고리즘] #2_2021 KATABI 알고리즘스터디_브루트 포스

브루트 포스란, 완전탐색 알고리즘 기법 중 하나로

가능한 모든 경우의 수를 모두 탐색하면서 요구 조건에 충족되는 결과만 가져오는 방식의 알고리즘이다. 

 

모든 경우를 다 구해서 그 중 만족하는 답을 찾아내는 '문제를 푸는 과정' 자체가 완전탐색이다. 이 방식은 100%로 

옳은 답을 구해낼 수 있는 강력한 방법이다. 

 

브루트 포스의 개념 

EX) 1부터 100까지의 합을 구하는 문제

1부터 100까지 차례차례 하나씩 계산해나가는 것

 

브루트 포스의 필요성

1. 아주 단순한 알고리즘

2. 항상 최적의 해를 구할 수 있음

 

브루트 포스의 문제점

1. 좋은 성능 X

2. 많은 자원을 필요로 하고, 복잡도에 민감

 

암호학적인 관점에서의 브루트 포스 

brute (난폭한, 무식한) + force (힘) = brute force (무차별 대입 공격) 

 

EX) 2자리의 암호

00부터 99까지의 수를 전부 대입해서 암호를 푸는 방식

 

하나씩 대입하는 무식한 방법이지만, 정확도 100%를 보장

하지만, 아무리 연산이 빠른 컴퓨터라 해도 오랜시간이 소요된다는 단점 존재

시간적 자원을 많이 필요로 하고, 유의미한 시간 내에 암호를 풀어낼 수 있는 가능성 ↓

 

 

---

 

* 문제링크 https://www.acmicpc.net/problem/2798

2798번: 블랙잭

 

 

내가 구현한 브루트 포스 (블랙잭) 문제 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {
	int N, M, i, j, k, sum;
	int near=0;
	int arr[100] = { 0 }; //N(3 ≤ N ≤ 100) 이므로 100짜리 배열 선언

	//첫번째 입력으로 N과 M 받기 
	printf("정수 N M 입력 : ");
	scanf("%d %d", &N, &M);

	//N개의 숫자를 입력받아 arr[] 배열에 넣어주기 
	printf("%d 개의 숫자를 입력 : ", N);
	for (i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}

	for (i = 0; i < N; i++) { //첫번째 카드 
		for (j = i + 1; j < N; j++) { //두번째 카드
			for (k = j + 1; k < N; k++) { //세번째 카드
				sum = arr[i] + arr[j] + arr[k]; //카드 1+2+3의 값을 sum에 넣기 

				if (sum <= M && near < sum) { //sum은 M보다 작거나 같고, 근접한 값이 sum보다 작으면
					near = sum;
				}
			}//end of for(k)
		}//end of for(j)
	}//end of for(i)

	printf("블랙잭 : %d", near);
}

 

---

 

zoom으로 온라인 스터디 진행

 

두번째 스터디는 첫번째보다 더 순조롭고 빠르게 진행할 수 있었다. 

재귀에 이어 오랜만에 C언어를 이용해 코드를 짜니 약간의 어려움이 있었다. 

 

1학년 때 구매해뒀던 C언어책을 이용해 다시 공부를 시작해보려고 한다.