[Algorithm] 완전 탐색

1. 완전 탐색 알고리즘이란?

가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. Brute Force라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 값을 얻어낼 수 있는 확실하고, 기초적인 방법이다. 

 

완전 탐색을 이용할 때는 두가지를 고려해야한다.

1. 사용된 알고리즘이 적절한가? 

2. 효율적으로 동작하는가?

 

1번은 만족하나 2번의 경우 제한이 따르는 경우가 많으니, 완전 탐색을 이용할 경우에는 문제에 대한 파악이 중요하다.

2. 완전 탐색 기법의 활용

완전 탐색 기법을 이용하기 위해서는 여러 알고리즘 기법이 이용된다. (완전 탐색 자체를 알고리즘으로 볼 수는 없다.)

 

- 단순 Brute-Force

단순하게 for문과 if문 등으로 모든 case들을 만들어서 답을 구하는 방법이다. (코테에서 거의 사용하지 않는다..)

 

ex. 숫자 5개 [1,2,3,4,5] 중 세개의 원소를 택하는 경우는?

• [1, 2, 3]
• [1, 2, 4]
• [1, 2, 5]
• [1, 3, 4]
• [1, 3, 5]
• [1, 4, 5]
• [2, 3, 4]
• [2, 3, 5]
• [2, 4, 5]
• [3, 4, 5]

총 10가지이고 이를 반복문으로 구현할 수 있다.

 

n = 5

result = []
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            result.append((i, j, k))

 

그럼 만약 5개 중 4개를 고른다면? 혹은 m개를 고른다면? 이 경우에 반복문으로 구현할 수 있을까?
4개를 고를 경우 반복문이 4개나 필요하고, m개일 경우 구현할 수 없기 때문에 다른 완전 탐색 기법을 사용해야한다.

 

 

- 재귀 함수

재귀함수란 말 그대로 자기 자신을 호출한다는 뜻이다. 재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출한다.

이를 이용하여 N개의 수에서 M개를 선택하는 문제를 해결할 수 있다.

 

def choose(arr):
    n = len(arr)
    picked = []
    start = 0
    def recur(start, n):
        # basecase
        if len(picked) == n:
            print(picked)
            return

        # 1개선택
        for i in range(start, n):
            picked.append(i)
            # 재귀하면서 나머지 원소 선택
            start = picked[-1] + 1
            recur(start, n)
            picked.pop()

    recur(start, n)
    
choose([0,1,2,3,4])

 

다만, 재귀를 사용할 때에는 몇가지 고려해야할 점이 있다.

 

1. 탈출 조건이 필요하다.

만약 위 코드에서 탈출 조건이 없다면 무한 루프가 발생할 수 있다.

 

2. 현재 상태를 저장하는 파라미터가 필요하다. 

picked와 start 변수를 사용하여 어떤 숫자까지 선택했는지 등 현재 상태를 저장해야한다.

 

따라서 재귀 함수를 사용할 때는 위 두가지를 고려하자! 

 

 

- 순열

순열은 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법을 의미한다. 

ex. [1,2,3]과 [3,2,1]는 순서에 차이가 있을 경우에 사용 가능하다. N개에서 M개를 고르는 문제는 순서가 달라도 같은 경우이기 때문에 순열을 사용할 수 없다.

같은 데이터가 입력된 수열이지만, 그 순서에 따라 의미가 있고 이 순서를 통해 연결되는 이전 / 다음 수열을 찾아낼 수 있는 경우를 계산할 수 있다.  파이썬에서는 itertools를 이용하여 간단하게 구현할 수 있다.

 

from itertools import permutations

arr = [0, 1, 2, 3, 4, 5]

print(list(permutations(arr, 3)))

 

 

N개 중 M개를 고르는 문제처럼 순서가 의미가 없다면 조합을 이용하면 된다.

 

from itertools import combinations

arr = [0, 1, 2, 3, 4, 5]

print(list(combinations(arr, 3)))

 

 

- 비트 마스크

2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다.

(pass)

 

 

- BFS, DFS 사용하기 

BSF와 DFS는 그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.

BFS는 너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘이고, DFS는 깊이 우선 탐색으로 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 

 

3. 파이썬에서 그래프의 표현 

DFS와 DBS를 보기 전에 그래프에 대해서 알아보자.

그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고 말한다.

프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있는데 코딩 테스트에서는 이 두가지 방식 모두 필요하기 때문에 숙지하자.

 

 

 

ex. 

1) 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식

 

그래프가 위 그림과 같다면 인접 행렬은 2차원 배열에 각 노드가 연결된 형태를 기록한다. 

파이썬에서는 이차원 리스트로 구현할 수 있다. 연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다.

 

	0	1	2
0	0 (자기자신)	7	5
1	7	0 (자기자신)	무한
2	5	무한	0 (자기자신)

 

 

INF = 999999999

graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]

 

 

2) 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식 

 

인접 리스트에서는 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.

이는 연결 리스트라는 자료구조를 이용해 구현하는데, 파이썬에서는 기본 자료형인 리스트 자료형에서 append() 메소드를 제공하므로 리스트를 이용해서 구현할 수 있다.

 

0 -> (1 노드와 연결, 간선은 7) (2 노드와 연결, 간선은 5)

1 -> (0 노드와 연결, 간선은 7)

2 -> (0 노드와 연결, 간선은 5)

graph = [[] for _ in range(3)]

# 0 노드
graph[0].append((1,7))
graph[0].append((2,5))

# 1 노드
graph[1].append((0,7))

# 2 노드
graph[2].append((0,5))

print(graph)

#[[(1,7), (2,5)],[(0,7)],[(0,5)]]

 

-> 인접 행렬은 모든 관계를 저장하므로 메모리가 불필요하게 낭비되고, 인접 리스트는 인접 행렬 방식에 비해 메모리는 효율적이지만 두 노드가 연결되었는지에 대한 정보를 얻는데 속도가 느리다는 단점이 있다. 

 

4. DFS

DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 

DFS는 스택 자료구조 (혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다.

 

1) 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다.

2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3) 더 이상 2번의 과정을 수행할 수 없을 떄까지 반복한다.

 

(이해가 어렵다면 아래 링크에 28분 참고)

https://www.youtube.com/watch?v=7C9RgOcvkvo 

 

구현

 

def dfs(graph, v, visited):
	visited[v]=True
    print(v,end='')
    # 인접한 노드 중 방문하지 않은 것이 있다면 
    for i in graph[v]:
    	if not visited[i]:
        	# 그 i를 기준으로 다시 탐색 시작
        	dfs(graph, i, visitied)


#그래프 표현
graph=[
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]

# 방문된 정보 표현
visited = [False] * 9

# 처음 방문할 노드는 가장 작은수로 선택하는게 일반적
dfs(graph, 1, visited)

 

 

4. BFS

BFS는 너비 우선 탐색이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다.

BFS는 DFS와 다르게 선입 선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하게되면 자연스럽게 먼저 들어온 것이 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다.

구체적인 동작 과정은 다음과 같다.

 

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3) 2) 과정을 더이상 수행할 수 없을 때까지 반복한다.

 

(이해가 어렵다면 아래 링크에 36분 참고)

https://www.youtube.com/watch?v=7C9RgOcvkvo 

 

구현

 

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

graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]

visited = [False] * 9
bfs(graph,1,visited)

 

보통 DFS보다 BFS 구현이 좀 더 빠르다.

코딩 테스트 중 2차 배열에서의 탐색 문제를 만나면 위와 같이 그래프 형태로 바꿔 생각하면 풀이 방법을 조금 더 쉽게 떠올릴 수 있다. 

그러므로 코딩 테스트에서 탐색 문제를 보면 그래프 형태로 표현한 풀이법을 고민하도록 하자. 

 

 

참고) 이것이 코딩테스트다. 
https://hongjw1938.tistory.com/78