DP 활용 편집 거리 문제 삽입 ,삭제 ,대체 연산을 사용하여 스트링(문자열) S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수 strong -> stone __ DP의 일반항, E[i,j] = S의 처음 i개 문자를 T의 처음 j개 문자로 바꾸는데 필요한 편집 거리 stro -> sto로 바꾸기 위한 편집거리는 E[4,3]이다. 매순간 삽입, 대체, 삭제 총 3가지 연산의 경우의 수가 있다. ![](https://velog.velcdn.com

분할정복 주어진 문제의 입력을 분할해 문제를 해결하는 기법 > 예시 : 아주 많은 동전 더미 속에 1개의 가짜 동전이 섞여 있다. 이 가짜 동전은 매우 정교하게 만들어져 누구도 눈으로 가짜인지를 식별할 수 는 없지만, 무게가 정상적인 동전보다 약간 가볍다. 1개의 양팔 저울만을 사용해 이 가짜 동전을 최소한의 저울질로 찾아낼 수 있는 방법은 무엇인가? Solution1 : 매 시행마다 양팔 저울에 동전 한개씩 올려서 비교한다. 매우 비효율적이다 Solution2 : 매 시행마다 양팔 저울에 두개의 그룹으로 나눈 동전 더미를 올려서 비교한다. 동전 더미가 2의 배수라면 매 시행마다 두 그룹으로 나눌 수 있지만, 2의 배수가 아니라면 어느 순간에 홀수개가 되기 때문에 구현이 어렵다. Solution3 : 두개의 그룹으로 나누는 것이 아닌, 저울에 올라가지 않는 동전더미 그룹을 하나 더 만들어 총 세개의 그룹으로 나눈다. 매 시행마다 2/3의 동전 더미를 배제시