설명최소 편집 거리 알고리즘은 두 문자열이 같아지기 위해 수행해야 하는 최소 ‘연산’ 횟수이다. 연산으로는 추가(Add), 수정(Edit), 삭제(Delete)가 있다.연산추가(Add)a = “xz”, b = “xyz”라고 할 때, a의 첫 번째 문자 다음에 y를 삽입하여 문자열을 같게 만들 수 있다.수정(Edit)a = “xyz”, b = “xwz”라고 할 때, a의 두 번째 문자를 y에서 w로 수정하면 문자열을 같게 만들 수 있다.삭제(Delete)a = “xyz”, b = “xy”라고 할 때, z의 마지막 문자를 삭제하면 문자열을 같게 만들 수 있다.예시“kitten”과 “sitting”의 최소 편집 거리는 3이다.k를 s로 수정한다.e를 i로 수정한다.g를 추가한다.구현최소 편집 거리 알고리즘은 ..

설명플로이드-워셜 알고리즘은 가능한 모든 경로의 최단 경로를 구할 때 사용한다. 다익스트라 알고리즘은 간선의 가중치가 음수인 경우 사용하지 못했지만, 플로이드-워셜 알고리즘은 음의 가중치를 가지는 간선에도 적용할 수 있다.코드arr[i][j] = 2; // i -> j 간선의 가중치는 2노드 간 연결 관계를 인접 행렬 형태로 입력받는다. dist[i][j] = 6; // i -> j로의 최단 거리 가중치는 6노드 간 최단 거리를 저장하는 배열 dist를 선언한다.for(int i = 1; i 입력받은 arr 배열을 바탕으로 dist 배열을 초기화한다. for(int k = 1; k 삼중 for문을 통해 최단 거리를 초기화하는데, 중간 노드 번호를 가장 바깥의 for문에서 초기화한다. 가장 바깥의 for..

설명트리의 정의는 순환이 존재하지 않은 무향그래프이다. 트리의 종류는 여러 종류가 있으며, 그 중 스패닝 트리는 그래프 내의 모든 정점을 포함하면서 사이클이 존재하지 않는 트리를 말한다. 스패닝 트리를 신장 트리라고 부르기도 한다. 스패닝 트리는 그래프의 최소 연결 부분 그래프이다. 최소 연결이란 정점을 잇는 간선의 수가 가장 적다는 의미이다. 따라서 정점의 개수를 n개라고 할 때, 스패닝 트리가 가질 수 있는 최소 간선의 수는 n - 1개이다.  간선의 가중치가 존재한다고 할 때, 사용된 간선들의 가중치 합이 최소인 스패닝 트리를 최소 스패닝 트리(Minimun Spanning Tree, MST)라고 한다. 즉, MST는 간선의 가중치의 합이 최소가 되어야 하며 정점의 수가 n개일 때 간선의 수는 n ..

설명다익스트라 알고리즘은 시작 노드에서 모든 노드까지의 최단 거리를 구하는 알고리즘이다. 가중치가 음수인 경우에는 사용할 수 없다. 즉, 모든 가중치가 0 또는 양수여야 가능하다.코드vector> nodes[MAX_SIZE];// MAX_SIZE: 노드의 수nodes 배열은 인접 노드 및 가중치에 대해 저장하는 배열이다. int dist[MAX_SIZE];시작 노드와 각 노드 간 최단 거리를 저장하는 배열이다. 시작 노드의 경우 dist의 값을 0, 나머지 노드들은 INF로 초기화한다. priority_queue, vector>, greater>> pq;// 또는 greater를 사용하지 않고 가중치에 - 부호를 붙여도 된다.첫 번째 요소는 가중치, 두 번째 요소는 현재 노드 번호가 들어가야 한다. 즉,..

설명유클리드 호제법 은 두 양의 정수의 최대공약수를 구하는 방법이다.공식은 다음과 같다.두 양의 정수 $a,\ b\ (a>b)$에 대하여 $a$를 $b$로 나눈 나머지를 $r$이라고 하자. 이 때 $a,\ b$의 최대공약수는 $b,\ r$의 최대공약수와 같다.위 과정을 $r$이 0이 될 때까지 반복하면 두 정수의 최대공약수를 구할 수 있다.의사코드나머지연산의 결과를 저장할 변수 c를 선언한다.b가 0이 될 때까지 다음 연산을 반복한다.c는 a를 b로 나눈 나머지이다.a를 b, b를 c로 설정한다.a가 최대공약수이다.코드int gcd(int a, int b) { int c; while (b) { c = a % b; a = b; b = c; } return a;}시간복잡도두 수 $a, \ b$에 대하여..

설명CCW는 Counter ClockWise의 약자로, 반시계 방향을 의미한다. CCW 알고리즘은 세 점이 주어졌을 때, 이들이 이루는 방향을 판별한다.  먼저 세 점 $A, B, C$를 두 개의 벡터 $\textbf{a}, \textbf{b}$로 나타내고, 두 벡터의 외적 $\textbf{a}\times \textbf{b}$를 계산한다. $\theta$를 두 벡터의 사잇각이라고 할 때,  $\textbf{a}\times\textbf{b}=\left\|\textbf{a}\right\|\left\|\textbf{b}\right\|\mathrm{sin}\theta$  이다.즉, 외적의 크기가 양수라면 두 벡터의 사잇각이 $0^{\circ}$~$180^{\circ}$이고, 이는 두 벡터가 반시계 방향이라는 것..