Algorithm_10

백트래킹

• 현재 상태에서 가능한 모든 경로를 따라 탐색

• 원하는 값과 불일치 하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아간다.

• 불필요한 탐색을 하지 않는다.

• 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기를 한다.

• 한정 조건을 잘 주어야 한다.

백트래킹 과 DFS의 차이점

• 백트래킹

  • 어떤 노드에서 출발하는 경로가 그 해결책으로 이어질 것 같지 않으면 더 이상 경로를 탐색하지 않음으로써 시도 횟수 감소

  • 불필요한 경로의 조기 차단

  • N! 가지의 경우의 수를 가진 문제에 대해 백트래킹에 가하면 일반적으로 경우의 수가 줄어들지만 최악의 경우는 처리 불가능

  • 모든 후보를 검사하지 않음

• DFS

  • 모든 경로를 추적

  • N! 가지의 경우의 수를 문제에 대해 깊이 우선탐색을 이용하면 처리 불가능

  • 모든 후보를 검사

Ex) 백준_1189

import sys
def input:
	return sys.stdin.readline

# r X c  맵
# 거리 k 인 가짓수 구하기
r,c,k = map(int, input().split())
graph = []
for _ in range(r):
    graph.append(list(input().rstrip()))

direction = [(1,0),(-1,0),(0,1),(0,-1)]

answer = 0
def DFS(x,y,distance):
    global answer
    # 목표 도착 지점 : (0,c-1)
    # 목표 거리 : k
    if distance == k and y == c-1 and x==0:
        answer += 1
    else:
        # True로 방문처리
        graph[x][y]=True
        for dir in direction:
            nx = x+dir[0]
            ny = y+dir[1]
            # 백트래킹 한정 조건 : graph[nx][ny] == '.'
            if(0 <= nx < r and 0 <= ny < c and graph[nx][ny] == '.'):
                graph[nx][ny]='T'
                dfs(nx,ny,distance+1)
                # 원래 상태로 돌려 놓아 다른 방향으로 다시 탐색하도록 한다.
                graph[nx][ny]='.'

# 초기 distance : 1
DFS(r-1,0,1)
# 정답
print(answer)

분할 정복 알고리즘

---

유래

• 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략
• 전력이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연한군을 둘로 나눔
• 둘로 나뉜 연합군을 한 부분씩 격파

설계전략

• 분할 : 해결한 문제를 여러 개의 작은 부분으로 나눈다
• 정복 : 나눈 작은 문제를 각각 해결
• 통합 : 해결된 해답을 모은다
• 소요시간 : O(log₂n)

def Power(Base, Exponent):
	if Exponent == 0 or Base == 0:
    	return 1
    if Exponent % 2 == 0
    	NewBase = Power(Base, Exponent/2)
        return NewBase * NewBase
     else:
     	NewBase = Power(Base, (Exponent-1)/2)
        return (NewBase * NewBase) * Base

퀵정렬

---

• 주어진 배열을 두 개로 분할하고, 각각 정렬한다.
• 합병정렬과 차이점
  • 합병정렬은 그냥 두 부분으로 나누는 반면에, 퀵정렬은 분할할 때, 기준 아이템 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다.
  • 각 부분 정렬이 끝난 후, 합병정렬은 "합병"이란 후처리 작업이 필요하나, 퀵정렬은 필요로 하지 않는다.
• 평균 시간 복잡도는 nlogn이다.
  

def quickSort(a, begin, end):
	if begin < end:
    	p = partition(a, begin, end)
        quickSort(a, begin, p-1)
        quickSort(a, p+1, end)
def partition(a, begin, end):
	pivot = (begin + end) // 2
    L = begin
    R = end
    while L < R:
    	while(L<R and a[L] < a[pivot]): L += 1
        while(L<R and a[R] >= a[pivot]): R -= 1
        if L < R:
        	if L == pivot : pivot = R
            a[L], a[R] = a[R], a[L]
    a[pivot], a[R] = a[R], a[pivot]
    return R