CS17 [알고리즘] 최소편집거리 알고리즘 edit distance, Levenshtien distance - 동적프로그래밍을 사용한다. - 서로 다른 문자열 str1과 str2이 같아지기 위해 몇 번의 과정을 거쳐야 하는지 이다. (두 문자열 사이 유사도 측정) - 과정에서 할 수 있는 동작은 insert, delete, replace 아래 3가지이다. 예를 들어 abcdeg를 azcde로 바꾼다면 1. 문자 지우기 : g를 지운다. 2. 문자 삽입 3. 문자 바꿔치기(replace): b를 z로 바꾼다. 가 될 수 있다. 접근방법: 이차원 배열을 사용한다. dp[i][j] dp[i][j]가 의미하는 바는 str1.substr(0,i)와 str2.substr(0,j)사이의 거리를 의미한다. dp[0][0]은 공문자열 사이에서 비교하는 것이기 때문에 거리가 0이다. dp[0][i]는 공문자열과 str.subs.. 2020. 10. 28. [알고리즘] Floyd's tortoise and hare 플로이드의 토끼와 거북이라는 귀여운 이름을 지닌 알고리즘이다. 다른 이름으론 플로이드의 순환 찾기 알고리즘으로 cycle detection에 사용된다. en.wikipedia.org/wiki/Cycle_detection Cycle detection - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search In computer science, cycle detection or cycle finding is the algorithmic problem of finding a cycle in a sequence of iterated function values. For any function f that maps a f.. 2020. 10. 20. [알고리즘] Tree Traversal - Depth First Traversal Depth First Traversal로 진행되는 트리 순회는 - preorder(root-> left -> right) - inorder(left->root->right) - postorder(left->right->root) 가 존재한다. www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/ Tree Traversals (Inorder, Preorder and Postorder) - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programmin.. 2020. 10. 4. [알고리즘] Prefix Sum 구간 합/누적 합 알고리즘 prefix sum이란 구간 합을 의미한다. 예를 들어, int arr[5] = {10,20,30,40,50}; prefix sum은 prefix[i] = prefix[i-1] + arr[i]일 것이다. int prefix[5]; prefix[0] = arr[0]; for(int i=1; i 2020. 10. 1. 이전 1 2 3 4 5 다음
