songyc/Logseq
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Logseq/pages/분할정복(Divide and Conquer).md
songyc macbook 9fd4bd6191 logseq 20260110
2026-01-10 22:46:58 +09:00

7.2 KiB
Raw Permalink Blame History

deck:: Logseq/coding tip

  • 1. 개념(Concept)

    • 크고 복잡한 문제를 {{c1 작고 간단한 하위 문제(Sub-problem)}}들로 나눈 뒤, 각각 해결하여 합치는 알고리즘 설계 패러다임. id:: 695bbd99-6b9b-4019-a174-9238a89758de

  • 2. 동작 원리 (Algorithm Flow)

    • 1단계 {{c1 분할(Divide)}} -> 2단계 {{c1 정복(Conquer)}} -> 3단계 {{c1 결합(Combine)}}

      id:: 695bbe3e-8b85-4abf-a9ed-6f0c24c8f2dd #+BEGIN_EXTRA 분할 : 원래 문제를 같은 유형의 더 작은 하위 문제로 쪼갠다. 정복 : 하위 문제를 재귀적으로 해결한다.(문제가 충분히 작다면 바로 해결) 결합 : 하위 문제의 해답들을 합쳐 원래 문제의 답을 만든다. #+END_EXTRA

  • 3. 시간복잡도

    • 문제의 크기를 N 이라고 할 때 {{c1 $O(\log N)$}} 이나 {{c1 $O(N \log N)$}} 으로 감소됨.

      id:: 695bbeb8-ecdc-4d0b-a29b-43231188ba86

  • 4. 예시

    • 1) 행렬의 거듭제곱(N \times N 크기의 행렬 $A$를 $B$번 거듭제곱 하기)

      • 점화식

        • $n$이 짝수일 때: A^n = (A^{n/2}) \times (A^{n/2})
        • $n$이 홀수일 때: A^n = (A^{n/2}) \times (A^{n/2}) \times A

      • 행렬곱(multiply_matrix) 함수 코드(python)

        id:: 695bc027-6274-498e-b798-0e94060eb147 N \times N 크기의 행렬 m1, m2와 N을 입력받아서 두 행렬을 곱한 행렬을 반환하는 코드 #card 
        • def multiply_matrix(m1, m2, N):
    result = [[0]* N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                result[i][j] += m1[i][k] * m2[k][j]
            result[i][j] %= 1000  # 문제 조건에 따라 모듈러 연산 추가
    return result

      • 분할정복(power_matrix) 함수 코드(python)

        거듭제곱 될 행렬 adj, 현재 곱해지는 지수 n, 행렬의 크기 N을 입력받아서 분할정복으로 adj^n 을 구하는 코드
          1. n이 1일 경우(차수가 1일 경우) #card id:: 695bc161-b88a-4f55-aaf7-7bc17ccd4dcc
          • # Base case : 지수가 1이면 그대로 반환한다.
if n==1 :
  	return [[num % 1000 for num in row] for row in adj]
          1. 분할 #card id:: 695bc1d6-8a7c-475c-9c51-45a672597058
          • # Divide: 지수를 절반으로 나누어 재귀 호출
temp = power_matrix(adj, n//2, N)
          1. 정복 및 결합 #card id:: 695bc232-7ee9-4c02-a3b1-1f65061737f9
          • if n % 2 == 0:
	# 짝수면: temp * temp
   	return multiply_matrix(temp, temp, N)
else:
    # 홀수면: temp * temp * A
    return multiply_matrix(multiply_matrix(temp, temp, N), adj, N)
        • 전체코드 
          • # 행렬 곱셈 함수 (N*N 행렬 두 개를 곱함)
def multiply_matrix(m1, m2, N):
    result = [ * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                result[i][j] += m1[i][k] * m2[k][j]
            result[i][j] %= 1000  # 문제 조건에 따라 모듈러 연산 추가
    return result

# 분할 정복을 이용한 거듭제곱 함수
def power_matrix(adj, n, N):
    # Base Case: 지수가 1이면 그대로 반환
    if n == 1:
        return [[elem % 1000 for elem in row] for row in adj]

    # Divide: 지수를 절반으로 나누어 재귀 호출
    temp = power_matrix(adj, n // 2, N)

    # Conquer & Combine
    if n % 2 == 0:
        # 짝수면: temp * temp
        return multiply_matrix(temp, temp, N)
    else:
        # 홀수면: temp * temp * A
        return multiply_matrix(multiply_matrix(temp, temp, N), adj, N)

    • 2) 피보나치 수열을 행렬로 표현해서 분할정복으로 구하기

      • 피보나치 수열의 행렬화

        • 피보나치 수열의 점화식 $F_n = F_{n-1} + F_{n-2}$를 행렬 곱셈 형태로 변환.
            1. 기본 점화식의 행렬화 #card id:: 69623201-075b-4955-9d5b-aedcbcf16170
            • F_{n+1} = F_n + F_{n-1} F_n = F_{n-1} + F_{n-2} 
            • 
\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}
            1. 재귀적으로 쭉 대입하면 최종적으로 다음과 같은 식이 나옴. #card id:: 69622f8c-b595-40fc-83b5-7298ca660f3a
            • 
\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F_1 \\ F_0 \end{bmatrix}

            • 
\begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix}
              #+BEGIN_EXTRA 즉 \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n 값의 1행 0열의 값이 F_n 값이 된다. #+END_EXTRA

        • 결론 : \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n 을 계산하면 n번째 피보나치 수열의 항을 구할 수 있다.

      • 예시문제 : n번째 피보나치 수를 1000000007 로 나눈 나머지를 출력하라.(Python)

        id:: 6962333f-ebe3-43a9-bca6-96e9442286e1 정의할 함수는 mul_mat(m1, m2) 와 power_mat(adj, n) 이다. 아래와 같이 코드가 주어질 때 두 함수를 정의하라. 
        import sys
input = sys.stdin.readline

# 문제에서 요구하는 나누기 상수
MOD = 1_000_000_007

# 1. 행렬 곱셈 함수 (2x2 고정)
def mul_mat(m1, m2):
    # 행렬 곱

# 2. 분할 정복을 이용한 거듭제곱
def power_mat(adj, n):
  	# 분할정복

# Main
n = int(input())

# 기본 행렬 [[1, 1], [1, 0]]
base_matrix = [[1, 1], [1, 0]]

# 행렬 제곱 계산
result_matrix = power_mat(base_matrix, n)

# 1행 0열의 값이 n번째 값
print(result_matrix[1][0])
        #card 
        • import sys
input = sys.stdin.readline

# 문제에서 요구하는 나누기 상수
MOD = 1_000_000_007

# 1. 행렬 곱셈 함수 (2x2 고정)
def mul_mat(m1, m2):
    res = [[0]*2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                res[i][j] += m1[i][k] * m2[k][j]
                res[i][j] %= MOD
    return res

# 2. 분할 정복을 이용한 거듭제곱
def power_mat(adj, n):
    if n == 1:
        return [[x % MOD for x in row] for row in adj]

    temp = power_mat(adj, n // 2)

    # 짝수일 때: A^(n//2) * A^(n//2)
    if n % 2 == 0:
        return mul_mat(temp, temp)
    # 홀수일 때: A^(n//2) * A^(n//2) * A
    else:
        return mul_mat(mul_mat(temp, temp), adj)

# Main
n = int(input())

# 기본 행렬 [[1, 1], [1, 0]]
base_matrix = [[1, 1], [1, 0]]

# 행렬 제곱 계산
result_matrix = power_mat(base_matrix, n)

# 1행 0열의 값이 n번째 값
print(result_matrix[1][0])