tonirr

최단경로 가중방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로 플로이드 알고리즘 모든 정점 간의 최단 경로 동적 프로그래밍 방법 적용 O(|V|^3) 가중치의 합이 음수인 사이클이 없다고 가정 플로이드 Floyd 알고리즘 다익스트라 Dijkstra 알고리즘 모든 정점 간의 최단 경로 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 (단일 출발점 최단 경로) 동적 프로그래밍 방법 적용 그리디 방법 적용 O(|V|^3) O(|V|^2) 가중치의 합이 음수인 사이클이 없다고 가정 음의 가중치를 갖는 간선이 없다고 가정 다익스트라 알고리즘 거리 d[v] 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이 출발점에서 시작하여 거리 d[..

두 문자열 X와 Y사이의 편집 거리 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도 X = x1x2x3 ... xn, Y = y1y2 ... ym 문자열 X를 Y로 변환하는 데 필요한 전체 편집 연산에 대한 최소 비용 특정 위치에 새 문자를 삽입하는 연산 -> 삽입 비용 특정 위치의 문자를 삭제하는 연산 -> 삭제 비용 특정 위치의 문자를 다른 문자로 변경하는 연산 -> 변경 비용 최적성의 원리 X와 Y사이의 편집거리는 이들의 부분 문자열 사이의 편집 거리를 포함 Xi = x1x2 ... xi와 Yi = y1y2 ... yj 사이의 편집 거리 성능 삭제할 때 성능: O(n) 삽입할 때 성능: O(n) 변경할 때 성능: O(nm) P(i, j) E(i, j)로 선택되는 최소값이 어떤 연산으로 결정되는..