Programming Language Training/Algorithm

브루트포스 알고리즘(Backtracking, DFS, BFS)

생각하는 이상훈 2023. 2. 12. 19:46
728x90

Brute Force Algorithm

브루트 포스 알고리즘(Brute Force Algorithm)은 컴퓨터 과학에서 올바른 해결책이 발견될 때까지 가능한 모든 해결책을 시도하여 복잡한 문제를 해결하는 데 사용되는 기술이다. 브루트 포스 알고리즘은 암호학, 비밀번호 크래킹, 최적화 문제 등 다양한 분야에서 사용될 수 있다. 그러나 브루트 포스 알고리즘에서 사용되는 세 가지 일반적인 테크닉인 백트래킹, 깊이 우선 검색(DFS) 및 폭 우선 검색(BFS)을 중심으로 코딩에서 브루트 포스 알고리즘이 어떤식으로 이용되는지 간단한 파이썬 코드 예제를 이용하여 보고자 한다.

Backtracking Algorithm

백트래킹 알고리즘은 브루트 포스 알고리즘에 포함된다고 할 수도 있지만 어떻게 보면 거의 같다고 할 수도 있는 것 같다.

백트래킹 알고리즘은 트리와 같은 구조의 데이터들을 전수조사하면서 원하는 정답이 아닌 경우 되돌아가서 다시 조사를 한다고 해서 "Back"tracking 알고리즘이다.

따라서 DFS, BFS와 같은 방법론은 Brute Force Algorithm과 Backtracking Algorithm에 포함된다고 볼 수 있다.

백트래킹 알고리즘의 특징이 잘보이는 코드를 보고 넘어가도록 한다.

def permutations(data, i, length):
    if i == length:
        print(data)
    else:
        for j in range(i, length):
            # i번째 데이터와 j번째 데이터를 swap
            data[i], data[j] = data[j], data[i]
            
            # 변화가 생긴 data에서 permutation을 재귀
            permutations(data, i+1, length)
            
            # i, j번째 데이터를 다시 swap
            data[i], data[j] = data[j], data[i]
 
permutations([1, 2, 3], 0, 3)

DFS & BFS

DFS란 정의와 같이 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 즉, 그래프를 탐색 할때 특정한 경로로 쭉 타고 밑바닥까지 내려간 후 막다른 길에 도착하면 다시 돌아와 다른 경로로 탐색하는 것이다.

DFS의 작동 과정이다.

  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)
            
# 각 노드(index)가 연결된 다른 노드 정보를 리스트로 표현
graph = [
         [],
         [2,4,6], # 1번 노드는 2,4,6에 연결되어 있음
         [1,3],
         [2],
         [1,5],
         [4],
         [1],
         ]
visited = [False]*7
dfs(graph, 1, visited)

BFS란 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. 즉, 그래프를 탐색 할때 가까운 노드들을 우선적으로 방문하고 멀리있는 노드를 나중에 방문한다.

BFS의 작동 과정이다.

  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
            
# 각 노드(index)가 연결된 다른 노드 정보를 리스트로 표현
graph = [
         [],
         [2,4,6], # 1번 노드는 2,4,6에 연결되어 있음
         [1,3],
         [2],
         [1,5],
         [4],
         [1],
         ]
visited = [False]*7
bfs(graph, 1, visited)

 

728x90