2022.11.10

Assignment

두 개의 문자열이 주어지고, 두 문자열의 유사도를 출력하는 프로그램을 작성하라.

Progress

문자열의 유사도를 계산하는 프로그램을 작성해야 한다.

Sol1 - 모든 문자 비교

가장 먼저 모든 글자를 비교해서 두 문자열 간 공통으로 들어간 문자의 개수를 구했다.
그리고 그 개수를 전체 문자열의 길이로 나누었다.

python

def sliceString(sample1, sample2):
	cnt = 0 #공통 문자 counting
    l = [] #공통 문자
    sample1 = sample1.replace(' ', '') #공백 제거
    sample2 = sample2.replace(' ', '')
    for s1 in sample1: #이중 for문으로 모든 문자 비교
    	for s2 in sample2:
        	if s1 == s2: #문자가 동일한 경우
            	cnt += 1 #개수 counting
                l.append(s1) #리스트에 공통 문자 추가
    
    return cnt/len(sample1), l

print(sliceString("김철수 학생", "착한 김철수"))

Sol2 - Edit Distance Algorithm

Edit Distance(편집 거리) 알고리즘을 활용했다.
편집 거리 알고리즘이란, 두 개의 문자열이 같아지기 위한 수정 횟수를 구하는 알고리즘이다.

Edit Distance Algorithm
두 문자열 A, B가 있다. (A = "착한 선우철수", B = "선구철수 학생")
B를 A(기준)와 비교했을 때 A와 얼마나 유사한지를 수정 횟수를 통해 구한다.
여기서 수정 횟수는 세 가지 연산을 말한다.
1. 삭제 - "학생" 삭제
2. 추가 - "착한" 추가
3. 수정 - "우" -> "구" 수정
https://velog.io/@chaemin/Edit-Distance-편집-거리-알고리즘
https://velog.io/@chaemin/python-백준-20542-받아쓰기Edit-Distance-Algorithm

python

def editDistance(str1, str2):

    MN = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)]

    # 기준이 되는 문자열 row str1 길이 만큼 초기화
    for i in range(1, len(str1)+1):
        MN[i][0] = i
    
    # 비교 문자열 column str2 길이 만큼 초기화
    for j in range(1, len(str2)+1):
        MN[0][j] = j
    
    # edit distance
    for i in range(1, len(str1)+1):
        for j in range(1, len(str2)+1):
            if str1[i-1] == str2[j-1]:
                MN[i][j] = MN[i-1][j-1]
            else:
                MN[i][j] = min(MN[i-1][j-1],MN[i][j-1], MN[i-1][j])+1
    
    #for i in range(0, len(str1)+1):
    #   for j in range(0, len(str2)+1):
    #       print(MN[i][j], end=' ')
    #   print()
    
    return MN[len(str1)][len(str2)]

비교

둘 다 이중 for문을 돌아서 걸리는 시간이 같아 보인다.
그러나 edit distance는 테이블을 만드는 시간을 제외하고 유사도를 알 수 있는 수정 횟수, 즉 마지막 인덱스만을 출력하면 되므로 상대적으로 빠르다.
다만 다이나믹 프로그래밍 방식을 채택하고 있어, 메모리를 많이 사용한다는 단점이 있다.

이와 같이 메모리와 시간은 언제나 반비례한다.