분할 정복을 이용한 재귀적 다항식 곱셈
다항식 곱셈을 효율적으로 처리하기 위해 분할 정복(Divide and Conquer) 기법을 사용할 수 있습니다. 다항식을 일정한 단위로 분할하여 재귀적으로 곱셈을 수행하며, 이 과정에서 다항식의 덧셈과 뺄셈 함수가 보조적으로 사용됩니다. 다음은 리스트 형태로 인코딩된 다항식을 계산하는 로직입니다.
def add_poly(p1, p2):
length = max(len(p1), len(p2))
res = [0] * length
for i in range(length):
v1 = p1[i] if i < len(p1) else 0
v2 = p2[i] if i < len(p2) else 0
res[i] = v1 + v2
return res
def sub_poly(p1, p2):
length = max(len(p1), len(p2))
res = [0] * length
for i in range(length):
v1 = p1[i] if i < len(p1) else 0
v2 = p2[i] if i < len(p2) else 0
res[i] = v1 - v2
return res
def multiply_poly_recursive(poly_a, poly_b):
n = max(len(poly_a), len(poly_b))
if n == 0: return [0]
if n == 1: return [poly_a[0] * poly_b[0]]
mid = n // 2
a_low = poly_a[:mid]
a_high = poly_a[mid:]
b_low = poly_b[:mid]
b_high = poly_b[mid:]
# 재귀적 분할 (단순화된 분할 정복 모델)
term1 = multiply_poly_recursive(a_low, b_low)
term2 = multiply_poly_recursive(a_high, b_high)
# 실제 구현 시에는 차수에 따른 위치 조정(Shift) 로직이 추가되어야 함
# 여기서는 분할 및 재귀 구조의 핵심 개념을 중점적으로 다룸
return add_poly(term1, term2)
블록 분할을 이용한 행렬 곱셈 알고리즘
행렬 A와 B를 각각 분할하여 곱셈을 수행하는 방식입니다. 예를 들어, 행렬 A를 세로로 분할하여 $A = [A_1, A_2]$로 만들고, 행렬 B를 가로로 분할하여 $B = [B_1, B_2]^T$로 만들면, $A \cdot B = A_1 B_1 + A_2 B_2$의 형태로 계산할 수 있습니다.
import numpy as np
def block_matrix_multiply(matrix_x, matrix_y):
# 행렬 분할 위치 계산
col_mid = matrix_x.shape[1] // 2
row_mid = matrix_y.shape[0] // 2
# A = [A1 | A2], B = [B1 / B2] 형태로 분할
x_left = matrix_x[:, :col_mid]
x_right = matrix_x[:, col_mid:]
y_top = matrix_y[:row_mid, :]
y_bottom = matrix_y[row_mid:, :]
# 분할된 블록의 곱을 합산
final_result = np.dot(x_left, y_top) + np.dot(x_right, y_bottom)
return final_result
# 실행 예시
mat_a = np.array([[1, 2, 3, 4], [5, 6, 7, 8]])
mat_b = np.array([[1, 2], [3, 4], [5, 6], [7, 8]])
output = block_matrix_multiply(mat_a, mat_b)
print(output)
이항 계수(Binomial Coefficient)의 재귀적 구현
이항 계수는 조합론의 기초로, 다음과 같은 재귀적 정의를 가집니다. $m = 0$이거나 $n = m$일 때 결과는 1이며, 그 외의 경우 $\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}$이 성립합니다.
def get_binomial_coeff(n, k):
# 기저 사례 처리
if k == 0 or n == k:
return 1
# 재귀 호출을 통한 합산
return get_binomial_coeff(n - 1, k - 1) + get_binomial_coeff(n - 1, k)
변형된 하노이의 탑: 인접 기둥 이동 제약
가장 왼쪽 기둥에서 가장 오른쪽 기둥으로 원판을 옮길 때, 양 끝 기둥 간의 직접적인 이동이 불가능한 '측향(Side)' 하노이의 탑 문제입니다. 모든 이동은 반드시 중간 기둥을 거쳐야 합니다.
이 경우 $n$개의 원판을 옮기는 과정은 다음과 같습니다:
- $n-1$개의 원판을 왼쪽에서 오른쪽으로 이동시킵니다.
- 가장 큰 원판을 왼쪽에서 중간으로 이동시킵니다.
- $n-1$개의 원판을 오른쪽에서 왼쪽으로 이동시킵니다.
- 가장 큰 원판을 중간에서 오른쪽으로 이동시킵니다.
- $n-1$개의 원판을 왼쪽에서 오른쪽으로 다시 이동시킵니다.
이진 탐색 트리(BST)의 노드 개수 계산
트리 구조가 [이름, 생일, 왼쪽_서브트리, 오른쪽_서브트리] 형태의 리스트로 구현되어 있을 때, 전체 노드의 개수를 구하는 재귀 함수입니다.
def count_tree_nodes(node_data):
# 빈 트리인 경우
if not node_data:
return 0
# 왼쪽 및 오른쪽 자식 노드의 개수를 재귀적으로 계산
left_side = count_tree_nodes(node_data[2])
right_side = count_tree_nodes(node_data[3])
# 현재 노드(1) + 좌우 서브트리 노드 합계
return 1 + left_side + right_side
연속된 동일 요소로 구성된 가장 긴 부분 리스트 찾기
리스트 내에서 동일한 값이 연속해서 나타나는 가장 긴 구간을 찾는 문제입니다. 이를 위해 모든 요소가 동일한지 확인하는 보조 함수를 사용하는 방식과, 보조 함수 없이 단일 재귀로 해결하는 방식이 있습니다.
# 보조 함수를 사용하는 방식
def is_uniform(elements):
if len(elements) <= 1:
return True
return elements[0] == elements[1] and is_uniform(elements[1:])
def find_longest_streak(arr):
if not arr:
return []
longest = []
n = len(arr)
for start in range(n):
for end in range(start + 1, n + 1):
sub = arr[start:end]
if is_uniform(sub):
if len(sub) > len(longest):
longest = sub
return longest
# 예시 데이터: [1, 3, 5, 5, 4, 4, 4, 5, 5, 6] -> 결과: [4, 4, 4]