브루트 포스(Brute Force)는 컴퓨터 과학에서 문제를 해결하기 위해 가능한 모든 경우의 수를 탐색하는 방법입니다. 다른 말로는 완전 탐색(Exhaustive Search)이라고도 합니다. 브루트 포스는 간단하고 직관적인 방법으로, 가능한 모든 조합을 시도하여 정확한 해답을 찾는데 사용됩니다.
브루트 포스 알고리즘의 단점은 가능한 모든 경우의 수를 시도하기 때문에 입력의 크기에 따라 실행 시간이 기하급수적으로 늘어날 수 있다는 점입니다. 따라서 브루트 포스는 작은 입력에 대해서는 효과적이지만, 큰 입력에 대해서는 실행 시간이 매우 오래 걸리는 경우가 있습니다.
브루트 포스는 다양한 문제 유형에서 활용될 수 있으며, 특히 문제의 가능한 경우의 수가 상대적으로 작을 때 효과적입니다. 예를 들어, 조합 가능한 비밀번호를 찾는 문제, 작은 데이터 세트에서의 최적해 찾기, 문자열 검색 등이 브루트 포스 알고리즘을 적용할 수 있는 예시입니다.
브루트 포스는 정확한 해답을 찾는데 사용되지만, 실행 시간이 길어지는 단점이 있으므로 큰 입력에 대해서는 다른 최적화된 알고리즘을 고려해야 합니다.
- 문제에 대한 가능한 해답의 범위를 정합니다.
- 가능한 모든 해답을 순차적으로 생성하면서, 각 해답이 문제의 조건을 만족하는지 검사합니다.
- 조건을 만족하는 해답이 있을 경우, 해당 해답을 반환하거나 결과로 활용합니다.
def main():
# 사용자로부터 두 개의 정수를 입력받습니다.
# N과 M은 map 함수를 사용하여 한 줄에서 두 정수를 입력받습니다.
N, M = map(int, input().split())
# arr 리스트를 생성하여 1002개의 원소를 False로 초기화합니다.
# 이 리스트는 입력된 정수들을 체크하기 위한 용도로 사용됩니다.
arr = [False] * 1002
# v 리스트는 입력된 정수들을 체크한 후에 False로 남아있는 수들을 저장하는 리스트입니다.
v = []
# 사용자로부터 정수들을 입력받아 arr 리스트에서 해당하는 원소를 True로 변경하여 입력된 정수들이 arr 리스트에서 체크되었음을 표시합니다.
for i in map(int, input().split()):
arr[i] = True
# v 리스트에는 arr 리스트에서 False로 남아있는 수들이 저장됩니다.
for i in range(1, 1002):
if not arr[i]:
v.append(i)
# result 변수를 2147483647로 초기화합니다.
# result 변수에는 입력된 정수 N과 v 리스트의 세 수를 곱한 값과의 차이를 계산하여 최솟값을 저장합니다.
result = 2147483647
# sz 변수에는 v 리스트의 길이를 저장합니다.
# sz 변수는 반복문에서 범위를 지정하는데 사용됩니다.
sz = len(v)
# 이제 세 수를 곱하여 N과 가장 가까운 값을 찾기 위해 세 개의 반복문이 사용됩니다.
for i in range(sz):
for j in range(sz):
for k in range(sz):
# 세 수를 모두 v 리스트에서 선택하여 곱하고,
q = v[i] * v[j] * v[k]
# 이 곱셈 값과 N과의 차이가 현재까지의 최솟값인 result보다 작으면 최솟값을 갱신합니다.
if abs(N - q) < result:
result = abs(N - q)
# N보다 큰 경우에는 더 이상 반복할 필요가 없으므로 해당 반복문을 종료합니다.
if N + 1 < q:
break
# 최종적으로 result에 저장된 최솟값을 출력합니다.
print(result)
if __name__ == "__main__":
main()