[문제 해결 알고리즘] 분할 정복 알고리즘 ②

1. 선택(Selection) 문제

 - n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제

 - 선택 문제 해결을 위한 간단한 방법

 - 최소 숫자를 k번 찾음

   단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거함

   최악의 경우 시간 복잡도 O(kn)

 - 숫자들을 정렬한 후 k번째 숫자를 찾음

   최악의 경우 시간 복잡도 O(nlogn)

 - 아이디어 : 입력이 정렬되어 있지 않으므로, 입력 숫자들 중에서 퀵정렬에서와 같이 피봇을 선택아혀 아래와 같이 분할 함

   s-group : 피봇보다 작은 숫자

   l-group : 피봇보다 큰 숫자

   > 분할 후 각 그룹의 크기를 알아야 k번째 작은 숫자가 어느 그룹에 들어있는지 알 수 있음

   > 그룹에서 몇 번째로 작은 숫자를 찾아야 하는지 알 수 있음

 - Selection(A,left,right)

  ⓐ 피봇을 A[left]~A[right]에서 랜덤하게 선택

    > 피봇과 A[left]와 자리를 바꾼다 > 피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자는 A[left]~A[p-1]로 옮김

    > 피봇보다 큰 숫자는 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓음

  ⓑ S = p-1 -left -1 // S = Small group의 크기

  ⓒ if(k<S)  Selection(A,left,p-1,k) //Small group에서 찾기

  ⓓ else if(k=S+1) return A[p]

  ⓔ else Selection(A,p+1,right,k-S-1) // large group에서 찾기

  - 나쁜 분할 : 분할된 두 그룹 중 하나의 크기가 입력 크기의 3/4와 같거나 그보다 크게 분할되는 경우 O(n)

  - 좋은 분할 : 나쁜 분할의 반대 = O(n)

2. 최근접 점의 쌍 찾기 문제 : 2차원 평면상의 n개의 점이 입력으로 주어질 때 거리가 가장 가까운 한 쌍의 점을 찾는 문제

 (1) 가장 간단한 방법 : 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾음 O(n(n+1)/2)=O(n^2)

 (2) 반반 방법

   - n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 찾음

   - 2개의 부분해를 취합할 때는 반드시 다음과 같은 겨우를 고려해야 함 

     왼쪽 부분의 최근접 쌍의 거리가 10이고 오른쪽 부분 문제의 최근접 쌍의 거리가 15임

     왼쪽 부분 문제의 가장 오른쪽 점과 오른쪽 부분 문제의 가장 왼쪽 점 사이의 거리가 7임

     따라서 2개의 부분 문제의 해를 취합할 때 단순히 10과 15 중에서 짧은 거리인 10을 해라고 할 수 없음

  +) 가장 짧은 거리인 10 이내의 중간 영역에 있는 점들 중에 최근접 점의 쌍이 있는지도 확인 필요

  - x 좌표로 자를 것으로 가정, x값을 기준으로 정렬 

  - x 좌표 left 값중 가장 큰값의 10이내의 점만 취합, right 값 중 가장 작은 값+10 이내의 점만 취합

  (3) 알고리즘 정리

   ⓐ if(i<=3) return (2, 3개의 점들 사이의 최근접 쌍)

   ⓑ 정렬된 S를 같은 크기의 SL과 SR로 분할 > S가 홀수면 |SL|=|SR|+1이 되도록 분할

   ⓒ CPL = Closestpair(SL)

   ⓓ CPR = Closestpart(SR)

   ⓔ d = min{dist(CPL), dist(CPR)} 일 때 중간 영역에 속하는 점들 중에서 최근접 쌍을 찾아서 이를 CPC라고 함

        * dist = 두점 사이의 거리

   ⓕ return min(CPL, CPR, CPC)

   > O(n(logn)^2))

3. 분할 정복을 적용하는데 있어서 주의할 점

 (1) 입력이 분할될 때마다 분할된 부분문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 매우 커지는 경우

    예) 피보나치 수 계산 알고리즘 (재귀 호출) > 저장한 후에 사용하는 방법이 더 적합함

4. 과제 : 분할 정복 알고리즘 사용 백준 온라인 문제 풀이 제출

색종이 만들기 2630 1. 색종이의 칸의 값을 모두 더한다. 2. 결과가 N*N(한변의 길이)인 경우에는 b값에 +1, 더한 모든 값이 0인 경우에는 w값에 +1한다.    두 가지 케이스에 해당하지 않을 경우 3번으로 간다. 3. 색종이를 4장으로 나눈다. 4. 4장의 색종이를 다시 1~3번의 과정을 반복한다. 5. 모든 재귀함수가 완료됐을 시 w, b값을 각각 출력한다. def check_all(A):     global w, b     total = sum(sum(row) for row in A)     if total == 0:         w += 1         return     elif total == len(A) * len(A):         b += 1         return     mid = len(A) // 2     A1 = [row[:mid] for row in A[:mid]]     A2 = [row[mid:] for row in A[:mid]]     A3 = [row[:mid] for row in A[mid:]]     A4 = [row[mid:] for row in A[mid:]]     check_all(A1)     check_all(A2)     check_all(A3)     check_all(A4) w, b = 0, 0 n = int(input()) matrix = [list(map(int, input().split())) for _ in range(n)] check_all(matrix) print(w) print(b)