123 × 456 = ? 평소에 일상적으로 계산하던 방법을 분석적으로 풀어써보면 이렇다. 우리는 평소 한 자리에 0부터 9까지의 숫자만 사용하는 십진법을 사용하기 때문에, 각 자리별로 십의 자리 수는 다음 칸으로 넘겨준다(예를 들어 10의 자리 27은 (20 + 7)이므로 100의 자리로 2를 넘겨준다). (4 * 10000) + (13 * 1000) + (28 * 100) + (27 * 10) + (18 * 1) = (5 * 10000) + (6 * 1000) + (0 * 100) + (8 * 10) + (8 * 1) = 56088 최종적으로 값을 이렇게 계산해 낼 수있다. 456의 갯수만큼, 123의 각 원소(1, 2, 3)과 한 번씩 곱셈연산을 해야함을 알 수있다. 따라서 전통적인 방법으로는 만약 ..

의 해당 단원 밑줄입니다. "분할 정복을 사용하는 알고리즘들은 대개 세 가지의 구성 요소를 갖고 있습니다. 문제를 비슷한 크기의 더 작은 문제로 분할하는 과정(divide) 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)" "같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 좋은 예입니다. 여러번 중복되어 계산되면서 시간을 소모하는 부분 문제들이 있기 때문입니다." ​​ 병합 정렬 (Merge Sort) 수열을 가운데에서 쪼개 두 개의 부분수열로 만들고, 각 부분 수열에 대해서도 같은 절차를 재귀 호출한다. 기저 사례(base case)까지 쪼개 값이 반환되면, ..