조용하지않는개발Blog

분할 정복 이란? 어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식. 라고 하는데 말로 설명하면 어렵다. 그래도 최대한 이해하기 쉽게 설명을 진행하겠다. 먼저 3을 10번 곱한다면 식으로 $$ 3*3*3*3*3*3*3*3*3*3 = 3^{10} $$이런식으로 계산을 하게 된다. 이때 분할 정복을 사용하면 $$ 3^{2}*3^{2}*3^{2}*3^{2}*3^{2} $$ 으로 나누어지고 계산된 값인 9를 $$ 9^{2}*9^{2}*9 $$ 이어서 또 다시 81을 $$ 81^{2}*9 $$ 만 계산하면 끝이난다 총 10번 반복할것은 3번으로 줄인것이다. 이처럼 분할 정복을 이용하면 시간을 단축시킬 수 있다. def Recursiv..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보면 단순해 보이지만 곱한수를 반복하다보면 시간 초과가 나는 문제이다. 이때 단순하게 나머지인 C의 길이만큼만 계산하면 해결하지 않을까 생각을 하며 풀었지만 시간 초과가 나오며 다른 사람들의 힌트를 얻어 문제를 해결하였다. 분할정복을 이용한 거듭제곱으로 재귀함수를 통해 곱셈을 줄여서 계산을 하면 O(n)을 O(nlogn)으로 바꿀수있어서 문제를 해결할수있다. 이번에 분할정복 관련해서는 알고리즘에 작성하며 나중에 비슷한 ..