🧚‍♂️알고리즘🧚‍♂️ - 완전탐색 - 브루트 포스

브루트 포스

완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과 찾기

 

이용 도구 

선형 구조를 전체적으로 탐색하는 순차 탐색

 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)/너비 우선 탐색(BFS, breadth first search)

---

1.

브론즈2

백준 2858 기숙사 바닥

2858번: 기숙사 바닥

- 빨간색 타일의 최대 수, 갈색 타일의 최대 수를 확인해서 적당한 수를 반복문에 넣는다.

from sys import stdin
R, B = map(int, stdin.readline().split())

# 무식한 힘 탐색
for i in range(3, 2000): # ij 가로세로
    for j in range(3, i + 1): # 중복 탐색을 막기 위해 i까지만
        a = (i * 2) + ((j - 2) * 2)
        if a == R and (i * j) - a == B:
            print(i, j)

수학으로 풀 수도 있다.

---

2.

실버 3

백준 2503 숫자 야구

2503번: 숫자 야구

from sys import stdin
from itertools import permutations

N = int (stdin.readline())
result = list(permutations([1,2,3,4,5,6,7,8,9], 3)) # 미리 모든 수 넣어 놓고

for _ in range(N):
    test, s, b = map(int, stdin.readline().split())
    test = list(str(test))
    remove_cnt = 0
	
    for i in range(len(result)):  # 후보군 전부 체크 - 브루트포스
        strike = 0
        ball = 0     
        i -= remove_cnt #! pop하면 후보군 줄어듬!!

        for j in range(3): #민혁이가 말한 세자리수 
            test[j] = int(test[j])
            # 현재 후보에 해당 수 존재
            if test[j] in result[i]:
                # 위치까지 같으면 현재 후보의 스트라이크수++
                if j == result[i].index(test[j]):
                    strike += 1 
                #위치가 다르면 볼 수 ++
                else:
                    ball += 1
                    
        if strike != s or ball != b: # result 중 답(스트라이크수볼수) 가 다른 애면 후보 제외
            result.pop(i)
            remove_cnt += 1

print(len(result)) #남아있는 애들은 후보

---

3.

실버2

백준 15686 치킨 배달

15686번: 치킨 배달

from itertools import combinations 
from sys import stdin
# 도시크기/ 남길치킨집개수
N , M = map(int,stdin.readline().split())
townMap = [list(map(int,stdin.readline().split())) for _ in range(N)]

#치킨집 위치 / 집 위치 저장
chicken = []
house = []
for i in range(N):
    for j in range(N):
        if townMap[i][j] == 1:
            house.append([i,j])
        elif townMap[i][j] == 2:
            chicken.append([i,j])
        else:
            pass
# 치킨집 M개씩 묶은 리스트
chicklist = list(combinations([i for i in range(len(chicken))], M))

#치킨집묶음리스트를 하나씩 살펴보며 마을치킨거리 최소 갱신하기
result = (N-1)*2*N
for cha in chicklist:
    Nlist = []
    for j in range(M):
        Nlist.append(chicken[cha[j]])

    townresult = 0
    # 각 집에서의 치킨거리 최소 갱신해서 마을치킨거리 찾기
    for home in house: 
        homeresult = N*2
        for k in range(M):
            length = abs(Nlist[k][0]-home[0])+abs(Nlist[k][1]-home[1])
            homeresult = min(homeresult, length)
        townresult += homeresult
    result = min(townresult,result)

print(result)

Edoc에서 만든거