본문 바로가기

분할정복

알고리즘 2020. 11. 3. [BOJ] 11444번: 피보나치 수 6 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 사용 알고리즘 divide and conquer memoization 시간 복잡도 O($M^3 log N$) : ( M : 행렬의 크기, N : N번째 항 ) 풀이 N이 아주 큰 $10^18$이기 때문에, 일반적인 1차원의 DP 점화식을 이용해서는 풀 수 없다. 점화식을 행렬의 형태로 표현하였으며, 행렬의 거듭제곱을 이용하여 시간복잡도가 O($M^3 log N$)로 풀 수 있다. 피보나치의 일반적인 점화식은 A[n] = A[n-1] + A[n-2] (A > 2)의 형태이다. 일반적인 점화식의 경우 O($N$)이며, 시간복잡도가 아주 커서 시..
알고리즘 2020. 10. 21. [BOJ] 10167번: 금광 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 www.acmicpc.net 사용 알고리즘 plane sweeping segment tree 시간 복잡도 O($N^2 log N$) 풀이 N이 최대 3000이기 때문에 시간 복잡도가 최대 O($N^2 logN$)인 알고리즘을 사용하여야 한다. 금광들을 직사각형 모양의 영역으로 묶어 이익을 확인할 경우, 금광들의 가장 좌측 상단에 있는 금광과 가장 우측 하단에 있는 금광을 기준으로 직사각형을 만들 수 있다. 따라서 금광들의 위치만으로 분할정복을 통해 구간의 합을..

티스토리툴바