본문으로 이동

미디어위키 1.45 안정화가 거의 끝났습니다. 다만 Flow 확장 기능 관련 이슈가 있어서 대체하는 작업을 수행할 계획입니다.

  1. 큰숲백과:청사진에서 위키 발전의 대략적인 방향성을 제시했습니다. 의견이 있으신 분은 큰숲백과토론:청사진에서 의견을 남겨주시면 좋겠습니다.
  2. 기능상의 오류로 지원하지 않고 있는 기능에 대해서는 큰숲백과토론:이슈 트래커에 요약했습니다. 참고하시기 바랍니다.
  3. 데이터베이스 덤프 받고싶으신 분은 큰숲백과 가입 후에 사용자토론:Bigforest에 의견 남겨주시면 ftp 주소, 계정, 비밀번호를 특수:EmailUser를 통해서 공개할 예정입니다.

분할 정복

큰숲백과, 나무를 보지 말고 큰 숲을 보라.


분할 정복(Divide and Conquer)는 알고리즘의 설계 방법론 중 하나로, 알고리즘이 푸는 문제를 같은 종류의 작은 여러 하위 문제로 분할한 뒤 재귀적으로 하위문제를 푼 답을 모아 최종 답을 내는 과정을 거친다.

이때 분할된 문제가 계속 분할될 수록 일종의 트리 구조가 형성된다. 이 트리는 데이터의 값의 크기의 log값(밑 2)의 높이를 가진다.

Master theorem

[편집 | 원본 편집]

마스터 정리

어떤 n비트의 입력 데이터들에 대한 전체 실행시간을 T(n)이라고 하자. 이때 분할 정복에 따라 T(n) = a*T(n/b) + O(nd)가 되는 경우 다음이 성립한다.[1]

  • d > logba인 경우: T(n) = O(nd)
  • d = logba인 경우: T(n) = O(ndlog n)
  • d < logba인 경우: T(n) = O(nlogba)

가령 두 이진수의 곱셈의 경우 일반적으로는 나올 수 있는 최대 자리수(비트) n의 제곱의 시간 복잡도, O(n2)을 가지지만, 다음 함수를 설계하여 곱셈을 하는 알고리즘을 따를 경우 O(nlog23)의 시간 복잡도를 가진다.[2]

function BinaryMultiply(x, y)
    입력: n bit의 이진수 x, y
    출력: x와 y의 곱
    if n = 1: return xy
    xL와 xR = x을 반으로 갈랐을 때 왼쪽 비트들, 그리고 오른쪽 비트들
    yL와 yR = y을 반으로 갈랐을 때 왼쪽 비트들, 그리고 오른쪽 비트들
    P1 = BinaryMultiply(xL, yL)
    P2 = BinaryMultiply(xR, yR)
    P3 = BinaryMultiply(xL + xR, yL + yR)
    return P1 * 2n + (P3 - P1 - P2) * 2n/2 + P2

분할 정복을 사용하는 예

[편집 | 원본 편집]
  • 병합 정렬
  • 임의로 배열된 수의 중간값 구하기: 무작위 수를 골라 그보다 작은 수의 배열, 그 수와 같은 수들의 배열, 그보다 큰 수의 배열로 분할하게 된다.
  • 세그먼트 트리[3]의 초기화 및 탐색
  • 행렬의 곱의 고속화
  • Fast Fourier Transform(FFT): 전자기학 등에서 주파수 분석이나 디지털 신호 처리에 사용한다.
  1. ↑ 여기서 a > 0, b >1, d ≥ 0이란 조건이 붙는다.
  2. ↑ log23은 약 1.58~1.59의 값을 가진다
  3. ↑ 구간 합을 저장하는 이진 트리, 트리를 구현하는 배열의 인덱스는 1부터 시작하는 관례가 있다.