알고리즘 탐색알고리즘 감잡기

탐색문제를 풀면서 생각나는 부분들 계속해서 적을 예정

 

탐색알고리즘의 근본

일단 대표적으로 브루트포스 , 백트래킹, bfs, dfs 가 있다.

 

탐색하는 경우의 수를 머리에 그리면서 단순화 시킬 필요가있다.

1차원 배열로 결과들을 기록해나갈수있고(nQ, 배낭문제), 각 단계가 2차원 배열일수도 있다(2048, 구슬 탈출2).

이중 구슬 탈출2의 경우는 각 단계가 2차원 배열로 그려지지만 실제로 중요한것은 공의 위치이므로 공의 위치만을 저장하여 풀수도있다.

 

bfs는 최단경로, 최소 횟수에 유용하고

백트래킹은 특정 조합을 찾는 경우, 특정 조합의 개수를 찾는경우에 유용하다.

dfs는 거의 쓸일이 없고 있어도 bfs로 풀수있다.

 

 

백트래킹

[Python] 백트래킹 (+ DFS와 차이)

 

내가 기억하는 백트래킹 문제를 생각해보면 외판원 순회, N-queens, 배당문제, 순열 문제등이 있다.

어떠한 조합을 찾을때 pruning을 하면서 특정 경우를 찾는다.

최단경우에는 어울리지 않는게 깊이 우선으로 탐색하다보니 최저성능이 보장되지 않는다. (이상한 경로에 빠지면 큰일)

 

구현 아이디어

리스트에 값을 넣고 재귀를 돌린다.
가지치는 과정이 있고 데이터를 넣었으면 되돌리는 과정이 있거나 아니면 덮어씌우거나 무시할 수 있어야한다.

ans = []

def back(n):
    if n == 3: # 최대 깊이
        print(" ".join(map(str, ans))) # 1 2 3 이런 상태로 출력하기 위해
        return 
    for i in range(1, N+1):
        if i not in ans: # 가지치기
            ans.append(i) # 데이터를 넣었다면
            back(n+1) # 재귀 후
            ans.pop() # 데이터를 빼야함
                        
back(0)


ans = [0,0,0]

def pruning(n,x):
	for i in range(n):
    	if x in ans[i]:
        	return false
    return true
	
def back(n):
    if n == 3: # 최대 깊이
        print(" ".join(map(str, ans))) # 1 2 3 이런 상태로 출력하기 위해
        return 
    for i in range(1, N+1):
        if pruning(n,i): # 가지치기
            ans[n] = i # 가지치기를 n 이전 인덱스만 영향받게 만들고 덮어씌우기
            back(n+1) # 재귀
 
                        
back(0)