Contents
- Brute-force algorithm
1-1. 모의고사 문제 풀이 - Recursive functions
2-1. Factorial
2-2. Exponentiation
1. Brute-force algorithm
A brute force algorithm is a simple and straightforward approach to solve a problem by trying every possible solution until finding the best one.
Brute-force search 를 이용한 알고리즘은 말 그대로 가능한 경우들을 일일이 나열하며 "완전탐색" 하여 답을 찾는다. 이는 우리가 직접 문제를 해결하기에 경우의 수가 너무 많지만 컴퓨터는 금방 처리할 수 있을 때 적합한 방법이다.
앞서 말했듯이 가능한 모든 상황을 고려하기 때문에 그 중에는 관련이 없거나 redundant 한 경우의 수들이 분명 존재한다. 즉, 우리는 완전탐색 시 알고리즘이 handle 해야 할 경우의 수의 범위를 판단할 줄 알아야 한다.
| Pros | Cons |
|---|---|
| • Simple and applicable to a wide range of problems. | • Inefficient and time-consuming. |
| • Basis for better algorithms. | • Lack of creative and constructive algorithms. |
따라서 brute-force algorithm 의 특성상 small and simple problems 에 적합하다. 하지만 이를 다시 말하면 그 반대의 경우에는 실행 불가능할 정도로 느릴 것이며, 실제로도 완전탐색은 "rarely produces efficient algorithms" 이다. 또한 완전탐색의 시간 복잡도는 모든 경우의 수와 같아 매우 간단하다.
1-1. 모의고사 문제풀이
다음은 programmers 에서 제공되는 완전탐색에 관한 문제 중 하나이다.
<문제>
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.
1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...
<제한 조건>
시험은 최대 10,000 문제로 구성되어있습니다.
<나의 풀이>
def solution(answers):
student1 = [1, 2, 3, 4, 5]
student2 = [2, 1, 2, 3, 2, 4, 2, 5]
student3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
scores = [0, 0, 0]
result = []
for idx, ans in enumerate(answers):
if student1[idx % len(student1)] == ans:
score[0] += 1
if student2[idx % len(student2)] == ans:
score[1] += 1
if student3[idx % len(student3)] == ans:
score[2] += 1
for idx, s in enumerate(scores):
if s == max(score):
result.append(idx + 1)
return result이 문제는 정답과 각 학생들의 답안을 비교하기 때문에 O(n) 의 시간이 걸린다. 시험 문제의 최대는 총 10,000 개이므로 우리는 brute-force search 이용 시 최대 만 번의 시도를 하게 되고, 이는 컴퓨터가 충분히 다룰 수 있는 양이다. 따라서 이 문제는 1) 각 학생들이 찍는 패턴을 파악하여 list 로 만들어주고 2) modulus 로 나머지를 찾아 해당 list 를 순회하며 3) 맞춘 개수를 비교하면 된다.
<참고>
enumerate(iterable, start = 0) adds a counter to an interable.
- It returns an iterator with index and element pairs from the original iterable as an enumerating object.
2. Recursive functions
재귀함수라 불리는 recursive functions 는 함수 내에서 자신을 계속 호출해 실행하는 방법이다. 이를 위해 우리는 컴퓨터가 수행해야 하는 많은 작업들을 여러 개의 작은 비슷한 조각들로 나눌 수 있어야 한다. 이 아이디어의 핵심은 바로 "들여다보는 범위가 작아질수록 각 조각의 형태가 유사해진다" 는 것이다.
Recursive function calls itself in its own definition. It is often used to solve problems that can be broken down into smaller, identical subproblems.
따라서 recursive function 은 완전탐색 구현 시 매우 유용한 도구이다. 왜냐하면 재귀 호출 이용 시 중첩 for 문을 사용하지 않고도 특정 조건을 만족하는 모든 조합을 쉽게 생성할 수 있기 때문이다.
모든 재귀 함수는 더 이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야 한다! 이 때, 쪼개지지 않는 가장 작은 작업들을 가리켜 base case 라고 한다.
이해를 돕기 위해 다음의 두 예시 문제들을 보도록 하자.
2-1. Factorial
만약 어떤 수 n 이 주어졌을 때 n! 을 구하고자 한다면 우리는 중첩 for 문을 쓰지 않고도 recursive function 을 이용해 구현할 수 있다. 왜냐하면 각 단계를 n 에서 -1 을 한 값을 곱해주는 identical 한 subproblems 로 나눌 수 있기 때문이다.
def factorial(n):
if n == 1:
return 1
return n * factorial(n-1)아래의 그림은 recursive function 의 calling 과 return 의 순서를 나타낸 것이다. 이 때, base case 는 n == 1 일 때이다.
2-2. Exponentiation
두 번째 예시로는 거듭제곱을 들 수 있다. Base 와 power 가 주어졌을 때 power 는 하나씩 줄어들면서 base 를 하나씩 곱하는 subproblems 로 나눌 수 있고, 이 때 base case 는 power 가 0 일 때 , 즉 1 이 되는 것이다.
def exponentiation_recursive(base, k):
if k == 0:
return 1
return base * exponentiation_recursive(base, k-1)