Divide#Conquer#combine
-
#Divide#Conquer#combine#1부터 n까지 더하는 문제Data miner 2019. 7. 8. 14:34
문제를 부분으로 나눠서(Divide), 그것들의 해답을 구한다(Conquer). 그 부분의 답들을 적절하게 합쳐서(Combine) 전체의 답을 구한다. 먼저 Divide & Conquer의 경우에도 1) 자신이 정의한 함수를 써도 되지 않아도 되는 base부분과 함수를 적용해 2) recursive 되게 풀어야 하는 부분 두 가지 경우를 나누어서 생각해야 한다. 1부터 n까지 더하는 문제를 생각해보자. 가장 쉽게는 for문을 사용해서 1부터 n까지의 값을 차례대로 호출하여 더해가는( += data)를 생각해볼 수도 있으나, Divide & Conquer하여 푼다고 생각해보자. 어떤 경우에 반복적인 함수를 써도 되지 않을까? 더 이상 부분으로 쪼개어 나누어서 풀 수 없는 경우 즉, start 부분과 end..