[Algorithm03] 완전 탐색
우리는 전 시간에 순열과 조합을 dfs(재귀적 접근)를 이용해서 공부했다.
계속 순열과 조합의 기본을 강조하는 이유가 어떤 문제든 탐색을 진행할 집합이 그래프화(배열이나 리스트 등)할 수 있다면 순열과 조합의 기본을 이용하여 모두 풀 수 있기 때문이다.
다만 못 푸는 경우도 존재하는데 이것은 정답을 찾을 수 없다가 아니라 문제를 풀 때 제한조건을 만족하지 못해서이다.
즉, 시간복잡도나 공간복잡도를 줄여야 하는 문제이기 때문이다.
이러한 시간복잡도와 공간복잡도를 줄이기 위해서 다양한 알고리즘들이 존재한다. 하지만 기본적인 완전탐색을 하지 못하는데 시간복잡도와 공간복잡도를 줄이기 위한 다른 알고리즘을 먼저 공부하는 것은 아니라고 생각한다. 본인만의 문제 접근법 풀이법이 정립이 되지 않았는데, 이 문제는 이 알고리즘으로만 풀고 이문제는 이 알고리즘으로만 풀어야지 하면 실제 새로운 문제를 볼 때 접근조차 어려울 수 있다. 우리는 먼저 해야 할 일이 문제에 대한 해석과 문제 해결에 대한 접근방법을 체득하는 것이다. 그렇기 때문에 먼저 문제를 '풀줄 알아야 한다.' 즉, 일단 정답을 도출해낼 줄 알아야 그다음에 시간 복잡도, 공간 복잡도, 코드의 간결화 등을 생각해서 다른 알고리즘을 공부하고 적용시켜 문제를 풀어낼 수 있다.
그럼 기본적으로 완전 탐색이 무엇인지 알아보자
완전 탐색
말 그대로 문제에서 주어진 조건에 부합한 가능한 모든 경우의 수 를 탐색하는 것이다.
완전 탐색의 방법들에는 단순 brute-force, 비트 마스크, 재귀함수, 순열, BFS, DFS 등이 있다.
결이 다른(shift연산자 이용) 비트 마스크를 제외하고 모두 공통점이 있다. 바로 반복문을 사용하여 조건에 부합하는 가능한 모든 경우의 수를 탐색한다라는 것이다.
brute-force: 단순 반복문과 조건문으로 모든 경우 탐색
Bitmask: 문제를 0과 1 두 가지로만 해석 가능한 경우에 한하여 shift연산을 이용해 조건에 부합하는 경우 탐색
재귀함수: 재귀적 호출을 이용하여 조건에 부합하는 부분만 파라미터에 담아 반복하여 탐색
순열: 사실 순열을 우리는 재귀함수로 표현할 줄 안다. 서로 다른 n개를 일렬로 나열하는 말이다.
DFS/BFS : 깊이 우선 탐색, 너비 우선 탐색 이 부분은 다음 시간에 깊게 다루겠다. DFS는 스택을 이용하여 BFS는 큐를 이용하여 구현하는데 스택은 재귀로 표현할 수 있다고 하지 않았는가! dfs 또한 재귀함수로 구현이 가능하다. 두 가지의 탐색기법을 통하여 조건에 부합하는 모든 경우의 수를 탐색한다.
반복문을 사용하여 조건에 부합하는 모든 경우의 수를 탐색 이 말이 얼마나 단순한가 우리는 이러한 큰 카테고리 안에서 우리만의 접근 방법을 만들어 가야 한다. 그래서 앞서 재귀함수를 공부하고 재귀함수를 통한 순열과 조합 구현을 공부하였다.
이번엔 완전탐색을 재귀함수 즉 dfs의 기본을 이용하여 푸는 방법을 배워보겠다.( 엄밀이 말하면 dfs는 그래프가 주어지고 그래프의 자식노드를 타고 가며 깊이를 우선으로 그래프의 끝까지 탐색하는 방법인데 재귀적 접근이라는 측면에서 편하게 dfs 기본이라고 하겠다. )
그렇다면 재귀를 이용한 완전 탐색 방법은 어떻게 하는 것일까? 이미 우리는 할 줄 안다. 순열과 조합에서 모든 것을 다한 것이다! 하지만 문제를 보고 어떻게 순열과 조합으로 풀어낼까 즉, 어떻게 반복문을 이용하여 조건에 부합하는 모든 경우의 수를 도출할 수 있을까라는 고민을 해봐야 한다. 아래의 예시들에서 문제만 보고 무엇을 정답으로 도출해 내야 하는지 생각해 보자. (아, 물론 이러한 재귀적 접근법 말고 단순 조건문과 1,2번 만의 중첩반복문 혹은 문자열처리로만 풀리는 문제도 있지만 지금 얘기하고 싶은 부분은 어떤 문제를 접근할 때 나만의 접근방법으로 일관되게 접근할 수 있는가를 먼저 할 것이다.)
다음부터 보는 예제들의 문제만 보고 추가적인 조건은 생각하지 말고 단순하게 문제에서 뭘 물어보는가만 뽑아보자
<아홉 난쟁이의 키가 주어지고 그중에서 일곱 난쟁이를 뽑아라> 어디서 많이 보지 않았는가 전 시간에 했던 N개에서 K개를 뽑아라이다.
그럼 생각을 해보자 N개는 아홉 난쟁이의 키 즉, n=9이고 K는 일곱 난쟁이 k=7 조건은 n개중에서 k개를 뽑았는데 k개의 합이 100이 되는 조합만 뽑으면 된다. 단순 반복문으로 합이 100이 되는 조건을 부합하도록 완전탐색을 할 수 있다. 하지만 우리는 전 시간에 순열과 조합을 재귀적 접근으로 공부했다. 전 시간에 한 것을 적용해 보자
n=9 k=7이고, 중복 X 순서 X 끝이다. 여기에서 추가적으로 조합 후에 (종료조건 시 < if depth==7: >) 총합이 100이 되면 정답 변수에 추가만 해주면 된다. 바로 코드로 보자.
혹시 순열과 조합이 지금 완벽히 안되어 있으면 옆에 동시에 켜두면서 코드를 비교해 보면 딱 종료조건에만 추가가 된 것을 알 수 있다.
arr = []
for i in range(9):
arr.append(int(input()))
path = [0] * 7
def dfs(depth, start):
# 7장 모두 뽑았으면 출력하고 리턴
if depth == 7:
if sum(path) == 100:
for i in sorted(path):
print(i)
exit()
else:
return
for i in range(start, 9):
path[depth] = arr[i]
dfs(depth + 1, i + 1)
path[depth] = 0
dfs(0, 0)
우리는 앞으로 순열과 조합으로 풀 수 있는 문제는 이러한 기본 틀을 잡고 문제에 접근하도록 하겠다. (추 후 이러한 기본틀이 백트래킹, dfs로 이어진다.)
한 문제만 더 보자
추가적인 조건 다 생각하지 않고, 문제가 뭘 물어보는가를 확인해 보자
<카드 N개 중에서 3장을 뽑아라> 끝이다. 이제 추가적인 조건을 보자 3장의 합이 M이 넘지 않으면서 최대한 가까워야 한다. 전형적인 우리가 공부한 N개에서 K개를 뽑는 순열조합 문제이다.
n=N k=3 중복 X 순서 X 끝이다. 그리고 추가적으로 재귀종료 조건에 뽑은 3장의 카드가 M이 넘지 않으면서 최대인 것을 누적시키면 된다. 바로 코드로 보자
n, m = map(int, input().split())
arr = list(map(int, input().split()))
path = [0] * n
all_case = []
def dfs(depth, start):
if depth == 3:
if m >= sum(path):
all_case.append(sum(path))
return
else:
for i in range(start, n):
path[depth] = arr[i]
dfs(depth + 1, i + 1)
path[depth] = 0
dfs(0, 0)
max = 0
for i in all_case:
if abs(m - max) >= abs(m - i):
max = i
print(max)if depth==3: 즉 기저조건에서 문제에서 요구하는 조건을 해결하였다. 나머지는 우리가 공부했던 기본적인 순열과 조합 틀이다.
단순한 조건을 구현하는 구현실력은 문제를 여러 번 풀어보고 해당언어의 라이브러리 활용이나 자료구조에 대한 이해가 우선이다. 문제를 풀 때에는 이렇게 접근 방법에 대해 고찰해 보고 자신만의 풀이법을 만들어가자.
연습을 위해 위의 두 개 문제를 빼고 추가적으로 같은 방법으로 꼭 풀어보길 바란다.
다음시간에는 이러한 완전탐새의 시간복잡도를 줄이는 백트래킹에 대해 알아보겠다. 미리 스포 하자면 완전탐색은 조건에 부합하는 모든 경우의 수를 뽑아내는 것인데 경우의 수 즉 하나의 조합에 대해 끝까지 탐색해서 뽑아내기 전에 끝까지 탐색할 필요가 없으면 탐색하지 않는 기법이다. 다음시간에 보자~