브루트 포스[Brute Force]

Brute Force Algorism은 "완전탐색알고리즘"으로 Brute는 "무식한"을 뜻한다.

---

무식하다? :

"가능한 모든 경우의 수를 '모두' 탐색하면서 요구조건에 충족되는 결과만을 가져온다"라는 특징에 존재한다.

*해가 존재할 것이라고 예상되는 영역을 모두 탐색!!*

---

Solution

step 1.주어진 문제를 선형으로 구조화하기

step 2.구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색한다.

step 3.구성된 해를 정리한다.

---

브루트 포스 문제의 종류

자료의 구조가

1) 선형구조 ->순차 탐색

2) 비선형구조 -> BFS, DFS

---

활용 문항

---

 

#2798_블랙잭

Solution)

1. 모든 Card를 List안에 넣는다.

2. Itertools 의 Combination함수를 활용해서 3개씩 묶어서 List를 만들어준다. (해가 존재할 것이라고 예상되는 모든 영역)

3. 값이 3개씩 묶여져 있는 리스트의 Element를 하나씩 다 sum시키고 큰 것을 탐색한다.

즉 모든 cases 를 탐색하여 풀이한다.

 

Code)

from itertools import combinations
N, M = map(int,input().split())
card = list(map(int,input().split()))
card = list(combinations(card,3))
for i in range(len(card)):
    if sum(card[i])<=M:
        card[i] = sum(card[i])
    else: card[i] = 0
print(max(card))

 

---

#1436_영화감독 숌

Solution)

입력값에 '666'이 있으면 뭐든! append시켜버리면 된다.

또는 666이 존재하면 index += 1를 하는 방식으로 활용한다면 불필요한 Data를 List에 굳이 Append시킬 필요가 없어진다.

 

Code)

number = 666
nth = 1
n = int(input())
while n > nth:
    number += 1
    if '666' in str(number):
        nth += 1
print(number)

---

1018_체스판다시칠하기