mhkim4886   4년 전

LCS 비슷하게 해서 편집 거리를 구하는 dp 알고리즘으로 풀려고 합니다. (https://salepark.tistory.com/17)

이렇게 하면 O(nm) 시간에 dp 테이블을 채우고 추적하면 될 거 같은데, dp 테이블 크기가 너무 커서 메모리에 저장할 수 없다는 문제가 생겼네요. 편집 스크립트의 길이만 필요하다면 dp 테이블을 두 줄만 들고있는 방식으로 풀 수 있을 텐데, 이 케이스는 역추적까지 해야 해서 dp 테이블을 다 갖고 있어야 해서..

어떻게 하면 좋을까요?

댓글을 작성하려면 로그인해야 합니다.