[ 알고리즘 ] 완전 탐색 (브루트 포스)

1. 개념

말 그대로 '완전 탐색'. 모든 경우의 수를 탐색한다.

장점 - 쉽고, 빠르게 구현할 수 있다.

단점 - 시간과 공간(메모리)적으로 매우 불리하다.

--> 따라서 모든 경우의 수를 탐색하되, 각 경우에서 쓸데없는 연산을 하지 않는 것이 중요하다. break 잘 때려주기!

 

2. 분류

1) 선형구조

- 배열(선형 리스트), 연결리스트(Linked List), 스택, 큐, 데크

- 데이터가 연속적으로 연결되어 있는 모양의 구조

- 포인터 등을 사용해서 자료를 연결하면, 자료가 일직선상에 표시되거나 하나의 원 상에 표시되는 구조

--> 순차탐색

 

2) 비선형구조

- 트리, 그래프

--> 백트래킹, DFS, BFS

 

 

 

3. 예제 - 백준 2798 블랙잭

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

1) 문제 설명

N개의 카드와 목표 숫자 M가 주어진다.

M에 최대한 가까운 카드 3장의 합을 출력하는 문제.

 

2) 코드

n, m = map(int, input().split())
l = []

l = list((map(int, input().split())))
max_num = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            temp = l[i] + l[j] + l[k]
            if m >= temp and m-temp < m-max_num:
                max_num = temp
            if max_num == m:
                break
        if max_num == m:
            break     
    if max_num == m:
        break
print(max_num)

 

3) 풀이

3중 for문을 적절히 사용하면 된다.

 

 

4. 참고자료

- 선형, 비선형 : https://server-engineer.tistory.com/130 

-