최소 편집 거리

영상 연습에서 최소 편집 거리를 사용해 두 문자열의 유사도를 판단하는 방법을 보셨죠. 다시 정리하면, 최소 편집 거리는 문자열 A에서 문자열 B로 가기 위해 필요한 최소 단계 수를 말하며, 사용할 수 있는 연산은 다음과 같습니다:

• 새 문자의 삽입
• 기존 문자의 삭제
• 기존 문자의 치환
• 연속된 두 기존 문자의 전치(자리 바꿈)

                    'sign'에서 'sing'까지의 최소 편집 거리는 얼마인가요? 또한 어떤 연산으로 도달할 수 있나요?