[알고리즘] Divide and Conquer (분할정복)

2016. 10. 14. 09:12·프로젝트 관련 조사/알고리즘
반응형

출처:http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5



분할정복

정의 : 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다.


알고리즘을 설계하는 요령

(1) Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.

(2) Conquer : 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.

(3) Combine : Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다.


  • 문제를 제대로 나누면 Conquer하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 가장 중요하다.
  • 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다.


분할정복의 응용

1. 병합 정렬 (Merge Sort)

헝가리 출신 미국인 수학자인 존 폰 노이만이 1945년에 개발한 알고리즘이다. 시간복잡도는 이고, 공간복잡도는 이다.


알고리즘

1. 정렬할 데이터 집합의 크기가 0또는 1이면 이미 정렬된 것으로 보고, 그렇지 않으면

2. 데이터 집합을 반으로 나눈다.

3. 원래 같은 집합에서 나뉘어져 나온 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단, 병합할 때 데이터 집합의 원소는 순서에 맞춰 정렬한다.

4. 데이터 집합이 다시 하나가 될 때까지 3을 반복한다.


예를 들어 다음과 같은 데이터 집합이 있다고 해보자.



알고리즘의 1~2 과정을 반복하여 나눈다. 색칠한 부분은 나눈 기준이 되는 부분이다.




분할을 했으니 정복을 할 차례다. 3~4과정을 반복해서 수행한다.


조각난 데이터 집합을 정렬해가면서 병합하면 결국 완전히 정렬된 하나의 데이터 집합을 얻는 알고리즘이다.


그런데 병합이 어떻게 정렬하면서 합칠 수 있는 것일까.


두 데이터 집합을 정렬하면서 합치는 방법

1. 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합을 만든다.

2. 두 데이터 집합의 첫 번째 요소들을 비교하여 작은 요소를 빈 데이터 집합에 추가한다. 그리고 새 데이터 집합에 추가한 요소는 원래 데이터 집합에서 삭제한다.

3. 원래 두 데이터 집합의 요소가 모두 삭제될 때 까지 2를 반복한다.


예를 들어 다음과 같은 데이터 집합 A, B와 이 두 데이터 집합의 크기의 합만큼의 크기를 가지는 빈 데이터 집합인 C가 있다고 하자.


두 데이터 집합의 첫 번째 요소를 비교한다. A의 첫 번째 요소는 2, B의 첫번째 요소는 1이므로 B의 것이 더 작다. C에 1을 추가하고 B에서 1을 삭제한다.


그 다음 A의 2와 B의 3을 비교한다. 2가 작으니 C에 2를 추가하고 A에서 2를 삭제한다.


A의 5와 B의 3을 비교한다. 3이 작으니 C에 3을 추가하고 B에서 3을 삭제한다.

이렇게 데이터 A와 B의 요소들을 비교해서 C에 넣고 A와 B의 각 요소들을 삭제해나가다보면, A에 9하나만 남게된다. B에는 비교할 요소가 남아 있지 않으므로 그냥 9를 C에 추가하고 A에서 9를 삭제한다. 이로써 A와 B의 요소들이 모두 삭제되었고 C는 정렬된 데이터 집합이 되었다.


2. 거듭 제곱 (Exponentiation)

n거듭 제곱은 자신을 n번 곱해야 함으로 의 시간이 소요된다. 이것을 개선하기 위해서 연산방법을 조금 바꾸어보자.


은 다음과 같이 정의되지만,

다음과 같이 표현할 수도 있다.

을 구할 때 C를 8번 곱하지 않고 를 구한 뒤 제곱을 두 번 더 반복하면 결국 세번의 연산만으로 같은 결과를 얻을 수 있다.

지수가 짝수일때는 지수를 반으로 나눠서 곱한다.

지수가 홀수일때는 지수에서 1을 빼고 반으로 나누어서 곱하고 밑을 한번 더 곱하면 된다.


이렇게 지수를 반으로 나눠가는 거듭 제곱 알고리즘의 수행 시간은 이다.


3. 피보나치 수열 (Fibonacci Sequence)

피보나치 수열은 다음과 같이 정의된다.


이 알고리즘으로는 걸리는 시간은 이다.

연산을 줄이기 위해 2차 정사각행렬을 이용한다.


 이므로 n제곱을 하게 되면



  이렇게 거듭제곱 알고리즘때와 비슷하게 나타낼 수 있다.

수행 시간 또한 거듭 제곱 알고리즘과 똑같은 이 걸리게 된다.

반응형
저작자표시 (새창열림)

'프로젝트 관련 조사 > 알고리즘' 카테고리의 다른 글

[알고리즘] Backtracking (백트래킹)  (0) 2016.10.14
[알고리즘] Dynamic Programming (동적 계획법)  (0) 2016.10.14
[알고리즘] Greedy Algorithm (탐욕 알고리즘)  (0) 2016.10.14
[C++ STL] Header <algorithm> – 1. Sort 파헤치기 (1)  (0) 2016.10.10
[알고리즘] 몬테카를로 알고리즘  (0) 2016.06.01
'프로젝트 관련 조사/알고리즘' 카테고리의 다른 글
  • [알고리즘] Backtracking (백트래킹)
  • [알고리즘] Dynamic Programming (동적 계획법)
  • [알고리즘] Greedy Algorithm (탐욕 알고리즘)
  • [C++ STL] Header <algorithm> – 1. Sort 파헤치기 (1)
호레
호레
창업 / IT / 육아 / 일상 / 여행
    반응형
  • 호레
    Unique Life
    호레
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 법률
        • 기본
        • 개인정보보호법
        • 정보통신망법
        • 전자금융거래법
        • 전자금융감독규정
        • 신용정보법
        • 온라인투자연계금융업법
      • 창업
        • 외식업 관련
        • 임대업 관련
        • 유통업 관련
        • 세무 관련
        • 마케팅 관련
        • 기타 지식
        • 트렌드
        • Youtube
      • IT기술 관련
        • 모바일
        • 윈도우
        • 리눅스
        • MAC OS
        • 네트워크
        • 빅데이터 관련
        • A.I 인공지능
        • 파이썬_루비 등 언어
        • 쿠버네티스
        • 기타 기술
      • 퍼블릭 클라우드 관련
        • Azure
        • GCP
        • AWS
      • 정보보안 관련
        • QRadar
        • Splunk
        • System
        • Web
      • 기타
        • 세상 모든 정보
        • 서적
      • 게임 관련
        • 유니티
      • 부동산
      • 맛집 찾기
        • 강남역
        • 양재역
        • 판교역
        • ★★★★★
        • ★★★★
        • ★★★
        • ★★
        • ★
      • 결혼_육아 생활
        • 리얼후기
        • 일상
        • 육아
        • 사랑
        • Food
      • 영어
        • 스피킹
        • 문법
        • 팝송
        • 영화
      • K-컨텐츠
        • 드라마
        • 영화
        • 예능
      • 독서
      • 프로젝트 관련 조사
        • 시스템 구축
        • 로그 관련
        • 웹
        • APT
        • 모의 해킹
        • DB
        • 허니팟
        • 수리카타
        • 알고리즘
        • FDS
      • 기업별 구내 식당 평가
        • 한국관광공사
        • KT telecop
        • KT M&S
        • KT powertel
        • KT cs 연수원
        • 진에어
      • 대학 생활
        • 위드윈연구소
        • 진로 고민
        • 채용정보
        • 자동차
        • 주식
        • 악성코드
        • 게임 보안
      • 쉐어하우스
  • 블로그 메뉴

    • 홈
    • 게임 관련
    • IT 기술 관련
    • 태그
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    무역전쟁
    상호관세
    수제버거
    마케팅
    런치
    점심
    쥬쥬랜드
    보안가이드
    맛집
    유니티
    판교역
    이재곧죽습니다
    수제버거존맛
    대통령
    AWS
    복리후생
    판교
    판교맛집
    수제버거맛집
    돈까스
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
호레
[알고리즘] Divide and Conquer (분할정복)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.