문제를 처음 볼때 가장 먼저 스스로에게 물어볼 것. 무식하게 풀 수 있을까 ?
무식하게 푼다 == Brute Force
컴퓨터의 빠른 계산 능력을 가능한 경우의 수를 전부 나열하면서 답을 찾는 방법.
'무식한' 알고리즘의 좋은 예)
- 두 점 사이 최단 경로를 찾을 때 전부 다 일일이 나열하면서 답을 찾는다.
- 자원을 분배할 수 있는 경우는 경우의 수를 전부 만들어보는것.
가능한 방법을 전부 만들어보는 알고리즘을 흔히 완전 탐색 (Exhaustive search)라고 한다.
완전히 같은 코드를 반복할 때, 유용.
모든 재귀함수는 기저 사례(base case) 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야한다.
문제의 특성에 따라 재귀 호출은 코딩을 훨씬 간편하게 해 줄 수 있는 강력한 무기가 된다.
완전 탐색 레시피
-
완전탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠. 만약 시간안에 계산 불가능이라면 다른 알고리즘을 적용.
-
가능한 모든 답의 후보를 만드는 과정을 여러개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한조각.
-
그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성.
-
조각이 하나밖에 안남은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성 했으므로 이것을 기저 사례로 선택하여 처리.
같은 답을 중복으로 세는 경우 고려할것.
프로그램을 짜기 전 답의 수가 얼마나 될지 예측해 보고 모든 답을 만드는데 시간이 얼마나 오래 걸릴지 확인.
문제의 답이 하나가 아니라 여러 개 이고, 그중 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제를 통칭해 최적화 문제(Optimization problem)라고 부른다.
최적화 문제를 해결하는 방법 중 기초적인 것이 완전 탐색이다.
완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법. 가능한 답을 모두 생성해보고 그중 가장 좋은 것을 찾아내면 되기 때문.
주어진 원소로 만들 수 있는 모든 순열 만들기, 주어진 원소 중 R개를 골라낼 수 있는 방법 만들기 등 다른 문제의 부분 문제로도 빈번히 출제된다.
서로 다른 N개의 원소를 일렬로 줄 세운 것이 순열(permutation).
- 가능한 순열의 수는 N!이 되는데 10을 넘어간다면 모든 순열을 제한 시간내에 생성하기 어려우므로 완전 탐색 말고 다른 방법을 생각해야한다.
서로 다른 N개의 원소 중 R개를 순서 없이 골라낸 것이 조합(combination).
~ 한 가운데 5가지 중 3가지를 고르는 조합이 조합의 좋은 예.
골라낸 것들은 언제 골랐던지 상관없기 때문. (1,2,3 == 3,2,1)
이때 경우의 수는 이항 계수 (N R)로 정의.
n개의 질문에 대한 답이 True/False 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수. 2ᴺ