Brute-Force

Peace·2021년 1월 30일

Brute-Force

Brute-Force란

brute-force란 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법이다.
brute-force의 다른 표현은 완전 탐색이다. 완전 탐색은 가능한 방법을 전부 만들어 보는 알고리즘들을 말한다. 속도가 빠르다르는 컴퓨터의 장점을 가장 잘 이용하는 방법이다.

재귀 호출

완전 탐색을 구현 하는 방법은 여러가지 존재한다. for문과 if문, 그리고 재귀 호출(함수) 방법을 사용하는 것이다.
재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 나눈 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수이다.
ex)
for 문을 이용한 완전 탐색

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

재귀 함수 방법

int recursiveSum(int n){
	if(n == 1) return 1; //base case
    return n + recursiveSum(n-1);
}

재귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있다.

간결한 코드를 작성하는 유용한 팁

입력이 잘못되거나 범위에서 벗어난 경우를 기저 사례(base case)로 택하여 맨 처음에 처리하는 것.
--> 위와 같이 처리하면 함수를 호출하는 시점에서 따로 오류를 검사할 필요가 없다. 재귀 함수는 항상 한군데 이상에서 호출되기 때문에, 이 습관은 반복적인 코드를 제거하는 데 큰 도움이 된다.

완전 탐색 알고리즘의 시간 복잡도를 계산하는 법.

가능한 답 후보들을 모두 만들어 보기 때문에, 가능한 후보의 수를 전부 세어 보기만 하면 된다.

완전 탐색 레시피

완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간안에 생성할 수 있을지 자늠할 수 있다.
가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한조각이라고 본다.
하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
조각이 하나 밖에 남지 않은 경우, 하나도 남지 않은 경우에는 답을 생성했으므로 base case로 처리한다.

최적화 문제

어떤 기준에 따라 가장 좋은 답을 찾아내는 문제들.

ex)
n개의 사과 중 r개를 골라서 무게의 합을 최대화하는 문제, 가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화 하는 문제.

최적화 문제를 푸는 방법은 여러 가지 방법이 존재한다. 가장 기초적으로 사용할 수 있는 방법이 완전 탐색이다. 완전 탐색은 가능한 답을 모두 생성해보고 그 중 가장 좋은 답을 선택하기 때문에, 최적화 문제를 풀기 위한 가장 직관적인 방법이라고 할 수 있다.
최적화 문제를 완전 탐색으로 풀기 위해서는 시간안에 답을 구할 수 있을 지를 확인해야 된다.