[알고리즘] 완전탐색 (Brute Force)

모든 공격로를 다 찌르는 기법 - Brute Force

 

몇 년만에 코딩테스트 대비 알고리즘 문제해결을 위한 학습을 다시 시작했다. 비교적 간단한 개념인 완전탐색을 그 시작으로 가볍게 시작해보자

 

완전탐색 혹은 Brute Force 라고 불리는 이 기법은 그 자체 그대로 '완전하게 탐색을 한다' 의 의미를 갖고 있다.

좀 더 구체적으로 가보자면, 완전하게 탐색을 한다는 것은 문제가 주어지고 해당 문제에서 원하는 정답을 찾기위해서 모든 경우의 수를 다 찾아보는 것이다.

 

 

철수가 과일가게를 갔는데, 살 수 있는 과일은 2가지이고 과일가게에서 파는 과일은 사과, 배, 키위, 수박, 메론, 두리안 이렇게 6개이다. 그리고 철수는 1,000원을 갖고 있고, 각 과일의 가격은 순서대로 200, 250, 310, 680, 680, 200원 이다. 그렇다면 철수가 거스름돈을 최대한 남기지 않는다 가정했을 때 살 수 있는 경우의 수를 구해야 한다고 가정해보자.

 

이렇게 된다면, 사람은 간단하게  '680원이랑 310원짜리 사면 되겠네~' 라고 할 것이다. 하지만 프로그램으로 만들 때 이렇게 모든 경우의 수를 하나하나 탐색해야 원하는 정답을 얻을 수 있다. 그리고 모든 경우의 수를 다 탐색한다라는 의미에서 완전탐색-Brute Force 이라는 용어를 사용한다.

 

---

 

그럼 문제를 통해서 완전 탐색에 대하여 더 자세히 알아보자.

 

이 문제에서 내가 완전탐색으로 접근한 이유는 먼저 모든 경우의 수를 탐색해서 M에 가까운 숫자 조합을 찾아야 했기 때문이다. 그리고 하나 더 중요한 것은 N의 범위가 3에서 100이하이기 때문에, for문으로 모든 경우의 수를 다 탐색해도 최악의 경우의 수를 따진다 하여도 970,200번 밖에 for문이 돌아가지 않는다. 시간복잡도에도 걸리지 않고 모든 경우의 수를 다 탐색할 수 있으니 완전 탐색을 돌릴 수 있는 것이다.

 

그래서 내가 제출한 코드는 아래와 같다.

 

#include<cstdio>

int main() {

	int n, m, card[105], sum = -1, ans = -987654321;

	scanf("%d %d ", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%d", card + i);

	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int k = j + 1; k < n; k++) {
				sum = card[i] + card[j] + card[k];
				if (sum >= ans && sum <= m) {
					ans = sum;
				}
			}
		}
	}

	printf("%d", ans);
	return 0;
}

https://www.acmicpc.net/problem/2798

 

2798번: 블랙잭

---

가장 쉬운 기법으로 이번 포스팅은 대충 때웠다. 아싸구리 데헷. 다음에는 뭘 할지 또 물색하고 공부하고 정리해서 포스팅을 해야겠다. 으쌰으쌰 우와앙~