# 분할정복

3개의 포스트

[BOJ 1629] 곱셈 (Java)

BOJ 1629 곱셈나에겐 너무나도 어려운 수학 문제... 그냥 외우자!제곱의 성질을 이용하여 분할정복으로 제곱 연산을 O(logn)에 처리하는 알고리즘이다.위와 같이 제곱수가짝수일 때는 밑^제곱수/2 \* 밑^제곱수/2 의 형태를홀수일 때는 밑^제곱수/2 \* 밑^제

2020년 2월 16일
·
0개의 댓글

분할 정복

부분 문제에 대한 각개 격파 > 첫 챕터 Brute force에서는 재귀 호출을 통해 큰 문제를 수 많은 작은 조각들로 나누어 하나씩 문제를 해결하는 방식으로 접근했다. 분할 정복 역시 이와 유사한 개념을 사용하지만, 큰 문제를 작은 문제들로 바로 쪼개는 것이 아니라 비슷한 크기의 문제들로 점점 쪼개 나가는 방식으로 문제를 해결한다는 점에서 차이가 있다...

2019년 6월 26일
·
0개의 댓글