tonirr

두 문자열 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)로 선택되는 최소값이 어떤 연산으로 결정되는..

동적프로그래밍 동적프로그래밍 방법의 원리 문제의 크기가 작은 소문제에 대한 해를 저장해놓고, 이를 이용해서 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근방법 각각의 소문제는 원래의 문제와 동일하지만 입력의 크기만 줄어듦 입력의 크기가 아주작은 단순한 문제가 되면 쉽게 해를 구할 수 있고 이런 소문제의 해는 다시 사용될 수 있으므로 테이블에 저장 해당 소문제의 해가 필요할 때마다 테이블에서 결과를 바로 이용 동적 프로그래밍(동적 계획법) 해를 구축하는 테이블을 이용함 최적화 문제에 사용됨(최소값, 최대값 찾기) 분할 정복 방법 하향식 접근 방법 상위 레벨의 큰 문제를 순환적으로 부분배열로 분할하고 이들의 해를 결합해서 원래 문제의 해결하는 방법 분할된 작은 문제들은 서로 독립적 이진탐색, ..