Merge Sort

• 원소 개수가 1개 또는 0개가 될 때까지 반으로 나눈뒤 반으로 나눈 원소들을 합쳐가는 과정에서 정렬하는 방식
• 정렬하려는 배열 크기만큼의 추가 배열이 필요함
• $O(nlogn)$으로 $O(n^2)$인 Selection, Insertion, Bubble Sort보다 훨씬 빠름
• Divide And Conquer 알고리즘

• 

동작

Merge가 동작하는 시점?을 하나의 Step으로 본다.

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

코드

public class Sort {
	
    public void mergeSort(int[] arr, int first, int last) {
    	if(first < last) {
        	int mid = (first + last) / 2;
            mergeSort(arr, first, mid);
            mergeSort(arr, mid + 1, last);
            merge(arr, first, mid, last);
        }
    }
    
    public void merge(int[] arr, int first, int mid, int last) {
    	int i = first;
        int j = mid + 1;
        int k = first;
        int[] copy = new int[arr.length];
        
        while(i <= mid && j <= last) {
        	if(arr[i] > arr[j]) {
            	copy[k++] = arr[j++];
            } else {
            	copy[k++] = arr[i++];
            }
        }
        
        if(i > mid) {
        	for(int l = j; j <= last; j++) {
            	copy[k++] = arr[l];
            }
        } else {
        	for(int l = i; i <= mid; i++) {
            	copy[k++] = arr[l];
            }
        }
        
        for(int l = first; l <= last; l++) {
        	arr[l] = copy[l];
        }
    }
    
}

왜 $O(nlogn)$일까?

Insertion Sort

• k번째 원소를 k-1번째 원소부터 첫번째 원소까지 비교하며 위치를 찾아 끼워넣는 방식
• O(n^2)인 정렬중에 빠른편에 속한다.

동작

Step1

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void insertionSort(int[] arr) {
    	for(int i = 1; i < arr.length; i++) {
            int target = arr[i];
            for(int j = i - 1; j >= 0 && arr[j] > target; j--) {
            	arr[j+1] = arr[j];
            }
            arr[j+1] = target;
        }
    }
}

Bubble Sort

• 첫번째와 두번째 원소를 비교하여 정렬, 두번째와 세번째 , ... , n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 첫번째와 두번째, ... , n-2번째와 n-1번째 ... 이를 반복하는 방식이다.
• Selection Sort와 마찬가지로 O(n^2)이다.

• 

동작

Step1

Step2 부터 j가 이동하면서 swap하지않고 그냥 지나가는 것은 생략한다.

Step2 

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = arr[index1];
    }
    
    public void bubbleSort(int[] arr) {
    	for(int i = arr.length - 1; i >= 0; i--) {
        	for(int j = 0; j < i; j++) {
            	if(arr[j] > arr[j+1]) {
                	swap(arr, j, j+1);
                }
            }
        }
    }
}

Selection Sort

• 처음 index부터 마지막 index까지의 이동하며 최대값을 찾은 후 저장하는 방식
• k-index에 들어갈 원소를 찾기위해서 k-1번 최대값을 찾는 비교를 해야하므로 O(n^2)이다.

• 

동작

Step1

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
	
	public void selectionSort(int[] arr) {
    	for(int i = arr.length-1; i >= 0; i--) {
        	int maxIndex = i;
            int j;
            for(j = 0; j < i; j++) {
            	if(arr[j] > arr[maxIndex]) {
                	maxIndex = j;
                }
            }
            swap(arr, i, maxIndex);
        }
    }
    
    
}

참고1 : 유튜브 (권오흠 교수, 2015 봄학기 알고리즘)

참고2 : (다양한 예제로 학습하는) 데이터 구조와 알고리즘 for java

1. 그래프 : G = (V, E)

1. 정의

• V : 정점(Vertex) 또는 노드(Node)들의 집합
• E : 간선,에지(Edge) 또는 링크(Link)라고 불리는 정점들의 쌍의 집합
• G = (V, E)

2. 종류

• 무방향(undirected) 그래프 vs 방향(directed) 그래프
  • 방향이 없는 그래프 vs 방향이 있는 그래프
  • (u, v) == (v, u) vs (u, v) != (v,u)
  • vs
• 가중치 그래프(Weight Graph)
• 방향, 무방향 그래프에 관계없이 각 간선에 가중치(weight) 혹은 비용(cost)이 할당된 그래프
  • 

3. 용어

• 인접 정점 or 인접 노드 : 간선에 의해 연결된 정점
• 차수(degree) : 정점에 연결된 다른 정점의 개수
  • 진입 차수(in-degree) : 방향 그래프에서 외부 노드에서 들어오는 간선의 수
  • 진출 차수(out-degree) : 방향 그래프에서 외부 노드로 나가는 간선의 수
• 연결 그래프(connected Graph)
  • 무방향 그래프에서 두 노드 사이를 연결하는 경로(path)가 존재할 때 두 정점은 서로 연결되어 있다고 한다.
  • 그래프 안의 모든 정점이 연결되어 있을때 연결된 그래프라고 한다
  • 연결 요소

  • 

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;
    }

}

1. 문장의 유사도

세 문자열을 보자

직관적으로 봐도 "나는 너를 좋아해" 와 "너는 나 좋아하니?"와 유사하고 "오늘 집에 갈거야" 와는 유사하지 않다는 걸 알 수 있다.

우리는 인간이니까 직관적으로 두 문자열이 비슷한지 전혀 다른지 판단할 수 있지만 기계는 직관적으로 판단 할 수 없다. 

두 문자열의 유사도를 어떻게 판단할 수 있을까? 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. 글자가 서로 동일하면 대각선 값을 가져온다
2. 변경이 필요하면 대각선 값에서 + 1을 한다.
3. 삽입이 필요하면 위의 값에서 +1을 한다.
4. 삭제가 필요하면 왼쪽 값에서 +1을 한다.
5. 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()];
  }
}

5. 예제

www.codewars.com/kata/5259510fc76e59579e0009d4/train/java

1. 개요 - LCS가 뭘까?

LCS(Longest Common Subsequence) 알고리즘은 공통부분 문자열 중 가장 길이가 긴 문자열을 찾는 알고리즘을 뜻한다.

여기서 Subsequnce와 Substring의 차이가 있는데 Substring은 연속된 부분 문자열이고, Subsequence는 연속되지 않는 부분 문자열이다.

같은 길이의 다른 해가 있을 수 있다.

막상 직접 만드려니 어렵네요;; 틀렸다면 댓글 부탁드립니다 ㅜ

2. LCS의 길이 구하기

LCS 알고리즘은 DP(Dynamic Programming)이므로 특정 범위까지의 LCS을 구하고 다음 범위의 LCS를 구할 때 이전에 구해 둔 값을 이용하여 문제를 해결한다.

점화식

점화식만 보면 이해가 잘 안 된다. 예시를 들어 설명하는 게 더 이해하기 쉬우니 예시를 들어보자.

문자열 "ABCBDAB"와 "ADCABA"를 표를 이용해서 비교해보자. 

1) 0부터

0을 추가하는 이유는 공통 부분이 없다면 LCS가 길이가 0이기 때문이다.

2) B와 비교 

표를 보는 방법은 열의 {A}와 행의 {A}, {AB}, {ABC}, {ABCB}.. 의 마지막 element를 비교하는 것이다.

점화식을 따라해보자.

• 우선 {A}와 {A}를 비교해보면 마지막 element는 "A"로 같다. 그러므로 두 문자열에서 "A"를 뺀 {}(empty)와, {}(empty)의 LCS길이인 0에 +1을 하여 표기한다. (점화식 2번 case)
• 그다음, {A}와 {AB}를 비교해 보자. 마지막 element는 "A"와 "B"로 다르다. 그러므로 {}(empty)와 {AB}의 LCS길이인 0과 {A}와 {A}의 LCS길이인 1중 더 큰 값인 1을 표기한다. (점화식 3번 case)
• 이번엔 {A}와 {ABC}를 비교해보자. 마지막 element는 "A"와 "C"로 다르다. 그러므로 {}(empty)와 {ABC}의 LCS길이인 0과 {A}와 {AB}의 LCS길이인 1중 더 큰 값인 1을 표기한다. (역시 점화식 3번 case)
• 계속 반복하면서 표기하다가 다시 {A}와 {ABCBDA}를 비교해보자. 마지막 element는 "A"로 같다. 그러면 두 문자열 마지막 element "A"가 없는 {}(empty)와 {ABCBD}의 LCS길이인 0에 +1을 하여 표기한다. (점화식 2번 case)

위에서 한 표기들을 DP측면에서 살펴보면

• {A}와 {A}의 LCS길이를 구하기 위해서 이전에 구해놓은 {}(empty)와 {}(empty)의 LCS길이인 0을 이용했다. 즉, 이전의 LCS길이값을 이용해서 현재 LCS길이값을 구할 수 있었다.
• {A}와 {AB}의 LCS길이는 공통부분이 "A"이기 때문에 1이다. 이것은 이전에 구해놓은 {}(empty)와 {AB}의 LCS길이, 그리고 {A}와 {A}의 LCS길이를 이용해서 구할 수 있었다. 

3) 몇 번 더 반복해보자

역시 점화식을 따라 해보자

• {ADCA}와 {ABCBDA}를 비교해보면, 마지막 element는 "A"로 같다. 그러므로 "A"가 없는 {ADC}와 {ABCBD}의 LCS길이인 2에 +1을 하여 표기한다 (점화식 2번 case)
• {ABCBDAB}와 {ADCABA}를 비교해보자. 마지막 element는 "B"와 "A"로 서로 다르다. 그러므로 {ABCBDAB}와 {ADCAB}의 LCS길이 4와 {ABCBDA}와 {ADCABA}의 LCS길이 4 중 더 큰 값을 표기한다. (점화식 3번 case)

이것도 DP관점에서 보면

• {ADCA}와 {ABCBDA}의 LCS길이를 구하기 위해 이전에 구해놓은 {ADC}와 {ABCBD}의 LCS길이를 이용한다.
• {ABCBDAB}와 {ADCABA}의 LCS길이를 구하기 위해 이전에 구해놓은 {ABCBDAB} 와 {ADCAB}, {ABCBDA}와 {ADCABA} LCS길이를 이용한다.

따라서 점화식을 해석하면

• 문자열 X나 문자열 Y의 index가 0일 경우 0
• 문자열의 마지막 element를 비교하여 같을 경우 왼쪽 위 대각선의 값 +1을 표기
• 문자열의 마지막 element를 비교하여 다를 경우 왼쪽 값과 위쪽 값 중 더 큰 값을 표기

코드로는 어떻게 구현할까?

package algorithm.lcs;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.jupiter.api.Test;

public class LongestCommonSubsequence {

  @Test
  public void testLcsLength() {
    assertThat(lcsLength("ADCABA", "ABCBDAB"), is(4));
  }

  public int lcsLength(String x, String y) {
    int maxLength = 0;

    x = "0" + x;
    y = "0" + y;
    int[][] lcsTable = new int[x.length()][y.length()];

    for (int i = 1; i < x.length(); i++) {
      for (int j = 1; j < y.length(); j++) {
        if (x.charAt(i) == y.charAt(j)) {
          lcsTable[i][j] = lcsTable[i - 1][j - 1] + 1;
          maxLength = lcsTable[i][j];
        } else {
          lcsTable[i][j] = Math.max(lcsTable[i][j - 1], lcsTable[i - 1][j]);
        }
      }
    }
    return maxLength;
  }
}

자바의 경우 int 배열을 선언하면 0으로 초기화되기 때문에 "0"에 해당하는 0 값을 따로 넣어주지 않았다.

3. LCS 구하기

LCS 길이를 표기해 나갔던 표를 역추적하여 LCS를 구할 수 있다.

LCS 길이 점화식을 다시 생각해보면

문자열 마지막 element가 같을 경우 왼쪽 위 대각선 값 + 1

문자열 마지막 element가 다를 경우 왼쪽이나 위쪽 값 중 더 큰 값

이를 이용해서 표를 역추적하면 실제 LCS를 구할 수 있다.

역시 이해가 잘 안 되니까 표를 보자.

우선 표의 끝(오른쪽 아래)에서 시작하자. ({6,8}("A", "B"))

시작 위치에서 위쪽, 대각선(왼쪽 위), 왼쪽 값을 비교하면 대각선 값 보다 크고 왼쪽, 위쪽 값과 같다. 이때 왼쪽 or 위쪽으로 이동할 수 있는데 위쪽을 선택

• 단, 왼쪽이나 위쪽을 선택했을 때, 선택한 방향으로만 이동해야 한다.

이동한 위치 ({5,8} ("B", "B"))에서 element 값이 같다. 그리고 왼쪽, 위쪽, 대각선 값보다 크다. 그러므로 대각선으로 이동한다. 이때 현재 위치 값 "B"를 기록해둔다.

• Output : B

이동한 위치 ({4,7}, ("A", "A"))에서 element 값이 "A"로 같다. 역시 왼쪽, 위쪽, 대각선 값보다 크기 때문에 "A"를 기록하고 대각선으로 이동한다.

• Output : AB

이동한 위치 ({3,6}, ("C", "D")}에서 element 값이 다르다. 그리고 대각선 값보다는 크고, 왼쪽 위쪽 값과는 같다. 처음에 이럴 경우 위쪽으로 이동하는 것을 선택했기 때문에 위쪽으로 이동한다.

이동한 위치 ({2,6}, ("D", "D")}에서 element 값이 "D"로 같다. 역시 왼쪽, 위쪽, 대각선 값보다 크기 때문에 "D"를 기록하고 대각선으로 이동한다.

• Output : DAB

이동한 위치 ({1,5}, ("A", "B")}에서 element 값이 다르다. 대각선과 위쪽 값보다는 크고, 왼쪽 값과는 같다. 그러므로 왼쪽으로 이동한다.

왼쪽으로 계속 이동하다가 ({1,1}, ("A", "A"))에서 element 값이 "A"로 같다. "A"를 기록하고 대각선으로 이동한다.

• Output : ADAB

이동한 위치가 {0,0}이므로 종료, 그러므로 LCS는 "ADAB"이다.

왼쪽과 위쪽 모두 같을 때 왼쪽을 선택한 경우도 있다.

이럴 경우 LCS는 "ACBA"이다.

즉, 같은 LCS 길이에 다른 LCS값이 나올 수 있다.

소스 코드

package algorithm.lcs;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.jupiter.api.Test;

public class LongestCommonSubsequence {

  @Test
  public void testLcsLength() {
    assertThat(lcs("ADCABA", "ABCBDAB"), is("ADAB"));
  }

  public String lcs(String x, String y) {
    x = "0" + x;
    y = "0" + y;
    int[][] lcsTable = getLcsTable(x, y);

    StringBuilder lcs = new StringBuilder();
    backTracking(lcs, x.length() - 1, y.length() - 1, lcsTable, x);

    return lcs.toString();
  }

  private void backTracking(StringBuilder lcs, int m, int n, int[][] lcsTable, String x) {
    if (m == 0 || n == 0) {
      return;
    }
    //위쪽, 왼쪽, 대각선(왼쪽 위) 값보다 클 때 👉 문자 기록하고 대각선으로 이동
    if (lcsTable[m][n] > lcsTable[m - 1][n - 1]
        && lcsTable[m][n] > lcsTable[m][n - 1]
        && lcsTable[m][n] > lcsTable[m - 1][n]) {
      lcs.insert(0, x.charAt(m));
      backTracking(lcs, m - 1, n - 1, lcsTable, x);
    }
    //왼쪽 값과 같고, 위쪽 값보다 클 때 👉 왼쪽으로 이동
    else if (lcsTable[m][n] > lcsTable[m - 1][n]
        && lcsTable[m][n] == lcsTable[m][n - 1]) {
      backTracking(lcs, m, n - 1, lcsTable, x);
    } 
    //왼쪽, 위쪽 값과 같을 때 👉 위쪽으로 이동
    else {
      backTracking(lcs, m - 1, n, lcsTable, x);
    }
  }
}

마지막 두 조건문 순서를 바꾸면 LCS는 "ACBA"이다.

4. 예제

• Longest Common Subsequence - www.codewars.com/kata/52756e5ad454534f220001ef
• 문제 풀 때마다 추가 예정