Brute Force (브루트 포스, 완전 탐색)

브루트 포스 알고리즘이란 무엇일까?

브루트 포스는 발생할 수 있는 모든 경우를 구하여 전체적으로 탐색하는 방식이다.
즉, 완전 탐색이라고도 한다.

브루트 포스(완전 탐색)은 해가 하나 이상 존재한다라는 가정을 세우고 모든 범위를 탐색하기 때문에 무조건 정답을 찾을 수 있다.

브루트 포스의 장점 ⭕

• 알고리즘을 설계하고 구현하는데 매우 쉽다
• 복잡한 알고리즘 없이 빠르게 구현이 가능하다.

브루트 포스의 단점 ❌

• 알고리즘의 실행 시간이 매우 오래 걸린다.
• 메모리 효율면에서 매우 비효율적이다.

브루트 포스의 종류

크게 선형 구조와 비선형 구조로 나눌 수 있다.

선형 구조

• 순차 탐색 : 1 → 2 → 3 → 4

비선형 구조

• 백트래킹
• DFS
• BFS

해당 알고리즘은 다른 게시글에서 소개하겠다.
우선, 순차 탐색에 대해 먼저 알아보자 ❗

브루트 포스의 적용

순차 탐색

순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.

아래의 리스트에서 5를 찾는다고 가정해보자.

우선, 가장 먼저 첫 번째 데이터를 확인한다.
2 != 5 이므로 다음 인덱스로 넘어간다.

두 번째 데이터를 확인 해본다.
1 != 5 이므로 다음 인덱스로 넘어간다.

이렇게 반복하면, 아래와 같이 5를 찾을 수 있다. 찾았을 경우에 탐색을 마친다.

순차 탐색 코드

순차 탐색을 파이썬 코드로 작성해 보자 ❗

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
	# 각 원소를 하나씩 확인
    for i in range(n):
        # 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
            return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1을 더한다.)

print('생성할 원소 개수를 입력한 뒤, 한 칸 띄고 찾을 문자열을 입력하시오.')
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print('앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.')
array = input.split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

브루트 포스 문제

백준 2798번 블랙잭 문제 📌

OOO에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 OOO마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

• 문제의 핵심은 M과 최대한 가까운 카드 3장을 고르는 것이다.

  OOO → Velog에서 비공개 키워드로 설정되어 있어 OOO로 변경하였음

Solution

import sys

N, M = map(int, sys.stdin.readline().split()) # 카드의 개수 N, 최대 M
card = list(map(int, sys.stdin.readline().split())) # 카드의 숫자

answer = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            if card[i] + card[j] + card[k] <= M:
                answer = max(answer, card[i] + card[j] + card[k])

print(answer)

• 첫 번째 값부터 3장씩 더해보면서 가장 가까운 값을 골라서 저장하는 방식으로 접근하였다.

[References]
https://foreverhappiness.tistory.com/104
나동빈 저자의 이것이 코딩 테스트다 with 파이썬 책을 참고하였습니다.