[알고리즘] Divide and Conquer

👀 알고리즘 설계 기법의 종류

1. 완전 탐색 (Brute Force)

- 배열 : 반복문으로 전체 순회
- 그래프 : DFS, BFS

2. 탐욕 (Greedy)

- 규칙 찾기
- 항상 최적해가 보장되지 않음을 주의

3. 동적 계획법 (DP)

- 하나의 큰 문제를 작은 문제로 나누어 부분적으로 해결 
- Memoization 활용
- 점화식(bottom-up), 재귀(top-down)

4. 분할 정복 (Divide and Conquer)

- 큰 문제를 작은 문제로 쪼개서 해결

5. 백트래킹 (Backtracking)

- 전체 중, 가능성 없는 것을 제외하고 보기 
- 가지치기 

---

🚩 분할정복

- 분할 : 문제를 쉽게 해결할 수 있을 때까지 나누기
- 정복 : 나눈 문제를 각각 해결하기 
- 통합 : (필요 시) 해결된 해답 모으기

분할 정복 알고리즘 : 거듭제곱 구하기

Recursive_Power(x, n)
	IF n == 1 : RETRUN x
   IF n is even
   	y <- Recursive(x, n/2)
       RETURN y * y
   ELSE
   	y <- Recursive(x, (n-1)/2)
      	RETURN y * y * x

- 병합 정렬

여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식

- 분할 : 전체 자료 집합에 대하여 최소 크기의 부분집합이 될 때까지 분할을 계속 한다
- 정복 : 나눠놓은 부분 집합을 정렬하고 병합한다
- 시간 복잡도 : O(N logN)

분할

merge_sort(LIST m)
	IF length(m) == 1 : RETURN m
    
    LIST left, right
    middle <- length(m) / 2  # 가운데
    FOR x in m before middle # 왼쪽 
    	add x to left
    FOR x in m after or equal middle # 오른쪽
    	add x to right
    
    # 재귀 호출
    left <- merge_sort(left)
    right <- merge_sort(right)
    
    RETURN merge(left, right)

정복(병합)

merge(LIST left, LIST right)
	LIST result
    
    WHILE length(left) > 0 OR length(right) > 0
    	IF length(left) > 0 AND length(right) > 0 
        	# 더 작은 것을 result 에 넣기
        	IF first(left) <= first(right) 
            	append popfirst(left) to result
            ELSE 
            	append popfirst(right) to result
        # 남은 데이터 모두 넣기
        ELIF length(left) > 0
        	append popfirst(left) to result
        ELIF length(right) > 0
        	append popfirst(right) to result
   	RETURN result 

- 퀵 정렬

병합 정렬과 같이 분할 정복을 이용하나 ...

- 차이점 1 : 기준 아이템(pivot item)을 중심으로 작은 것은 왼편, 큰 것은 오른편에 위치시킨다
- 차이점 2 : 퀵 정렬은 병합 작업이 필요하지 않다  

• 기준 값보다 큰 값은(i) 오른쪽, 작은 값(j)은 왼쪽 집합에 위치시킨다
  - i, j 찾는 알고리즘
  1. Hoare partition
  2. Lomuto partition
• 기준(피봇)을 두 집합의 가운데에 위치시킨다
  - 피봇 선택 : 왼쪽 끝, 오른쪽 끝, 임의의 세개 값 중 중간 값(값이 중간)

Lomuto partition 알고리즘

partition(A[], p, r)
	x <- A[r]
    i <- p - 1
    
    FOR j in p -> r - 1
    	IF A[j] <= x
        	i++, swap(A[i], A[j])
        
    swap(A[i+1], A[r]
    RETURN i + 1

---

❓ 왜 배우는 걸까?

• 파이썬 내장 라이브러리 sort(), sorted() 효율이 더 좋다
• 병합 정렬과 퀵 정렬 모두 직접 구현할 일이 적다
• 하지만 과거 면접 단골 질문 + 분할 정복 학습에 좋다

코드를 보기 전에 반드시 손으로 직접 적어보기

병합정렬

• 멀티 쓰레드 : 나누어서 동시에 처리하고 나중에 합친다

퀵 정렬

• 평균적으로 굉장히 좋음 (NlogN)
• 큰 데이터를 다룰 때 좋음
• 단점 : 역순 정렬 등 최악의 경우 O(N^2)

(+) 추후, 슈도코드 파이썬 코드로 구현해보기