목록2차원배열_DP (1)

국문과 유목민

[DP] 편집거리

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 30분 + a 1. 문제 설명 - 2개의 string이 주어질 때 1번째 string을 2번째 string으로 바꾸기 위해서 '삽입, 삭제, 교체'등의 연산을 수행할 수 있다. 이때, 최소한의 연산을 수행했을 때의 값은? 2. 접근 방식 - 2차원 배열의 DP를 활용해서 문제를 풀면된다. - 두 문자가 같은 경우 : dp[i][j] = dp[i-1][j-1] - 두 문자가 다른 경우: dp[i][j] = 1+ min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] (삽입, 삭제, 교체 순) 3. 코드 ## 최소편집거리 계산을 위..
알고리즘_코딩테스트/이것이 코딩테스트다 2021. 12. 21. 23:59
이전 Prev 1 Next 다음