[알고리즘 문제해결전략] 알고리즘 설계 패러다임

무식하게 풀기

‘무식하게 푼다(brute-force)‘는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미합니다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 완전 탐색(exhaustive search)이라고 부릅니다.

재귀 호출과 완전 탐색

재귀 함수(recursive function)란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가르킵니다. 그렇게 자기 자신을 호출하는 것을 재귀 호출(recursion)입니다.

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

재귀 호출과 부분 문제

재귀 호출을 논의할 때 문제(problem)란 항상 수행해야 할 작업과 그 작업을 적용할 자료의 조합을 의미합니다. 재귀 호출을 하기 위해 원래 문제를 쪼개어 형식이 같은 또 다른 문제들을 만들어 내는데, 이 문제들은 원래 문제를 구성하는 조각들 중 하나를 뺐기 때문에 원래 문제의 일부라고 말할 수 있습니다. 이러한 문제들을 원래 문제의 부분 문제(subproblem)라고 합니다.

재귀 함수와 완전 탐색을 이용하여 푼 문제들은 각각의 recursion, brute force 태그를 확인하시면 찾아보실 수 있습니다.

최적화 문제

어떤 기준에 따라 가장 ‘좋은’ 답을 찾아 내는 문제들을 통칭해 최적화 문제(Optimization problem)라고 부릅니다.