[알고리즘] 무식하게 풀기(Brute-Force)

<알고리즘 문제해결 전략>의 해당 단원 밑줄입니다.

 

"공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련이고, 그래서 바로 앞에 보이는 쉽고 간단하며 틀릴 가능성이 낮은 답안을 간과하기 쉽습니다."

 

"컴퓨터의 최대 장점은 결국 속도가 빠르다는 것이니까요. 특히 현실 세계의 문제 중에는 입력의 크기가 작아 컴퓨터가 처리하기에는 별 것 아니지만, 손으로 직접 풀기에는 경우의 수가 너무 많은 경우가 종종 있는데, 이럴 때 완전탐색(가능한 방법을 전부 만들어 보는 알고리즘)은 충분히 빠르면서도 가장 구현하기 쉬운 대안이 됩니다."

 

"우리가 들여다 보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있습니다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 호출입니다. 재귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있습니다. 떄문에 재귀 호출은 완전 탐색을 구현할 때 아주 유용한 도구입니다."

 

"'더이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 합니다. 이 때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례라고 합니다.

 

"문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은'답을 찾아내는 문제들을 통칭해 최적화 문제라 부릅니다. 완전 탐색은 최적화 문제의 가장 기초적이고 직관적인 해결 방법입니다. 가능한 답을 모두 생성해 보고, 그중 가장 좋은 것을 찾아내면 되기 때문입니다."

​