PY-L3-046 / 동적 계획
편집 거리
중급문제
문자열 a를 b로 바꾸는 최소 편집 횟수를 반환하세요. 한 번에 문자 삽입·삭제·치환 하나를 할 수 있습니다.
solve(*args) 함수에서 값을 반환하세요. print 출력은 정답 판정에 사용하지 않습니다.
입출력 예시
예제 1
입력: ["kitten","sitting"] 반환: 3
예제 2
입력: ["","abc"] 반환: 3
힌트
접두어끼리의 최소 비용을 표로 정의하세요.
해설·정답 보기
삽입·삭제·치환 후보 중 최소를 택합니다. 직전 행만 보존해 메모리를 줄입니다.
def solve(a, b):
prev = list(range(len(b) + 1))
for i, x in enumerate(a, 1):
row = [i]
for j, y in enumerate(b, 1):
row.append(min(row[-1] + 1, prev[j] + 1, prev[j-1] + (x != y)))
prev = row
return prev[-1]solution.py결과 비교
코드는 이 브라우저에 자동 저장돼요.
풀이 결과
코드를 작성하고 채점하기를 눌러보세요.
학습용으로 제공된 조건을 확인해요. 알고리즘 사용 방식·설계 의도는 해설과 함께 비교해보세요.