6강 동적 프로그래밍 알고리즘(2)

스트링 편집거리 문제

• 두 문자열 X, Y 사이의 편집거리를 구하는 문제
  ✨편집거리?
  • 문자열 X를 Y로 변환하는데 필요한 전체 편집 연산에 대한 최소 비용
    1. 특정 위치에 새 문자를 삽입하는 연산
    2. 특정 위치의 문자를 삭제하는 연산
    3. 특정 위치의 문자를 다른 문자로 변경하는 연산
• 최적성의 원리
  X와 Y 사이의 편집 거리는 이들의 부분 문자열 사이의 편집거리를 포함한다. → 최적성의 원리를 만족하여 동적 프로그래밍 적용이 가능하다

모든 정점 간의 최단 경로(플로이드 알고리즘)

• 가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로
• 유형
  1. 단일 출발점 최단 경로: 하나의 특정 정점에서 다른 모든 정점으로의 최단 경로
  2. 모든 정점 간의 최단 경로 → 모든 조합의 두 정점 간의 최단 경로
• 플로이드 알고리즘은 가중치의 합이 음수인 사이클이 존재하지 않는 다는 가정하에 존재한다.