곱셈1 [알고리즘] 분할 정복 & 백준(곱셈, 행렬 제곱) 분할 정복(Divide & Conquer) 분할 정복은 문제를 여러개로 나누어서 푸는 알고리즘이다. 교수님께서 미친듯이 강조해서 "디바이드앤퀀쿼"만 기억이 난다.. * 동적 계획법(DP)과의 차이점 1. 동적 계획법은 분할한 문제들이 서로 영향을 미침. 2. 분할 정복은 분할한 문제들이 서로 영향을 미치지 않음. * 분할 정복의 필요조건 1. 문제를 나눌 수 있어야 한다. 2. 부분 문제의 답을 이용하여 원래 문제의 답을 계산하는 방법이 있어야 한다. * 분할 정복의 알고리즘의 접근법 1. 분할: 문제를 작은 문제로 분할하는 과정 2. 정복: 분할한 작은 문제들을 해결 3. 조합: 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합한다. 분할 정복을 이용한 거듭제곱 먼저, 거듭제곱이란 주어진 수를 주.. 2022. 10. 5. 이전 1 다음
