Brute Force[완전탐색]

📗 Brute Force

• 가능한 모든 경우를 탐색하는 방법
• 정확성은 100% 보장되지만 효율성은 최악임. 따라서 주어진 데이터가 매우 적을 때 사용하는 것이 좋음
• 일반적으로 for & if 문을 활용하거나, BFS/DFS를 활용하는 경우가 대부분임
• 다음의 사항을 고려해보고 수행함
  1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
  2. 가능한 모든 방법 고려
  3. 실제 답을 구할 수 있는지 적용

완전탐색의 5가지 방법

1. 단순 Brute Force
2. 순열, 조합
3. 재귀 함수
4. 비트마스크
5. BFS, DFS

🔔 python에서의 완전탐색

import itertools

# product : 곱집합
itertools.product(list1, list2, _ [repeat=1]

# permutations : 순열
# 가능한 모든 순서를 반환, 반복되는 요소 없음
# r 값에 따라 조합 수가 정해짐
itertools.permutations(list, r) 

# combinations : 조합
# 반복되는 요소가 없는 정렬된 순서
itertools.combinations(list, r)

# combinations_with_replacement : 중복이 가능한 조합
# 조합에서 개별 요소마다 두 번 이상 반복 가능
itertools.combinations_with_replacement(list, r)

🔔 재귀함수를 이용한 순열 구현

def permutations(arr, r):
	result = []
    
    def permute(p, index):
    	if len(p) == r:
        	result.append(p)
            return
        for idx, data in enumerate(arr):
        	if idx not in index:
            	permute(p + [data], index + [idx])
   permute([], [])
   return result

for r in permutations(['A', 'B', 'C', 'D'], 2):
	print(r)

🔔 재귀함수를 이용한 조합 구현

def combinations(arr, r):
	result = []
    
    def combinate(c, index):
    	if len(c) == r:
        	result.append(c)
            return
        for idx, data in enumerate(arr):
        	if idx > index:
            	combinate(c + [data], idx)
   combinate([], -1)
   return result

for r in combinations(['A', 'B', 'C', 'D'], 2):
	print(r)

🔔 DFS(깊이 우선 탐색)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• Stack 자료구조에 기초(선입후출), 따라서 재귀함수를 이용할 때 간결하게 구현 가능
• 시간복잡도 : O(N)
• 동작 과정
  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
  2. 스택 최상단 노드에 방문하지 않은 인접 노드가 있으면 해당 노드를 스택에 넣고 방문 처리
     • 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄
  3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

def dfs(graph, v, visited):
	visited[v] = True
    # print(v, end='')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)
            
visited = [False] * 9 # 방문 정보를 리스트로 표현
# 각 노드가 연결된 정보를 리스트로 표현
graph =[
	[], 		# 0번 노드와 연결된 노드 정보
    [2, 3, 8],	# 1번 노드와 연결된 노드 정보
    [1, 7],		# 2번 노드와 연결된 노드 정보
    [1, 4, 5],	# 3번 노드와 연결된 노드 정보
    [3, 5],		# 4번 노드와 연결된 노드 정보
    [3, 4],		# 5번 노드와 연결된 노드 정보
    [7],		# 6번 노드와 연결된 노드 정보
    [2, 6, 8],	# 7번 노드와 연결된 노드 정보
    [1, 7]		# 8번 노드와 연결된 노드 정보
]

dfs(graph, 1, visited)

🔔 BFS(너비 우선 탐색)

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
• Queue 자료구조에 기초(선입선출)
• 시간복잡도 : O(N) - 일반적으로 DFS보다 수행 시간이 좋음
• 동작 과정
  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
  2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
  3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복

from collections import deque
def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
        # print(v, end='')
    	for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
        
visited = [False] * 9 # 방문 정보를 리스트로 표현
# 각 노드가 연결된 정보를 리스트로 표현
graph =[
	[], 		# 0번 노드와 연결된 노드 정보
    [2, 3, 8],	# 1번 노드와 연결된 노드 정보
    [1, 7],		# 2번 노드와 연결된 노드 정보
    [1, 4, 5],	# 3번 노드와 연결된 노드 정보
    [3, 5],		# 4번 노드와 연결된 노드 정보
    [3, 4],		# 5번 노드와 연결된 노드 정보
    [7],		# 6번 노드와 연결된 노드 정보
    [2, 6, 8],	# 7번 노드와 연결된 노드 정보
    [1, 7]		# 8번 노드와 연결된 노드 정보
]

bfs(graph, 1, visited)

📘 관련 문제

⭐ 최소직사각형
⭐ 모의고사
⭐ 소수찾기
⭐ 카펫
⭐ 피로도
⭐ 전력망을 둘로 나누기
⭐ 모음사전