[종만북] Brute Force / 무식하게 풀기

Algorithmic Problem Solving Strategies 

개인적으로 읽고 정리한 요약 입니다.

아래 링크에 문제 풀이 예제가 있습니다.

GitHub - chanheki/AlgorithmicProblemSolvingStrategies: Algorithm Book Study

무식하게 풀기

도입

문제를 처음 볼때 가장 먼저 스스로에게 물어볼 것. 무식하게 풀 수 있을까 ?

무식하게 푼다 == Brute Force

컴퓨터의 빠른 계산 능력을 가능한 경우의 수를 전부 나열하면서 답을 찾는 방법.

'무식한' 알고리즘의 좋은 예)

• 두 점 사이 최단 경로를 찾을 때 전부 다 일일이 나열하면서 답을 찾는다.
• 자원을 분배할 수 있는 경우는 경우의 수를 전부 만들어보는것.

가능한 방법을 전부 만들어보는 알고리즘을 흔히 완전 탐색 (Exhaustive search)라고 한다.

---

재귀 호출과 완전 탐색

- 재귀 호출

완전히 같은 코드를 반복할 때, 유용.

모든 재귀함수는 기저 사례(base case) 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야한다.

문제의 특성에 따라 재귀 호출은 코딩을 훨씬 간편하게 해 줄 수 있는 강력한 무기가 된다.

- 완전 탐색

완전 탐색 레시피

1. 완전탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다. 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠. 만약 시간안에 계산 불가능이라면 다른 알고리즘을 적용.
2. 가능한 모든 답의 후보를 만드는 과정을 여러개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한조각.
3. 그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성.
4. 조각이 하나밖에 안남은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성 했으므로 이것을 기저 사례로 선택하여 처리.

---

예외 케이스 처리 / 답 수의 상한

같은 답을 중복으로 세는 경우 고려할것.

프로그램을 짜기 전 답의 수가 얼마나 될지 예측해 보고 모든 답을 만드는데 시간이 얼마나 오래 걸릴지 확인.

---

최적화 문제

문제의 답이 하나가 아니라 여러 개 이고, 그중 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제를 통칭해 최적화 문제(Optimization problem)라고 부른다.

최적화 문제를 해결하는 방법 중 기초적인 것이 완전 탐색이다.

완전 탐색은 최적화 문제를 풀기 위한 가장 직관적인 방법. 가능한 답을 모두 생성해보고 그중 가장 좋은 것을 찾아내면 되기 때문.

---

많이 등장하는 완전 탐색 유형

주어진 원소로 만들 수 있는 모든 순열 만들기, 주어진 원소 중 R개를 골라낼 수 있는 방법 만들기 등 다른 문제의 부분 문제로도 빈번히 출제된다.

모든 순열 만들기

서로 다른 N개의 원소를 일렬로 줄 세운 것이 순열(permutation).

• 가능한 순열의 수는 N!이 되는데 10을 넘어간다면 모든 순열을 제한 시간내에 생성하기 어려우므로 완전 탐색 말고 다른 방법을 생각해야한다.

모든 조합 만들기

서로 다른 N개의 원소 중 R개를 순서 없이 골라낸 것이 조합(combination).

~ 한 가운데 5가지 중 3가지를 고르는 조합이 조합의 좋은 예.

골라낸 것들은 언제 골랐던지 상관없기 때문. (1,2,3 == 3,2,1)

이때 경우의 수는 이항 계수 (N R)로 정의.

2ᴺ 가지 경우의 수 만들기

n개의 질문에 대한 답이 True/False 중의 하나라고 할 때 존재할 수 있는 답의 모든 조합의 수. 2ᴺ

 

 

---