알고리즘 Part 3

분할정복 (Divide & Conquer)

주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘이다.

분할된 입력에 대한 문제를 부분문제(Subproblem)이라 하고, 부분문제의 해를 부분해라고 한다.
더 이상 분할할 수 없을 때까지 계속 분할한다.
큰 문제 -> 작은문제

분할 정복 알고리즘의 분류

1. 문제가 a개로 분할되고, 부분문제의 크기가 1 / b로 감소하는 알고리즘
   -> a=b=2 합병정렬, 최근접 점의 쌍 찾기 등
2. 문제가 2개로 분할, 부분문제의 크기 일정하지 않은 알고리즘
   -> 퀵 정렬
3. 문제가 2개로 분할, 그 중 1개의 부분문제는 고려할필요가 없으며, 부분문제의 크기가 1/2로 감소하는 알고리즘
   -> 이진 탐색
4. (2) + (3)
   -> 선택 문제 알고리즘
5. 부분문제의 크기가 1, 2개씩 감소하는 알고리즘
   -> 삽입 정렬, 피보나치 수

3.1 합병 정렬

n개의 숫자들을 n / 2개의 부분문제로 분할, 각 부분문제를 재귀적으로 합병 후 정렬한다.
합병 과정에서는 정렬하며 합병한다.

Line 1에서 p = q, 즉 원소의 수가 1이면 , 그 자체로 정렬된 것이므로 호출했던 곳으로 리턴한다는 점을 유의하자!

입력의 크기가 n 일 때, 시간복잡도는?
n을 나눌 수 없는 크기인 1까지 분할을 하면 log n 임이 층 수 임을 알 수 있고, 입력 크기인 n을 곱한다.
-> (층수) O(n) = log n O(n) = O (n log n)

합병 정렬의 단점

공간 복잡도는 O(n)이다.
입력을 위한 공간외에 추가의 공간이 별도로 필요하다.
2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문이다.

응용

합병 정렬은 외부정렬의 기본이 되는 정렬 알고리즘이다.
연결 리스트에 있는 데이터를 정렬할 때에도 타 정렬보다 효율적이다

 ---
 

3.2 퀵 정렬

퀵 정렬(Quick Sort)는 분할 정복 알고리즘으로 분류되나, 사실 정복 후 분할하는 알고리즘으로 볼 수 있다.
2개의 부분문제로 분할하는데, 두 부분문제의 크기가 일정하지 않다.

피벗을 맨 왼쪽 값과 Swap해주고 시작한다.
피벗을 기준으로 작은 값과 큰 값을 비교 및 교환하며 분할정복한다.

최악의 경우의 분할

피봇값이 가장 작거나 큰 경우이다.
퀵 정렬의 성능은 피봇 선택이 좌우한다. 위와 같이 가장 작거나 큰 값이 된다면 한 부분으로 치우치는 분할이 되며, 성능이 많이 떨어지게 된다.
입력의 크기가 n 이라면 , 최악의 경우 (n-1)+(n-2)+...+1 = n(n-1)/2
-> O(N^2)이다.

최선의 경우의 분할

1 / 2씩 균등하게 분할할 경우이다.
각 층에서 비교는 O(n)번씩, 총 층 수는 log n이니 즉 O(n log n)이다.

평균 경우의 분할

피봇을 항상 랜덤하게 선택한다고 가정하면, 평균 경우 시간복잡도를 계산할 수 있다.
평균 경우의 시간복잡도는 최선의 경우와 동일하게 O(n log n)이다.

피봇 선정 방법

• 랜덤하게 선정하는 방법
• 3개 숫자의 중앙값으로 선정하는 방법
  -> 최악의 경우는 피할 수 있다!!!

성능 향상 방법

• 입력의 크기가 매우 클 때, 삽입 정렬이 동시에 사용되면 성능이 더 향상된다.
  -> 사실, 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이긴 한다.
• 입력의 크기가 작을 때, 퀵정렬의 효율은 낮을 수 있다. -> 재귀호출 때문에
• 생물 정보 공학에서 접미 배열과 함께 퀵 정렬을 자주 쓴다.

3.3 선택 문제 (Selection)

선택문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제이다.

중앙값을 찾기에 용이해 데이터 분석을 위해 자주 사용된다. ( 평균 값은 왜곡된 분석을 야기시킨다...)

아이디어

• 1) 최소 숫자를 k번 찾는다.
• 2) 숫자들을 정렬 후, k번째 숫자를 찾는다. 위의 알고리즘은 각각 최악의 경우 O(kn)과 O(n log n)의 시간복잡도를 가진다.

  핵심 아이디어

  숫자들을 정렬 후 한 부분문제만 탐색하는 이진탐색 (Binary Search)과 유사한 개념을 사용해 입력을 Small Group & Large Group으로 1 / 2로 나눠 탐색하자.
  핵심은 나눠진 두 부분 중에서 한 부분만 검색한다는 점이다.
  피봇은 랜덤으로 정해진다.

  퀵 정렬과 유사하게 진행된다. 랜덤으로 지정된 피봇을 맨 왼쪽 인덱스와 Swap 해준다. 이후 작은 값과 큰 값과의 비교 및 교환을 해준 뒤 피봇과 4번째 인덱스와 Swap을 한다.
  피봇 값을 기준으로 좌측은 Small Group이 형성되었고, 우측은 Large Group이 형성되었다.
  만약 K = 7(찾고자 하는 숫자)이라면, Small Group에서 탐색을 할 필요없이 Large Group을 탐색하면 된다.
  이 과정을 반복하게 되면 해를 구할 수 있다.

  Selection 알고리즘은 분할 정복 알고리즘이면서, 랜덤 알고리즘이기도 하다. (피봇이 랜덤)
  만약 부분문제가 한 쪽으로 극단적으로 치우치게 된다면 알고리즘의 수행시간은 길어진다.( 퀵소트와 유사!)

  ---

  그렇다면 어떻게 분할되어야 좋은 분할이라고 할 수 있을까?

  분할된 그룹 중 하나의 크기가 입력 크기의 3 / 4 이상이면 나쁜(Bad) 분할 이라고 정의하자. 좋은(Good)분할은 반대로 생각하면 된다.

  예를 들어 위와 같이 16개의 숫자 중에 피봇이 5 ~ 12사이가 선정된다면 Good분할, 반대의 경우는 Bad분할이 된다.
  확률적으로는 각각 1 / 2의 확률을 가지고 있기 때문에 평균 2회 연속해서 랜덤하게 피봇을 정한다면 Good분할을 할 수 있게된다.

  시간복잡도는??

  입력 크기가 n에서부터 3 / 4배로 연속적으로 감소된다, Good분할만 연속적으로 이루어졌을 때의 평균 경우 시간복잡도는 O(n)이다.
  추가적으로 평균 2번 만에 Good분할이 되기 때문에 최종 시간복잡도는 2 * O(n) = O(n)이 된다!!

  ---

3.4 최근접 점의 쌍 찾기

2차원 평면상의 n개의 입력 값 중에서, 거리가 가장 가까운 한 쌍의 점을 찾는 문제이다.

간단한 방법

모든 점에 대해서 전수 조사(Brute Force)한다.
-> ex) 5개의 점을 전부 비교한다. 5 (5 - 1) / 2 = 10번 비교!!
즉 O(n^2) 이란 시간이 소요되는 방법이다.

이 방법은 비효율적이다. 분할 정복을 이용해보자

그렇다면 위와 같은 2차원 평면상의 점들 중 최근점 점의 쌍은 어떻게 구할까?

1) 입력된 점의 개수인 n개의 점을 1 / 2 로 분할한다.

2) 분할된 부분문제 중 짧은 거리를 가진 점의 쌍을 찾는다. (분 할과정에서 Sl or Sr에서도 계속 분할될 수 있다.)

3) d= min{왼쪽 부분 해, 오른쪽 부분 해} 를 구해 10 이내에 있는 중간 영역에 있는 점들 중 최근접 점의 쌍이 있는지 확인한다.

y값이 제외된 배열을 보면 4번, 5번 인덱스의 값들에서 d 값을 빼거나 더해준 범위의 값들이 중앙범위의 값들이 된다.

4) 중앙 영역에 속한 점들 중 최근접 점의 쌍 CPc를 찾아 리턴하면 끝이다.

시간복잡도

입력 S에 n개의 점이 있다고 가정한다.
전처리 과정에서 x좌표로 정렬하는데, O(n log n)의 시간이 소요된다.
추가적으로 층 수인 log n을 곱하면 O(n log^2 n) 이다.

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

분할정복이 부적절한 경우는 부분문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 매우 커지는 경우다.

예를 들어, n 번째 피보나치 수를 구할 때 F(n) = F(n-1) + F(n-2)로 정의되는데, 이 경우 입력은 1개이지만 사실상 n값 자체가 입력 크기인 것이다. 즉 n이라는 숫자에 의해 2개의 부분문제가 만들어지고 입력크기가 거의 2배로 늘어나게된다.

그래서 피보나치 계산의 경우 분할 정복 알고리즘보다는 For Loop를 사용하는게 중복된 계산 없이 간단하게 구할 수 있다.
사실 모든 문제에서 반복문을 사용할 수 있다면 재귀호출 보다는 반복문을 사용하는게 더 효율적이다.

이 알고리즘은 O(n)이 소요된다.