분할 정복 알고리즘이란

 
 
Division of Computer Science & Engineering, Chonbuk National University
안녕하세요!  분할정복 알고리즘을 연구하는 전북대학교  알고리즘 수업 5 조 Simple 입니다.

Сайн байцгаана уу? Чонбук Их Сургуулийн Пак Сунь Чоль багштай Алгоритмийн 5-р Simple баг та бүхэнтэй мэндчилж байна.

 
 
분할 정복법은 주어진 문제를 작은 사례로 나누어(Divide) 각각의 작은 문제들을 해결(Conquer)하는 방법입니다. 1805년 12월 2일 아우스터리츠 전투에서 프랑스의 황제 나폴레옹이 사용했던 훌륭한 전략에서 따왔습니다. 오스트리아-러시아 연합군은 나폴레옹의 군대보다 15,000명 정도 많았습니다. 연합군은 프랑스군의 우측면에 대규모 공격을 감행하게 되었습니다. 
공격을 예상한 나폴레옹은 연합군의 중앙으로 쳐들어가, 그들의 병력을 둘로 갈라 놓아버렸고, 둘로 나눠진 병력은 개별적으로는 나폴레옹의 군대와 상대가 되지 못했기 때문에, 패하고 퇴각하지 않을 수 없었습니다.
 
분할정복법은 위와 같은 사례를 적극 이용합니다.
  1. 문제의 사례를 2개 이상의 더 작은 사례로 나눈다.
  2. 이 작은 사례는 주로 원래 문제에서 따온다.
  3. 나눈 작은 사례의 해답을 바로 얻을 수 있으면 해를 구하고 아니면 더 작은 사례로 나눈다.
  4. 이처럼 해를 구할 수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법이다.
 
 
 

Digital Alarm Clock

가젯 사양 URL을 찾을 수 없습니다.
하위 페이지 (1): Gallery
Comments