방향, 무방향 그래프에 관계없이 각 간선에 가중치(weight) 혹은 비용(cost)이 할당된 그래프
3. 용어
인접 정점 or 인접 노드 : 간선에 의해 연결된 정점
차수(degree) : 정점에 연결된 다른 정점의 개수
진입 차수(in-degree) : 방향 그래프에서 외부 노드에서 들어오는 간선의 수
진출 차수(out-degree) : 방향 그래프에서 외부 노드로 나가는 간선의 수
연결 그래프(connected Graph)
무방향 그래프에서 두 노드 사이를 연결하는 경로(path)가 존재할 때 두 정점은 서로 연결되어 있다고 한다.
그래프 안의 모든 정점이 연결되어 있을때 연결된 그래프라고 한다
연결 요소
{a,b,c,d}, {e,f}, {g,h,i}로 3개이다.
2. 그래프의 표현
1. 인접 행렬
인접 행렬 (무방향 그래프)
두 정점 사이에 간선이 있을경우 1, 없을 경우 0으로 표현한다.
가중치 그래프의 경우 0,1 대신 가중치로 표현한다.
무방향 그래프의 경우 자기 자신을 기준으로 대칭이다. (A, B) == (B, A)
방향 그래프의 경우 비대칭이다.
저장공간 : O(n^2)
어떤 노드 v에 인접한 모든 노드를 찾을 때 걸리는 시간 : O(n)
어떤 간선 (u,v)가 존재하는지 검사할때 걸리는 시간 : O(1)
간단한 구현 코드 (무방향 그래프)
public class Graph {
int[][] adjMatrix;
int vertexCount;
public Graph(int count) {
vertexCount = count;
adjMatrix = new int[vertexCount][vertexCount];
}
public void addEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1;
}
public void removeEdge(int u, int v) {
adjMatrix[u][v] = 0;
adjMatrix[v][u] = 0;
}
public List<Integer> findAdjVertex(int u) {
ArrayList<Integer> adjVertexList = new ArrayList<>();
for(int i = 0; i<adjMatrix.length; i++) {
if(adjMatrix[u][i] == 1) {
adjVertexList.add(i);
}
}
return adjVertexList;
}
public boolean isEdge(int u, int v) {
return adjMatrix[u][v] == 1;
}
}
2. 인접 리스트
인접 리스트 (무방향 그래프)
정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 리스트
두 정점 사이에 간선이 있을 경우 리스트에 추가한다 (순서는 상관없다)
저장 공간 : O(n+m)
n은 정점개수, m은 간선 개수이다.
무방향 그래프의 경우 2m, 방향 그래프의 경우 m이지만, Big - O 표기법에서는 O(n+m)이다.
어떤 노드 v에 인접한 모든 노드를 찾을 때 걸리는 시간 : O(degree(v))
v에 해당하는 리스트의 길이이다.
어떤 간선 (u,v)가 존재하는지 검사할 때 걸리는 시간 : O(degree(u))
u에 대한 연결 리스트를 돌면서 v가 있는지 확인한다.
간단한 구현코드 (무방향 그래프)
public class Graph {
List<Integer>[] adjList;
int vertexCount;
public Graph(int count) {
vertexCount = count;
adjList = new List[vertexCount];
for(int i = 0; i<vertexCount; i++) {
adjList[i] = new ArrayList<>();
}
}
public addEdge(int u, int v) {
adjList[u].add(v);
adjList[v].add(u);
}
public removeEdge(int u, int v) {
adjList[u].remove(adjList[u].indexOf(v));
adjList[v].remove(adjList[v].indexOf(u));
}
public List<Integer> findAdjVertex(int u) {
return adjList[u];
}
public boolean isEdge(int u, int v) {
for(int i = 0; i < adjList[u].size(); i++) {
if(adjList[u].get(i) == v) {
return true;
}
}
return false;
}
}
직관적으로 봐도 "나는 너를 좋아해" 와 "너는 나 좋아하니?"와 유사하고 "오늘 집에 갈거야" 와는 유사하지 않다는 걸 알 수 있다.
우리는 인간이니까 직관적으로 두 문자열이 비슷한지 전혀 다른지 판단할 수 있지만 기계는 직관적으로 판단 할 수 없다.
두 문자열의 유사도를 어떻게 판단할 수 있을까? Hamming Distance, Smith-Waterman, Sørensen–Dice coefficient 등 있지만 지금은 가장 간단한 Levenshtein Distance을 알아볼 것이다.(사실 문제 풀다가 나와서 정리하는 것)
2. 레벤슈타인 거리(Levenshtein Distance)
레벤슈타인 거리 알고리즘은 두 문자열이 같아지려면 몇번의 문자 조작(삽입, 삭제, 변경)이 필요한지 구하는 것이다.
레벤슈타인 거리 점화식
점화식만 보면 어려우니까 예시로 표현해보자.
두 문자열을 비교하면 문자 조작 비용은 총 6이다.
3. 알고리즘
위에서 말한 것 처럼 직관적으로 비용이 6인것을 알 수 있는데, 이를 알고리즘으로 어떻게 구현하는지 알아보자. LCS와 매우 유사하다.
처음 비교 대상은 공집합과 공집합이다. 둘 다 같은 문자열이기 때문에 비용은 0이다. 그 다음은 공집합과 "나" 이다. 공집합이 "나"가 되려면 비용이 1이다. 그 다음은 공집합과 "나는"이다. 마찬가지로 비용이 2가든다. 계속 진행하면 위와 같이 표가 완성된다.
이제 "너" 와 공집합 - "나" - "나는" - "나는 "... - "나는 너를 좋아해!"를 비교해보자.
"너"와 공집합을 보자. '너'가 {}이 되려면 문자를 삭제해야 한다. 그러므로 비용 1
"너"와 "나"를 보자. '너'와 '나'는 서로 다르기 때문에 교체해야 한다. 그러므로 비용 1
"너"와 "나는"을 보자. 길이가 다르기 때문에 추가해야 하고, 교체해야 한다. 그러므로 비용 2
"너"와 "나는 "을 보자. 역시 길이가 다르기 때문에 2개 추가해야 하고, 교체해야 한다. 그러므로 비용 3
"너"와 "나는 너"를 보자. 길이가 다르기 때문에 문자 3개를 추가해야 하지만, '너'는 서로 같기 때문에 그대로 둔다. 그러므로 비용 3
이런식으로 "나는 너를 좋아해!"까지 표를 완성하면 위와 같이 된다.
한번만 더 해보자. "너는"과 공집합 - "나" - "나는" - "나는 " - ... - "나는 너를 좋아해!"를 비교해보자
"너는"과 공집합을 비교해보자. "너는"이 {}이 되려면 문자 두개를 삭제해야 한다. 그러므로 비용 2
"너는"과 "나"를 비교해보자. 문자 한개 삭제와 교체가 필요하다. 그러므로 비용 2
"너는"과 "나는"을 비교해보자. '는'은 서로 같고, '너'와 '나'는 다르기 때문에 교체가 필요하다. 그러므로 비용 1
"너는"과 "나는 "을 비교해보자. 추가, 교체가 필요하다. 그러므로 비용 2
이런식으로 표를 완성하면 다음과 같이 된다.
쉽게 정리하면
글자가 서로 동일하면 대각선 값을 가져온다
변경이 필요하면 대각선 값에서 + 1을 한다.
삽입이 필요하면 위의 값에서 +1을 한다.
삭제가 필요하면 왼쪽 값에서 +1을 한다.
1~4의 경우에서 최소값을 가져온다.
4. 코드
public class Levenshtein {
public static int getDistance(String a, String b) {
int[][] table = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i <= a.length(); i++) {
table[i][0] = i;
}
for (int j = 1; j <= b.length(); j++) {
table[0][j] = j;
}
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= b.length(); j++) {
int insert = table[i - 1][j] + 1;
int delete = table[i][j - 1] + 1;
int replace = (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1) + table[i - 1][j - 1];
}
}
return table[a.length()][b.length()];
}
}
vs 
