# Recurrence

• 2026년 7월 28일 알고리즘
  동적 계획법 ② — 점화식은 어떻게 세우는가

  날마다 일급이 다르고 연속된 날엔 일할 수 없을 때 총 일급을 최대화한다. '최적해가 마지막 날을 포함하는가?'라는 결정 하나에서 S(n)=max(S(n-1), S(n-2)+aₙ)을 유도하고, 상향식으로 O(n)에 푼다. DP①이 점화식을 계산했다면 ②는 점화식을 세운다.

• 2026년 7월 27일 알고리즘
  카라츠바 알고리즘 — n자리 곱셈은 n²보다 빠를 수 있다

  n자리 두 수를 곱하는 데 정의대로면 Θ(n²)이 든다. 반으로 잘라 재귀해도 곱셈이 4번이라 여전히 n²이다. 카라츠바는 (x₁+x₂)(y₁+y₂) 하나로 곱을 3번으로 줄여 Θ(n^1.585)를 얻는다. Strassen의 8→7과 같은 구조를, 한 단계 더 단순한 무대에서 본다.

• 2026년 7월 23일 알고리즘
  행렬 곱셈 — 나누기만으로는 못 이긴다, Strassen이 곱을 줄이는 법

  N×N 행렬 곱은 정의대로면 O(N³)이다. 2×2 블록으로 나눠 재귀해도 곱셈이 8번이라 여전히 N³이다. Strassen은 곱셈을 7번으로 줄여 O(N^2.807)을 얻는다. 왜 지수가 바뀌는지, 7개의 곱이 답을 재구성하는지 검증한다.