Python 자료구조&알고리즘 - 분할 정복

 

1. 분할 정복(Division Conquer)

• 문제를 나눌 수 없을 떄까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘
• 하향식 접근방법으로 상위의 해당을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식(재귀함구로 구현)
• 문제를 잘게 쪼갤때 부분 문제는 서로 중복되지 않음
• Memorization 기법을 사용하지 않음

---

2. 대표적인 분할 정복 알고리즘 : 퀵 정렬(quick sort

• 정렬 알고리즘의 꽃(고급 알고리즘)
• 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성
• 각 왼쪽, 오른쪽은 재귀용법으로 사용해 다시 동일 함수로 호출하여 위 작업을 반복함

 

---

2-1. 퀵 정렬 알고리즘 구현

• 리스트 개수가 1개면 해당 리스트를 리턴
• 리스트 맨 앞의 데이터를 기준점으로 정함
• left,right 리스트 변수를 생성
• 맨 앞에 데이터를 뺀 나머지 데이터를 기준점과 비교
  • 기준점보다 작으면 left에 저장
  • 기준점보다 크면 right에 저장
• return quicksort(left) + pivot + quicksort(right)로 호