'분할정복' 태그의 글 목록

이번 포스팅은 알고리즘을 설계하는 방법 중 분할정복 방법에 대한 포스팅입니다. 분할정복이란 글자 그 자체로 이해하면 편합니다. 1. 분할 : Data를 분할한다. 2. 정복 : 분할된 Data에 알고리즘을 적용한다. 3. 결합 : 정복단계의 알고리즘 결과를 취합한다. 위 3단계를 거쳐서 알고리즘이 수행되는 단계를 거치는 알고리즘 설계기법입니다. (단, 3단계 결합이 빠지는 경우도 분할정복 방법론으로 봅니다) 분할정복을 사용하는 알고리즘으로는 이진탐색, 퀵정렬, 합병정렬등을 예로 들 수 있습니다 이진 탐색을 예로 볼까요? 위 이진탐색의 내용을 다시 보겠습니다. 정복에서 알고리즘이 종료되지 않는다면 분할 단계에서 받은 부분배열에서 또다시 부분배열을 나누게 됩니다. 원하는 수준으로 작은 Data가 나오기 전까..