[알고리즘] 패러다임: 브루트 포스

첫 알고리즘 포스트입니다. 공부하면서 쓰다보니 부족한 부분이 있을 수 있겠으나, 같이 공부하는 분들께 도움이 되었으면 좋겠습니다.

 

(이론 자체는 간단한 내용이기도 해 이 포스트는 간소합니다 :) )

 

출처: Pixabay 무료 이미지

 

브루트 포스(Brute-force), 주먹구구식

 

말 그대로 무식하게 푸는 것을 의미합니다. 가장 기본적인 방법입니다.

쉽게 풀어도 별 문제가 없다면, 특별한 경우가 아닌 한 굳이 어려운 길을 갈 필요가 없겠죠.

 

가능한 경우의 수를 모두 확인해 푸는 방법입니다. 즉 완전 탐색입니다.

 

가장 단순한 switch/if문 문제들과 DFS/BFS, 순열, 재귀함수, 비트마스크가 있습니다.

최적해를 보장할 수 있기에 이를 위해 사용하기도 합니다.

 

몰론 시간이 오래 걸리는 경우가 많아 엄청 많은 연산에는 쓰지 못합니다.

가령 순열의 경우를 봅시다. 1에서 N까지를 일렬로 나열하는 경우의 수를 세는 문제가 있습니다. 예를 들어 5가 입력 값으로 들어왔다고 해봅시다. 12345, 12354, 12453 ... 경우의 수를 계산하는 공식을 떠올려보면 5!의 가짓수가 있음을 알 수 있습니다. 한 자리 수라면 해볼 만 하지만, 두 자리 수도 가능하다면... 아찔합니다.

 

하지만 반대로 컴퓨터의 장점을 잘 활용할 수 있는 방식이기도 합니다.

프로그래밍 언어에 입문할 때 구구단 프로그램을 만들어본 기억이 있으실 겁니다. 사람이 구구단을 외울 때는 그래도 시간이 꽤 걸리지만, 컴퓨터는 순식간에 끝내버립니다. 빠른 연산속도의 이점을 바탕으로 쉽게 문제를 풀 수 있는 방식이라 할 수 있겠습니다.

 

-

 

재귀 호출

 

재귀 함수(recursive function)는 자기 자신을 호출하는 함수입니다.

계속 유사한 작업이 반복된다면 재귀 함수를 이용해 풀 수 있습니다. 문제를 풀기 위해 작은 작업들로 나누었을 때 for문이 비슷한 작업을 계속 실행하는 것을 자주 볼 수 있습니다. 이와 같이 문제를 작은 같은 조각들로 나누어서 푸는 문제를 재귀 함수로도 풀 수 있습니다.

 

피보나치 수열을 예시로 들어봅시다. 1+1=2, 1+2=3, 2+3=5, 3+5=8 ... (1, 1, 2, 3, 5, 8, ...) 현재 수와 이전의 수를 더해 다음 수를 만드는 일을 반복합니다. 만약 n번째 피보나치 수를 구하는 함수를 만들려고 한다고 합시다. 이를 재귀 함수로 푼다면, 다음과 같습니다.

int fibo(int n) {
	if(n <= 1) { return n; }
    else { return fibo(n-1)+fibo(n-2); }
}

 

유의해서 볼 점은 더 이상 쪼개지지 않는 가장 작은 작업에 다다르면 답을 반환하는 조건문이 필요하다는 점입니다. 이를 base case라고 합니다. 따라서 모든 입력이 base case를 이용해 답을 계산할 수 있도록 신경써야 합니다.

 

재귀 호출은 코드를 간결하게 짤 수 있도록 도와주고, 경우에 따라 연산을 줄이는데 도움을 주기도 하지만(파스칼의 삼각형 같은 경우.) 함수 호출에 의한 오버헤드가 있으므로 유의해야 합니다.

 

-

 

재귀호출과 조합

 

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

 

a, b, c, d 4가지의 수 중에서 2개를 뽑는 모든 조합을 찾으려 한다고 합시다. (단, (a,b)와 (b,a)는 같습니다.) 이를 for문으로 작성한다고 생각한다면 어떻게 될까요? 처음에 올 수 있는 알파벳 하나, 두번째에 올 수 있는 알파벳 하나 이렇게 두 개를 뽑아야 할 테니 2중 for문으로 작성할 수 있습니다. 3개를 뽑는다면? 3중 for문을 쓰면 되죠. 어... 그런데 문제가 생깁니다. 만약 알파벳의 종류가 더 많고, 뽑아야 할 것도 늘어난다면 끔찍한 코드가 됩니다. 7중 for문? 말도 안 됩니다.

 

이를 재귀 함수로 풀면 더 간단해집니다. 먼저 함수가 호출 된 후, a를 뽑고 b, c, d를 뽑는 경우를 각각 호출합니다. 이 다음에 다시 첫 함수로 돌아가 b를 뽑고 c, d를 뽑는 경우를 함수 내부에서 다시 호출합니다. 다음은 c를 뽑은 후 내부에서 호출된 함수를 통해 d를 호출하면 됩니다.

 

-

 

DFS, BFS 그리고 DP등에 대해서는 다음에 더 자세히 다뤄보도록 하겠습니다.