브루트포스(Brute Force)

브루트포스란 나올 수 있는 모든 경우의 수를 계산하여 조건에 맞는 값을 가져와 알고리즘을 푸는 방식이다. 다른 말로 완전탐색이라고 한다.

브루트포스 알고리즘의 장점은 무조건 결과를 찾을 수 있다는 점이나, 모든 경우의 수를 계산하기에 딱히 알고리즘이라 볼 수 없을 뿐더러 효율성이 매우 떨어진다.

즉, 코딩테스트시 브루트포스 알고리즘을 쓰는 경우는 높은 확률로 더 좋은 알고리즘이 존재할 것이며 대부분의 사람들이 구현만 할 수 있으며 짤 수 있으므로 잘 안 나온다고 볼 수 있다.

그리고 브루트포스 보다는 수학적 알고리즘을 섞어서 내는 경우가 많으므로 딱히 이 부분을 준비한다기보다 최후의 보루로 남겨두는 편이 안전할 것이다.

DFS와 BFS

이들은 그래프 순회의 방식들로 일반적으로 BFS에 비해 DFS가 널리 쓰인다고 한다.
DFS는 스택이나 재귀로 구현하며,
BFS는 큐로 구현한다. 또한 BFS는 최단경로를 찾는 다익스트라 알고리즘에서도 응용되니 잘 알아두면 좋다.

BFS

너비 우선 탐색으로 주로 큐로 구현한다. 큰 틀은 다음과 같다

def BFS(start):
	dicovered = [start]
    Q = [start]
    while Q:
    	v = Q.pop(0)
        for w in graph[v]:
        	if w not in discovered:
            	discovered.append(w)
                Q.append(w)
    return discovered

• pop(0)는 성능이 떨어지기 때문에 deque()로 선언 후 popleft를 쓰는 게 좋다.

DFS

깊이 우선 탐색으로 주로 스택이나 재귀로 구현한다. 큰 틀은 다음과 같다.

<재귀>
def DFS(v,dicovered=[]):
	dicovered.append(v)
    for w in graph[v]:
    	if not w in dicovered:
        	dicovered = DFS(w,dicovered)
    return dicovered
    

<스택>
def DFS(start):
	dicovered = [start]
    stack = [start]
    while stack:
    	v = stack.pop()
        for w in graph[v]:
        	if w not in discovered:
            	discovered.append(w)
                stack.append(w)
    return discovered

• 보다시피 스택으로 구현하는 구조는 BFS와 유사하다. 따라서 필자는 스택으로 구현하는 것을 선호하는 편이다. 개념을 이해한다면 스택으로 구현하는 것이 성능도 좋다.

백트래킹

DFS를 이야기하다 보면 백트래킹이라는 단어가 함께 나온다. DFS보다 좀 더 광의의 의미를 가지며 탐색을 하다가 더 갈 수 없는 경우 되돌아가 다른 길을 찾는데서 유래했다. 백트래킹은 주로 재귀로 구현하며 알고리즘마다 조금씩 변형된다. 이는 브루트포스와 유사하나 가능성 없는 경우 즉시 후보를 포기한다는 점에서 브루트포스보다는 더 우아한 방식이라 볼 수 있다.

프로그래머스 문제

• 브루트포스
• DFS&BFS