반응형 이진 탐색1 Divide and Conquer design pattern(분할정복) 이전에는 알고리즘의 효율성을 판단하는 방법을 살펴봤었다. 이제 처음에 언급했듯이 하나의 디자인 패턴을 이용하여 몇가지 문제를 해결해보고 이를 분석해보자. Introduction to Divide-and-Conquer divide&conquer. 한글로 해석하면 나눠서 정복하는 것이다. 즉 input으로 주어진 instance가 너무 거대할 때, 이를 두개 이상의 작은 부분으로 나누어 이것들을 하나씩 해결해나가는 것이다. 작은 부분들을 해결한 결과물을 합치게되면 원래 해결하고자 했던 문제를 해결할 수 있게 되는 것이다. 만약 나눠진 문제가 해결하기에 여전히 큰 문제라면, 이를 해결할 수 있을 때까지 더 작은 조각으로 나눌 수 있다. 이러한 divide&conquer 접근은 original problem의 .. 2021. 10. 4. 이전 1 다음 반응형
