one Book a Day

LCS는 실상 냅색이랑 다를바가 없는 것 같다. 하지만 매우 중요한 개념. import sys input = sys.stdin.readline s1, s2, s3 = (input().rstrip() for _ in range(3)) n1, n2, n3 = len(s1), len(s2), len(s3) dp = [[[0 for _ in range(n1+1)] for _ in range(n2+1)] for _ in range(n3+1)] for i in range(n1): for j in range(n2): for k in range(n3): if s1[i] == s2[j] == s3[k]: dp[k+1][j+1][i+1] = dp[k][j][i] + 1 else: dp[k+1][j+1][i+1] = max..

편집거리 알고리즘 두 문자열의 유사도를 판단하는 알고리즘 유사도란? 어떤 문자열을 삽입, 삭제, 변경을 몇 번 해서 동일하게 바꿀 수 있는지의 최솟값. LCS와 같이 2차원 배열을 통해 문자열을 하나씩 비교. 최초는 공집합과 비교해 문자열 길이만큼 1씩 카운트를 준다(공집합에서 그 문자열이 되려면 열마나 삽입되어야 하는가?) 두 문자를 비교해 추가, 삭제, 변경의 소요마다 1씩 카운트. A[i]==B[j]일 때 편집거리 D(i,j) = D(i-1,j-1) 같은 문자가 나왔을 때는 대각선 왼쪽 위의 값을 가져온다. A[i]!=B[j] 면 D(i,j) = min(D(i-1,j),D(i,j-1),D(i-1,j-1)) + 1 즉 수정, 삽입, 삭제를 한 편집거리중 최소값을 가져온다. def editDistanc..