'알고리즘' 태그의 글 목록

[알고리즘] 스트링 편집 거리

Computer Science/Algorithm 2021. 12. 14. 19:19

스트링 편집 거리(string edit distance) 두 스트링의 유사도를 측정하기 위해 사용 Levenshtein distance(LD)라고도 함 원래 스트링을 S, 목표 스트링을 T S를 T로 변환하는 데 필요한 삽입, 삭제, 대치 연산의 최소 비용 편집 거리가 커질수록, 두 스트링의 유사도는 낮아지게 됨 논문이나 보고서의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용됨 동적 계획법의 적용 스트링 편집 거리 예시를 들어 설명하겠습니다. S = GUMBO T = GAMBOL U -> A 로 교체 L 을 추가 따라서, GUMBO를 GAMBOL로 변경하는 최소 편집 거리는 2임을 알 수 있습니다. 스트링 편집 거리를 구하기 위해선, 간단히 표로 작성하여 구할 수 있습니다. 1. 초기 테이블을 ..

01. 자료구조와 알고리즘

Computer Science/Data Structure 2021. 3. 21. 14:02

- 학습목표 자료구조와 알고리즘의 개념을 이해한다 추상 자료형 도입의 필요를 이해한다 시간 복잡도의 개념을 이해한다 빅오 표기법에 의한 알고리즘 분석 기법을 이해한다 자료구조 표기법을 이해한다 1.1 자료구조와 알고리즘 자료구조란? - 사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다. 이러한 구조들을 자료구조라 한다. - 예를 들면, 해야할 일들을 중요도에 따른 내용들을 컴퓨터가 이해하려면 순차적으로 진행하는 List를 사용해야한다. 일상생활 자료구조 그릇, 연탄 스택 마트 계산대의 줄 큐 버킷 리스트 리스트 영어 사전 사전 지도 그래프 컴퓨터의 디렉토리 구조 트리 알고리즘이란? - 컴퓨터로 문제를 풀기 위한 단계적인 절차 - 특정한 일..

[Python] 유클리드 호제법(Euclidean Algorithm)

Algorithm/Basic 2021. 3. 19. 18:46

1. 정의 - 두 수의 최대공약수를 구하는 알고리즘 2. 방법 - 2개의 자연수 a, b(a > b) 에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대 공약수는 b와 r의 최대공약수와 같음 -> 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수가 된다. 3. 비교 유클리드 호제법이 아닌 다른 방법으로 코드를 작성한 후, 시간을 비교해보았습니다. 2초 가량 차이가 난다. 결론: 최대공약수를 구할 땐 유클리드 호제법을 이용하자

ABOUT ME

hye0.log hye0.log

티스토리툴바