안녕

가능하다면 다음 두 가지 경우에 대해서는 분할 정복을 피해야 합니다. instance of size N is divide into two or more instances each almost size n. 크기가 n인 사례가 거의 n에 가까운 두 개 이상의 사례로 분할될 때 이렇게 분할하면 지수 시간 알고리즘이 나옵니다. instance of size N is divied into almost n instances of size n/c, where c is a constant 4개로 쪼갰는데, 다시 4번의 재귀할 때, 혹은 2개로 쪼갰는데, 2번 재귀할 때 이렇게 분할하면 \(n^{\Theta(nlgn)}\)의 알고리즘이 나옵니다. 만약 피보나치수열을 재귀적인 방법 즉, 분할 정복을 이용해서 문제를 해결..

from os import sep import sys input = sys.stdin.readline count = 0 def mmult(n, a, b, c): # 단순 행렬 곱셈 for i in range(n): for j in range(n): for k in range(n): c[i][k] += a[i][j] * b[j][k] # += 해줘야함. 그냥 =를 하면 마지막으로 들어가는 값으로만 치환됨 def partition(n, a, a11, a12, a21, a22): # 행렬 분할 for i in range(n): for j in range(n): a11[i][j] = a[i][j] a12[i][j] = a[i][j + n] a21[i][j] = a[i + n][j] a22[i][j] = a[i ..