[알고리즘] DP - 스트링 편집 거리(문자열 유사도 측정)
스트링 편집 거리(string edit distance) 알고리즘이란 두 문자열의 유사도를 측정하기 위해 사용되는 알고리즘으로 Levenshtein distance(LD)라고도 합니다. 스트링 편집 거리 알고리즘은 논문, 보고서 등의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용되어지는데요. 두 문자열의 유사도는 S: 원래 스트링 T: 비교 스트링이라 했을 때 S -> T로 변환하는데 필요한 삽입, 삭제, 대치 연산의 최소 비용(최소 편집 횟수)을 구함으로써 판단합니다. (비용이 작게 나올수록 유사도가 큼) 만약 GUMBO라는 단어와 GAMBOL이라는 단어의 편집 거리를 구해보면, U -> A로 대치 (비용 +1), 맨 마지막에 L 추가 (비용 +1)로 편집 거리는 2가 되게 됩니다. (삽입, ..
파이썬 문자열 관련 메소드 정리
안녕하세요! 오늘은 문자열과 관련된 함수를 정리해 보려 합니다. 파이썬에서 문자열은 리스트와 마찬가지로 인덱싱 및 슬라이싱이 가능합니다. (파이썬은 다른 언어에 비해 문자열 처리가 상당히 편리한거 같아요.) # 인덱싱 & 슬라이싱 a = "Hello World!!" print(a[0], a[-1], a[7:11]) # 결과: H ! orld ● join() -문자열 삽입 # 문자열 삽입(join) join_str = ",".join('abcdef') print(join_str) # 결과: a,b,c,d,e,f ● strip() - 공백 지우기 # 왼쪽 공백 지우기(lstrip) test = " Hello World!! " print(test.lstrip()) # Hello World!! # 오른쪽 공백 ..