↪️ 백트래킹(Backtracking)

해를 찾는 도중에 막히면 되돌아가서 다시 해를 찾아가는 기법.

• 최적화(옵티미제이션)
• 결정(디시젼)
  ex) 미로찾기, n-queen, Map Coloring, 부분 집합의 합

그렇다면 미로찾기 문제는 깊이 우선탐색(DFS)로도 가능한데 둘의 차이는?

• 백트래킹 : 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로 횟수를 줄임.
  가지치기(플루닝) : 불필요한 경로의 조기차단, 모든 후보검사 X
• 깊이 우선탐색 : 모든 경로를 추적, 모든 후보검사

---

✂️ 분할 정복 알고리즘

합병 정렬: 각 부분 정렬이 끝난후 후처리 필요
퀵 정렬 : 피벗을 중심으로 왼쪽은 작은 것 오른쪽은 큰것으로, 후 처리 필요
평균 복잡도 : O(nlogn), 최악의 시간복잡도 :O(n2)