tonirr

두 문자열 X와 Y사이의 편집 거리 두 문자열 사이의 근접성 또는 유사성을 판단하는 척도 X = x1x2x3 ... xn, Y = y1y2 ... ym 문자열 X를 Y로 변환하는 데 필요한 전체 편집 연산에 대한 최소 비용 특정 위치에 새 문자를 삽입하는 연산 -> 삽입 비용 특정 위치의 문자를 삭제하는 연산 -> 삭제 비용 특정 위치의 문자를 다른 문자로 변경하는 연산 -> 변경 비용 최적성의 원리 X와 Y사이의 편집거리는 이들의 부분 문자열 사이의 편집 거리를 포함 Xi = x1x2 ... xi와 Yi = y1y2 ... yj 사이의 편집 거리 성능 삭제할 때 성능: O(n) 삽입할 때 성능: O(n) 변경할 때 성능: O(nm) P(i, j) E(i, j)로 선택되는 최소값이 어떤 연산으로 결정되는..

최대점수 구하기(냅색 알고리즘) #include using namespace std; int main() { ios_base::sync_with_stdio(false); //freopen("input.txt", "rt", stdin); int n, m, s, t; cin >> n >> m; vector dy(m+1, 0); for(int i=0; i> s >> t; for(int j=m; j>=t; j--){ dy[j] = max(dy[j], dy[j-t]+s); } } cout

피자배달거리 #include #include #include /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; int x1, x2, y1, y2, ch[20], sum, dis, min_dis, m, min_res=2147000000; vector hs; vector pz; void DFS(int s, int L) { if(L==m) { sum=0; for(int i=0; isum) min_res=sum; } else { for(int i=s; i>n>>m; for(int i=1; ik; if(k==1) hs.push_back(make_p..

#include #include /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; int ch[100], n, sum=0, res=-2147000000; vector map[20]; vector T; vector P; void DFS(int L, int sum) { if(L==n+1) { if(sum>res){ res=sum; } } else { if(L+T[L]

원더랜드(Kruskal MST 알고리즘: Union&Find 활용) #include #include #include #include /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; int unf[1001]; struct Edge{ int v1; int v2; int val; Edge(int a, int b, int c){ v1=a; v2=b; val=c; } bool operator

미로탐색 #include /* run this program using the console pauser or add your own getch, system("pause") or input loop */ using namespace std; int map[30][30], n, m, ch[30][30], cnt=0; int dx[4]={-1, 0, 1, 0}; int dy[4]={0, 1, 0, -1}; void DFS(int x, int y){ int i, j, xx, yy; if(x==7 && y==7) { cnt++; return; } else { for(i=0; i

인접행렬(가중치 방향그래프) #include #include #include using namespace std; int map[21][21]; int main() { freopen("input.txt", "rt", stdin); int n, m, a, b, c, i, j; scanf("%d %d", &n, &m); for(i=1; i

깊이우선탐색은 루트 노드가 어디에 위치하는가에 따라서 세가지로 나뉘어 진다. 전위순회, 중위순회, 후위순회 전위순회 루트노드가 가장 먼저 나오는 방식 루트노드가 가장 먼저 나오고나서 왼쪽부터 노드들을 순회 중위순회 루트노드가 중간에 나오는 방식 노드들의 왼쪽부터 순회하여 루트노드가 중간에 나옴 후위순회 루트노드가 마지막에 나오는 방식 왼쪽노드 -> 오른쪽노드 -> 부모노드 순서로 순회 각각의 예제코드 아래는 트리를 구성하는 코드이다. #include using namespace std; void D(int v){ if(v>7) return; else { D(v*2); D(v*2+1); } } int main() { D(1); return 0; } 위 코드에서는 D라는 재귀함수를 계속적으로 호출하고 있지만..