# Dynamic Programming

• 2026년 8월 26일 알고리즘
  추가 설명 — 되짚기는 길 하나가 아니라 영역을 준다

  편집 거리의 표는 최솟값만 담는다. 표를 거꾸로 읽어 연산을 복원하면 최선의 길이 여럿일 수 있고, 그래서 결과는 길 하나가 아니라 표 위의 영역이 된다.

• 2026년 8월 26일 알고리즘
  편집 거리 — 비슷하다는 말을 수로 바꾸기

  자리끼리만 맞추는 Hamming 거리는 글자 하나가 빠지면 뒤가 전부 밀려 무너진다. 빈 칸을 허용해 정의한 편집 거리를 표 하나로 채우고, O(NM)보다 빠를 수 없다는 말의 정확한 뜻까지 짚는다.

• 2026년 8월 11일 알고리즘
  플로이드·워셜의 메모리 줄이기 — N³칸에서 N²칸으로

  플로이드·워셜은 D[k][i][j]로 N³칸을 쓴다. k를 계산할 때 k-1층만 참조한다는 점에서 2층으로 줄이고, D^{k-1}[i][k]와 D^k[i][k]가 같다는 것을 보여 1층으로 줄인다. 덮어써도 답이 변하지 않는 이유를 증명한다.

• 2026년 8월 11일 알고리즘
  모든 쌍 최단 거리 — 다익스트라 N번과 플로이드·워셜

  한 시작점이 아니라 모든 노드 쌍의 최단 거리를 구한다. 다익스트라를 N번 돌리는 기준선을 세우고, 경유할 수 있는 노드를 {1..k}로 제한해 k를 늘려 가는 플로이드·워셜을 유도한다. 점화식 D^k[i][j]=min(D^{k-1}[i][j], D^{k-1}[i][k]+D^{k-1}[k][j])가 왜 성립하는지 양방향으로 증명한다.

• 2026년 8월 6일 알고리즘
  최대 부분배열 — 자리마다 최선 하나만 들고 간다

  합이 가장 큰 연속 구간을 찾는 문제를 세 번 푼다. 모든 구간을 세면 O(N³), 누적합을 미리 만들면 O(N²), 각 자리에서 끝나는 최선의 합 하나만 들고 가면 O(N)이다. 빈 배열을 답으로 허용하느냐가 점화식을 어떻게 바꾸는지까지 본다.

• 2026년 7월 31일 알고리즘
  추가 설명 — 어떤 순서로 곱했는지 되짚기

  동적 계획법 ③의 표는 최소 비용만 담는다. 어떤 괄호 순서로 곱해야 그 비용이 나오는지는 표에 없다. 채우는 동안 이긴 분할점 k를 함께 적어 두면 (1,n)에서 재귀로 (M₁(M₂M₃)) 같은 괄호화를 복원한다. d=[3,2,4,2] 예시로 되짚고, 파스 트리와 동점의 미묘함까지 짚는다.

• 2026년 7월 30일 알고리즘
  동적 계획법 ③ — 구간을 어디서 자를 것인가

  행렬 M₁×…×Mₙ을 곱할 때 결과는 같아도 곱셈 횟수는 괄호를 어디에 치느냐로 달라진다. (3×2)(2×4)(4×2)는 48번 대 28번. '이 구간의 마지막 곱을 어디서 하는가'라는 결정에서 M[i,j]=minₖ(M[i,k]+M[k+1,j]+d_{i-1}d_k d_j)를 세우고, 짧은 구간부터 채워 O(n³)에 푼다. dp-2의 결정 사고를 원소에서 구간으로 확장한다.

• 2026년 7월 28일 알고리즘
  추가 설명 — 어느 날을 골랐는지 되짚기

  동적 계획법 ②의 표는 최댓값만 담는다. 채운 표를 마지막 칸부터 거꾸로 읽으면 어느 날을 골랐는지도 복원된다. a=[3,5,6,10] 예시로 직접 되짚고, 되짚기를 코드로 옮긴 뒤 동점 처리의 미묘함까지 짚는다.

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

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

• 2026년 7월 24일 알고리즘
  동적 계획법 ① — 피보나치로 배우는 재귀·메모이제이션·DP

  피보나치를 세 방법으로 푼다. 정의 그대로의 재귀는 같은 부분 문제를 지수 번 다시 풀어 O(2^n)에 가깝다. 계산한 값을 적어 두는 메모이제이션은 O(N)으로 줄인다. 채우는 순서까지 알면 재귀 없이 상향식으로 채우는 동적 계획법이 된다.