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회의 편집..
Chap4-4. 부분 배낭 문제
배낭 문제란? 배경 = 물건 n개의 집합 S = {1, 2, 3, 4, ..., n}이 있고 물건 무게 W = {W1, W2, W3..., Wn}, 물건을 팔았을 때의 가치(이윤) P = {P1, P2, P3, ..., Pn }가 있다고 하자. 조건 = W은 물건 무게 이므로 Wi > 0이어야 한다. P도 Pi > 0이어야 한다. 자신이 배낭에 물건을 가지고 가서 시장에서 판다고 가정하자 배낭에 넣을 수 있는 무게는 제한되었다. 최대 무게를 M이라고 하자 1 ~ n까지의 Wi * Xi ≤ M 이면서 (x= 물건의 개수) 1 ~ n 까지의 Pi * Xi 를 최대화하는 방향을 찾아야 한다. • n개의 물건이 각각 1개씩 있고, • 각 물건은 무게와 가치를 가지고 있으며, • 배낭이 한정된 무게의 물건들을 담..