본문 바로가기

DP

 (3)
Chap 5-3. 편집거리 (Edit Distance) [편집거리 (Edit Distance)] = 삽입 (insert), 삭제 (delete), 대체 (substitute) 연산을 사용하여 스트링(문자열) S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수 즉, 3개의 연산(삽입, 삭제, 대체)을 통해 다른 문자열로 변환이 가능하다. [예시 strong -> stone] strong을 stone으로 바꿔보자 2가지 방법이 가능하다. 방법 1 ) 순서대로 s, t는 그대로 두고 o를 삽입하고 r, o를 삭제한다. n은 그대로 두고 g를 e로 바꾼다. ⇒ 총 4회의 편집 연산을 했다. 방법 2) ‘s’와 ‘t’는 그대로 사용한 후, ‘r’을 삭제하고, ‘o’와 ‘n’을 그대로 사용한 후, ‘g’를 ‘e’로 대체하여, 총 2회의 편집..
Chap 5-2.연속 행렬 곱셈 연속 행렬 곱셈(Chained Matrix Multiplication) 문제 = 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제 행렬 곱셈 (1) 두 행렬의 곱셈이란? 두 행렬 A, B가 있다. A = 10 x 20 B = 20 x 5 라면 총 곱셈의 횟수 = 10 * 20 * 5 = 1000이다. (2) 3개의 행렬 곱셈 A = 10 x 20 B = 20 x 5 C = 5 x 15 행렬의 곱셈은 결합법칙 성립하므로 (A* B) * C , A * ( B * C) 이 둘 다 성립한다. 하지만 둘의 결과값는 같지만 곱셈의 횟수는 전자가 더 적다.(과정이 다르다) [ 행렬 곱셈의 주의점 ] 주어진 행렬의 순서를 지켜서 “반드시 이웃하는 행렬끼리” 곱해야 한다. 동적 알고리즘 적용 (1) ..
Chap 5. 동적 계획 알고리즘 Dynamic Programming(DP) 알고리즘 -입력 크기가 작은 부분 문제들을 해결한 후에 -그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결해어 -최종적으로 원래 주어진 입력의 문제를 해결 [문제] n개의 원소를 갖는 문제 같은 형태로 문제를 해결해나가지만 n개보다 작은 값으로 (작은 문제로 ) 만들어서 푸는 방법 (1) 최적의 하위구조 특성 k < n 인 k개의 원소를 갖는 문제를 정의하고 문제를 풀었더니 그것이 최적의 풀이법이고 점점점 작은 문제들을 결합해서 최종 풀이법이 완성되어지는 형태의 특성을 갖는 문제를 “최적의 하위구조 특성을 갖는 문제”라고 부른다. 예시) 두 도시를 자동차로 갈 수 있는 최단 경로 A도시 B도시 C도시가 있는데 A에서 C로 가기 위해서는 A-B의 최단 경로를..

티스토리툴바