1. 분할정복

  • 분할 : 해결할 문제르를 여러 개의 작은 부분으로 나눈다.
  • 정복 : 나눈 작은 문제를 각각 해결한다.
  • 결합 : 해결된 해답을 모은다.

[예] 거듭제곱의 경우, 반복하면 시간복잡도가 O(n)이지만, 반씩 나눠서 분할 정복하면 O(logn)의 시간복잡도를 가진다.

2. 병합정렬

  • 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합을 만드는 방식
  • 자료를 최소 단위까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄
  • 시간복잡도 : O(nlogn)

병합정렬은 링크드 리스트로 구현했을 때 가장 빠르다.

3. 퀵정렬

  • 주어진 배열을 두 개로 분할하고, 각각을 정렬한다.

병합정렬과 퀵정렬의 차이점

  • 병합정렬은 그냥 두 부분으로 나눠서 진행되는 반면, 퀵 정렬은 분할의 기준인 pivot을 중심으로, 작은 것은 왼편, 큰 것은 오른편에 위치된다.
  • 병합정렬은 정렬이 끝난 후, 병합의 과정이 필요하지만, 퀵정렬은 필요로 하지 않다.

4. 이진검색

  • 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
  • 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

[예] 병뚜껑의 숫자 맞추기 게임

5. 백트래킹

  • 여러 가지 선택지들이 존재하는 상황에서 한가지를 선택한다.
  • 선택이 이뤄지면 새로운 선택지들의 집합이 생성된다.

백트래킹 VS DFS

  • 깊이우선탐색은 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단
  • 백트래킹은 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써 시도의 횟수를 줄인다.(가지치기)