편집 거리
📌문제두개의 문자열 A,B가 주어졌을 때 문자열 A를 편집하여 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 다음 세 연산 중 한번에 하나씩 선택하여 이용할 수 있다.1. 삽입: 특정한 위치에 하나의 문자를 삽입2. 삭제: 특정한 위치에 있는 하나의 문자를 삭제3. 교체: 특정한 위치에 있는 하나의 문자를 다른 문자로 교체 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하시오. 📌풀이최소 편집 거리를 담을 2차원 테이블1. 행과 열에 해당하는 문자가 서로 같다면, 왼쪽 위에 해당하는 수를 그대로 대입2. 행과 열에 해당하는 문자가 서로 다르다면, 왼쪽(삽입), 위쪽(삭제), 왼쪽 ..
코딩테스트
2024. 12. 21. 20:03