정렬 알고리즘

정렬이라는 것은 일종의 조건에 맞게 아이템들을 나열하는 것을 말한다. 이러한 정렬에도 여러가지 방식이 있으며 이를 하나하나 알아보자. 중간중간 이해가 잘 되지 않는다면 visualgo에서 관련된 sorting 을 재생해보면 도움이 될 것이다.

선택 정렬, Selection Sort

선택 정렬이란 앞쪽 index 부터 시작해서 마지막까지 값들을 확인하며 최솟값을 비교한다. 끝에 다다랐을 때 최솟값을 앞 index에 넣는다. 즉 앞 쪽부터 정렬되게 된다.

구현

이를 kotlin 으로 구현하면 아래와 같다.

var min_idx = 0

for (i in 0..arr.lastIndex-1) {
    min_idx = i

    for (j in i+1..arr.lastIndex) {
        if (arr[min_idx] > arr[j]) min_idx = j
    }

    val term = arr[i]
    arr[i] = arr[min_idx]
    arr[min_idx] = term
}

TimeComplexity

for문이 2개이므로 O(n^2)이 된다. 만약 이미 정렬되어 있는 array라 하더라도 끝까지 탐색해보아야 알 수 있기에 그대로 O(n^2)이다.

버블 정렬, Bubble Sort

버블 정렬이란 연속된 두 값을 비교해 더 큰 값이 뒤로 가도록 수행하는 정렬이다. 선택정렬과는 정 반대로 뒤에서 부터 큰 값들이 정렬된다.

구현

for (i in 0..arr.lastIndex-1) {
    for (j in 0..arr.lastIndex-1-i) {
        if (arr[j] > arr[j+1]) {
            val term = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = term
        }
    }
}

TimeComplexity

일반적으로는 for문이 2개이므로 O(n^2)이다. 위 구현에 정렬되어 있을 경우 바로 알고리즘을 끝내는 장치를 추가한다면, 이미 정렬된 array는 O(n)이 된다.

삽입 정렬, Insertion Sort

index를 기준으로 해당 index의 값을 그 앞 index의 값과 비교하여 더 작을 경우 swap하고, 더 클 경우 반복을 마치고 다음 index의 값을 새롭게 정렬하기 시작한다. 정렬을 시작할 index 이전의 값들은 모두 정렬되어 있다는 특징이 있다.

구현

for (i in 0..arr.lastIndex-1) {
    for (j in i+1 downTo 1) {
        if (arr[j] < arr[j-1]) {
            val term = arr[j-1]
            arr[j-1] = arr[j]
            arr[j] = term
        } else break
    }
}

TimeComplexity

이 또한 이중 for문 이므로 일반적으로는 O(n^2)이 된다. 허나 이미 정렬이 되어 있을 경우 바깥쪽 for 문은 n-1번 도는데 반해, 내부 for문은 바로 앞 값하고만 비교를 하고 끝나게 되어서 (1번 시행) O(n)이 된다.

병합 정렬, Merge Sort

배열을 같은 크기(or +1)로 나눠 분할한 배열을 각각 정렬한 후 합하는 알고리즘이며, 분할 정복(재귀를 통한)을 이용한다.

구현

세 가지 함수로 나눠서 구현해보았다.

1. split : 배열을 두 개로 자른다.
2. merge : 두 배열을 합치며 정렬한다. 각 배열의 pointer를 이용하여 더 작은 값이 앞에 오도록 배열하면 된다.
3. mergeSort : 재귀함수이며, mergeSort를 실행한다.

fun mergeSort(arr:List): List { if (arr.size < 2) return arr

val (front, rear) = split(arr)
return merge(mergeSort(front), mergeSort(rear))

}

fun split(arr: List): Pair<List, List> { val mid = arr.size / 2 return Pair(arr.subList(0, mid), arr.subList(mid, arr.size)) }

fun merge(left:List, right:List): List { var l_idx = 0 var r_idx = 0

val result = mutableListOf<Int>()

while (l_idx < left.size && r_idx < right.size) {
    val l_v = left[l_idx]
    val r_v = right[r_idx]

    if (l_v < r_v) {
        result.add(l_v)
        l_idx += 1
    } else if (l_v > r_v) {
        result.add(r_v)
        r_idx += 1
    } else {
        result.add(l_v)
        result.add(r_v)
        l_idx += 1
        r_idx += 1
    }
}

if (l_idx < left.size) {
    result.addAll(left.subList(l_idx, left.size))
}
if (r_idx < right.size) {
    result.addAll(right.subList(r_idx, right.size))
}
return result

}

### TimeComplexity
단계를 계속해서 2로 나눠가면 쪼개기 때문에 단계는 logN개가 생길 것이다. 또 각 단계를 합칠때 결국 비교되는 숫자는 N개이기 때문에 상수xN번 시행되므로 결국 N이 된다. 따라서 단계 x 각 단계별 계산이 시간복잡도가 될 것이므로 O(NlogN)이 된다. 위 3개의 정렬과 다르게 항상 평균적으로 좋은 시간 복잡도를 보여준다.

## 퀵 정렬, Quick Sort
퀵 정렬이란 배열에서 임의의 하나의 값을 정하고 해당 값을 pivot으로 하여 이보다 작은 값은 pivot보다 왼쪽에, 큰 값은 pivot보다 오른쪽에 배치시키는 방식으로 정렬한다. 이 또한 재귀적으로 진행되는데 한번 시행한 경우 pivot의 위치가 고정되므로, 이를 제외하고 왼쪽과 오른쪽의 배열에 대해서 QuickSort를 다시 시행하면 된다.

### 구현
index를 이용해 새로운 배열 생성없이 처리가 가능하다.
```kotlin
fun quickSort(arr: IntArray, start: Int, end: Int) {
    if (start + 1 > end) return
    val pivot = arr[end]
    var i = start - 1

    for (j in start..end-1) {
        if (arr[j] < pivot) {
            i += 1
            val term = arr[j]
            arr[j] = arr[i]
            arr[i] = term
        }
    }
    arr[end] = arr[i+1]
    arr[i+1] = pivot
    quickSort(arr, start, i) // pivot 기존 왼쪽 배열 정렬
    quickSort(arr, i+2, end) // pivot 기존 오른쪽 배열 정렬
}

TimeComplexity

이러한 퀵 정렬은 배열이 pivot 기준으로 얼만큼 잘 짤리는지에 따라 결과가 많이 달라진다. 우선 최악의 경우는 pivot 기준으로 나머지 값이 모두 크거나, 모두 작은 경우이다. 이 경우 O(n^2)이 된다. 반면에 가장 이상적인 케이스의 경우 merge sort 처럼 매번 균등하게 분할이 될 경우이다. 이 경우 O(nlogn)이 된다. 평균적인 경우에는 O(nlogn)이 된다.

Merge Sort vs Quick Sort

merge sort는 평균적으로 O(nlogn)이 걸리고 quick sort 또한 평균적으로는 O(nlogn)이 걸린다. 여기에 quick sort의 경우에는 worst case에서는 O(n^2)으로 O(nlogn)인 merge sort에 비해 더 느린 케이스가 충분히 존재한다. 그럼에도 여러 자료들을 찾아보면 quick sort가 평균적으로 더 성능이 좋기에 이를 많이 활용한다고 한다. 이유가 뭘까 궁금해서 여러 내용을 찾아보았다.

• 정렬해야 하는 배열의 크기가 큰 경우에는 merge sort가, 작은 경우에는 quick sort가 성능이 더 좋다고 한다.
• merge sort는 추가 메모리 공간을 필요로 하는 반면, quick sort는 그렇지 않다.
• 참조의 지역성으로 인해 캐쉬의 도움을 많이 받는 quick sort가 일반적으로 더 빠르다. 여기서 지역성(Locality)이란 특정 부분의 정보를 집중적으로 참조하는 특성(?)이라고 할 수 있다. merge sort의 경우 넓은 범주의 값들을 계속해서 왔다갔다하며 참조하는 반면, quick sort의 경우 한정적인 범위에서 데이터들이 움직이며 시행이 거듭될수록 그 폭이 작아지므로 cache hit가 더 자주 일어나 "하드웨어"적으로 merge sort에 비해 더 우수하다.

정규화란 릴레이션 간의 잘못된 종속 관계로 인해 데이터베이스 이상 현상이 일어나 이를 해결하거나, 저장 공간을 효율적으로 사용하기 위해 릴레이션을 여러 개로 분리 하는 과정이다. 여기서 기억해둘 핵심은 "저장 공간"을 효율적으로 사용하기 위함이라는 것이다.

정규화 단계

단계라는 키워드를 사용하는 것이 적합한지는 모르겠으나, 이 정규화도 여러 종류가 존재한다. 일반적인것으론 1NF6NF와 BCNF 가 있으나, 실제적으로는 1NF3NF 정도까지의 과정을 거친다고 한다.(여기서 NF는 Normal Form의 준말이다.)

제 1 정규화, 1NF

1 정규형의 특징은, 원자성이다. 테이블의 컬럼 값이 원자값, 즉 하나의 값을 갖도록 테이블을 분해하는 것이다. 쉽게 말해 특정 테이블에서 임의의 데이터가 "과일" 이라는 컬럼에 대해 ["사과", "배"] 라는 값을 가지고 있다면, 이는 원자값이 아닌 것이다. 이 경우 이를 두개의 데이터로 나누는 것을 제 1 정규화라고 한다.

제 2 정규화, 2NF

제 1 정규화를 진행한 테이블에 대해, 완전 함수 종속을 만족하도록 하는 것이다. 여기서 완전 함수 종속은 기본키의 부분집합이 특정 필드의 결정자가 되면 안된다는 뜻이다. 사실 말로는 나도 잘 와닿지 않는다. 다음과 같은 예시가 있다.

제 3 정규화, 3NF

제 2 정규화를 진행한 테이블에서 이행적 종속을 없애는 것을 말한다. 이행적 종속이란 A->B와 B->C가 존재하는 상황에서, 논리적으로는 A->C가 성립하는데 이러한 종속을 테이블에서 제거하는 것을 말한다.

이 정규화를 하는 이유는 다음과 같다. 만약 기존 테이블에서 두번째 데이터의 과일을 배 -> 사과 로 변경하고 싶다고 하자. 물론 데이터의 변경 자체는 말 그대로 배 자체를 사과로 바꾸기만 하면 된다. 하지만 이 경우 가격이 600인 사과가 존재해야 한다는 만일의 가정 또한 필요해진다. 그게 아닌 경우라면 두번째 데이터의 가격 역시 600 -> 500으로 바뀌어야 할 것이다. 제 3 정규형은 이러한 일이 일어나는 것을 피하기 위해 이행적 종속을 없앤 것이다. 제 3 정규화를 거친 오른쪽을 보면 B의 과일을 사과로 바꾸더라도, 사과 -> 500이라는 가격 매핑은 그대로 유지되게 된다.

보이스 코드 정규형, BCNF

제 3 정규화를 진행한 테이블에서, 모든 결정자가 후보키인 상태로 만드는 것을 말한다. 여기서 결정자는 어떠한 칼럼 Y가 X에 대해서 결정될 때, 즉 X->Y 관계가 성립될 때 X를 결정자라고 한다. 즉 특정한 결정자가 후보키가 되지 못한다면, 후보키가 될 수 있는 범주로 테이블을 자르는 것이다.

정규화의 이면

이 정규화라는 것은 처음에 언급했듯이 "저장 공간"을 효율적으로 사용하기 위해 진행하는 과정이다. 그렇기에 DB 정규화가 DB의 처리속도의 향상을 항상 가져올 것이라는 것은 틀린 말이 된다. 여기서 DB의 처리속도란 CRUD에서 R과 CUD로 구분지을 수 있다. 데이터를 입력하고 수정하고 삭제하는 처리속도의 경우, 정규화를 수행하면 속도가 빨라진다. 실제적으로 한 테이블의 용량도 최소화되기에 그러할 것이다. 그러나 오히려 Read, 즉 조회 성능의 경우 조건에 따라 처리 속도가 저하될 수 도 있다. 그러한 이유야 여러가지가 있을 수 있지만 join의 영향도 꽤나 있을 것이다. 정규화를 하다보면 table을 여러개로 나누게 된다. 그렇다 보니 특정 쿼리의 경우 table join을 여러 번 해야할 수 있기 때문일 것이다.

확정적으로 말할 수 있는 것은 아니나, 결국 기억해야 하는 것은 정규화, 반정규화(비정규화, 역정규화라고도함. DB 성능 향상을 위해 데이터 중복을 허락해 데이터를 묶는 행위들의 일종)가 무조건적인 성능 향상 및 하락을 가져오는 것은 아니며, 상황에 맞게 적당한 수준으로 적용해야 한다는 것이다.

아래 링크에서 좀 더 자세한 예시들을 살펴볼 수 있다. https://dataonair.or.kr/db-tech-reference/d-guide/sql/?pageid=5&mod=document&uid=332

이진 탐색

영어로는 binarySearch라고 한다. 이 알고리즘은 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 여기서 핵심이 되는 말은 "정렬"이다. 이진 탐색이 이뤄지기 위한 조건이 바로 저 정렬되어 있다는 것이다.

이진 탐색 방식

알고리즘의 방식은 다음과 같다. 우선 정렬되어 있는 데이터 배열이 있다. 일단 오름차순이라고 가정하자. 우리의 목표는 값 k를 찾는 것이다. 이 이진 탐색 방식을 아래 순서로 설명한다.

1. 배열에서 중앙에 위치하는 임의의 값을 확인하고 k와 비교한다.
2. 값이 k보다 작다면 k는 해당 값보다 배열의 index 상 우측에 존재한다. 따라서 k 다음 값부터 마지막까지의 배열에 1번을 반복한다. 값이 k보다 크다면 반대로 k보다 작은 값들의 배열로 1번을 반복한다.
3. 이렇게 탐색을 하다 k 값을 찾게 되면 종료한다.
4. 혹은 전체를 탐색했지만 k 값을 찾지 못하고 다음 수색해야 하는 배열이 비어있다면, 해당 값이 존재하지 않는다고 판단하고 종료한다.

단순에 보이는 이 방식은 기존에 O(N)이 걸렸던 방식을 O(logN)까지 줄여준다.

코드로의 구현

이진 탐색을 kotlin 코드로 구현하면 아래와 같다. start가 end보다 커지거나, k를 발견할 경우 멈추게 되어 있다. k를 찾지 못하고 start > end가 되면 -1을 return하고 이는 값이 존재하지 않음을 의미한다.

fun binarySearch(arr: IntArray, k:Int): Int {
    var start = 0
    var end = arr.lastIndex

    while (start <= end) {
        val mid = (start+end)/2
        val cur = arr[mid]
        if (cur < k) {
            start = mid + 1
        } else if (cur == k) {
            return mid
        } else {
            end = mid - 1
        }
    }

    return -1
}

이진 탐색 알고리즘의 변형

이진 탐색 알고리즘의 경우 중복되지 않은 값들 중에서 특정한 값을 찾아낼 때 유용하다. 그렇다면 중복되는 값들이 배열로 주어졌을 때는 어떻게 해야할까? 이떄 유용하게 사용할 수 있는 변형된 형태의 이진 탐색 알고리즘이 있다. 바로 lower bound와 upper bound이다.

참고자료 : https://jackpot53.tistory.com/33

lower bound

말 그대로 아래쪽 경계를 의미한다. 중복이 허용되는 배열에서 특정한 값 k를 찾을 때 해당 k 값이 여러개 존재할 수 있다. lower bound의 경우 그러한 k 값들 중 가장 먼저 등장하는 k 값을 찾아준다. 또, 이러한 특징 때문에 k값 보다 크거나 같은 값이 처음으로 등장하는 위치를 찾아주는 역할도 한다.

구현은 아래와 같다.

fun lowerBound(arr:IntArray, k:Int): Int {
    var start = 0
    var end = arr.lastIndex

    while (start < end) {
        val mid = (start+end)/2
        val cur = arr[mid]
           if (cur < k) {
            start = mid + 1
        } else {
            end = mid    
        }
    }

    return start
}

upper bound

lower bound와 정 반대로 k값보다 처음으로 큰 값이 나오는 원소를 찾아준다. 구현은 아래와 같다.

fun upperBound(arr:IntArray, k:Int):Int {
    var start = 0
    var end = arr.lastIndex

    while (start < end) {
        val mid = (start+end)/2
        val cur = arr[mid]
        if (cur <= k) {
            start = mid + 1
        } else {
            end = mid
        }
    }

    return end
}

lower & upper bound의 활용

위에서도 언급했지만 lower bound의 경우 k값보다 크거나 같은 값이 처음으로 등장하는 지점을 찾기 위해서, upper bound의 경우 k값보다 큰 값이 처음으로 등장하는 지점을 찾기 위해서 사용한다. 해당 개념을 머리속에 잘 담아 두고 상황에 맞게 활용하면 된다.

이진 탐색의 활용

이진 탐색 자체를 탐색에 사용할 수 도 있지만, 고약한 문제의 경우 모든 경우의 수를 빠르고 효율적을 탐색할 수 있는 방법이 될 수도 있다. 예를 들어 1~n까지의 값들 중 답이 되는 값 k를 찾는 경우 말이다. 이럴 때는 문제에 이진 탐색이라는 것이 들어나지는 않으나, 생각치도 못하게 이진 탐색이 해법이여 버리는 상황들이 있다.

아래 문제가 그 예시이다. 나도 해설을 찾아 보기 전까지는 감도 찾지 못했었다. 그러나 사실 그렇게 좋은 문제라고 생각하지는 않는다.(개인의 생각이다.) 입국 심사 문제

누적합 알고리즘은 최근에 공부를 하며 접하게 되었다. 누적합의 개념 자체는 매우 간단하다. 특정한 배열이 있을 때, 해당 배열까지의 합을 나타내는 말이다. 즉 [1,2,3,4,5] 라는 배열이 있을 때 이 배열의 누적합을 배열로 나타내면 [1,3,6,10,15]가 되는 것이다.(물론 누적합 알고리즘의 구현에 편의를 위해 인덱스가 하나 큰 배열을 만들거나 하는 경우도 있다.)

누적합의 장점

누적합을 사용할 경우 time complexity의 관점에서 큰 이득을 가져다 준다. 이는 누적합의 경우 미리 계산!! 해둘 수 있기 때문이다. 만약 어떠한 배열에서 a번째 부터 b번째 까지의 수의 합을 알아야 한다고 가정해보자.

1. 누적합을 사용하지 않을 경우 a 부터 b 까지 직접 값들을 더해나가야 하며, 이 경우 0<=a<=b<=n에서 최악의 경우 O(N)의 시간이 걸리게 된다. 여기에 이러한 a~b 까지의 합을 구해야 하는 경우가 m번 존재한다면 O(NM)의 시간이 걸리게 된다.

2. 누적합을 사용하는 경우 누적합을 사용하려면 먼저 계산이 필요하다. 이 계산 자체가 전체를 탐색해야 하기 때문에 O(N)이 일단 필요하다. 하지만 그 이후 a~b까지의 합은 누적합 배열에서 (b까지의 합) - (a-1 까지의 합)으로 나타낼 수 있다. 즉 O(2) == O(1)로 해결할 수 있게 된다. 이 경우가 m번 존재한다 해도 결국 O(M) 만큼의 시간이 걸릴 것이고 결국 총 O(N+M)만큼 들게 된다.

따라서 M이 크면 클수록 누적합을 활용하는 것이 O(NM) >= O(N+M)이기에 시간 복잡도에서 큰 이점을 갖는다.

구현

사실 누적합은 구현이라고 할 것이 없다. 말 그대로 특정한 배열에 따라 해당 원소까지의 합을 미리 구해놓으면 되니 말이다. 다만 1차원이 아닌 2차원 배열로 확장할 경우 누적합을 잘 구할 수 있는 식 정도는 존재한다.

해당 내용은 추후에 복습을 하며 다시 추가해두겠다.

팁

이 누적합을 잘 활용할 수 있는 상황이 있다. 바로 연속되는 구간에 일정한 값을 더하거나 빼고 싶을 때이다. 만약 길이가 10인 배열의 37까지 1씩 더하고 싶다고 생각해보자. 이런 경우가 하나라면 그냥 하면 된다. 단순히 37까지 더하면 되는 것이다. 허나 이런 경우가 매우 많아 질 경우 문제가 된다. 이 때 사용할 수 있는 팁이다. 위 사진을 보며 설명해보자. 우선 3~7까지 1씩 더하고 싶은 거니까 목표는 (1)번과 같다.

1. 우선 (2)번과 같이 배열의 보다 크기가 1만큼 큰 배열을 만들자.
2. 수를 더하기 원하는 시작점(ex: 3)에 더하고 싶은 수(ex: 1)를, 수를 더하기 원하는 마지막점 + 1 자리에 (ex: 7 + 1 = 8)자리에 더하고 싶은 수에 -1을 곱해 (ex: -1) 배치하자. 이 경우 (3)번과 같은 형태가 될 것이다.
3. 그리고 (3)번 배열의 누적합 배열을 구해보자. 그러면 (4)번과 같은 형태가 되며 (1)번 배열의 맨 마지막에 0이 하나 붙어 있는 형태가 된다.
4. 이렇게 만든 (4)번 배열을 원래 기존의 배열에 각 원소끼리 덧셈을 하면 기존 배열에 3~7번 원소에 1을 더한 배열을 구할 수 있다.

이렇게 보면 아니 저게 무슨 의미가 있냐~ 이럴 수 있다. 하지만 위에서 언급했던 것 처럼, 해당 작업을 여러번 해야 될 경우 의미가 있다. 여러 구간에 여러 수를 더하고나 빼야 한다면 (2)번과 같은 배열을 만들어 (2) -> (3)으로 만드는 작업을 반복적으로 진행하자. 그렇게 되면 배열에 하고싶은 여러 작용을 (3) 배열 하나로 나타낼 수 있게 된다. 그 후 (3)의 누적합 배열을 구해 기존 배열과 계산만 해주면 훨씬 빠르게 간편하게 목표한 일을 달성할 수 있다.

연습 문제

아래 문제들을 누적합을 이용하면 효과적으로 해결할 수 있는 코딩테스트 문제들이다. 시간이 된다면 꼭 풀어보는 것을 추천한다. 파괴되지 않은 건물 광고 삽입 문제

순열과 조합

순열과 조합은 쉽게 수학 공부를 하다보면 확률과 통계에서 접할 수 있는 개념이다. Permutation과 Combination으로 말이다. 예전에 python을 할 때에는 python package에서 순열과 조합을 제공해줬던 것으로 기억한다. 따라서 별 어려움 없이 이를 활용할 수 있었지만, kotlin에서는 그렇지 않다. 그렇기에 kotlin에서 순열과 조합을 구현하는 방법을 알아보자.

조합

조합은 Combination으로 n개의 item 중 k개를 뽑는 방법을 의미한다. 이를 구현하면 아래와 같다. 아래 코드의 기준은 item이 Int일 때의 예시이다.

fun combination(el:List<Int>, k: Int): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    comb_helper(result, emptyList(), el, k, 0)
    return result
}

fun comb_helper(
    answer: MutableList<List<Int>,
    temp: List<Int>,
    el: List<Int>,
    r: Int,
    start: Int
) {
    if (r==0) {
        answer.add(temp)
    } else if (el.size-start == r) {
        answer.add(temp + el.slice(start until el.size))
    } else {
        for (i in start until el.size) {
            val cur = temp + el[i]
            comb_helper(answer, cur, el, r-1, i)
        }
    }
}

여러 방식이 있을 수 있겠지만 나는 이 방식을 사용한다. 우선 재귀적으로 불릴 helper function을 이용한다. helper function는 현재까지 뽑은 temp 에다가 r(추가적으로 더 뽑아야할 원소의 갯수)이 0보다 크다면 남은 원소(el 중 start 이후의 원소)들 중 한개를 뽑는 동작을 시행한다. 모든 가능한 선택지에 대해 시도하기 때문에 빼먹는 경우의 수는 없을 것이다. 이 방식을 통해 combination function 내부의 result에 원소를 추가하고, 마지막에 result를 return 하는 것으로 combination을 성공적으로 구현 할 수 있다.

여기까지의 글을 보고 구현이 이해가 안된다면 helper function을 아래와 같은 생각을 가지고 읽어보자.

1. 조합은 n개 중에 k개를 뽑는 것이다.
2. n개 중에 k개를 뽑는 것은 n개 중 임의의 원소 하나를 선택한후 남은 n-1개 중에서 k-1개를 뽑는 것과 동일하다.

순열

순열은 permutation이라고도 하며 특정 원소들을 순서에 상관있어 배열하는 것을 말한다. 사실 정확히는 n개의 원소중 k개의 원소를 중복없이 순서있게 배열하는 것이다. 다만 여기서 나는 구현의 편의를 위해서 n개 중의 k개의 원소는 이미 뽑았다고 가정하고, 이를 순서있게 배열하는 경우의 수를 구하는 것으로 초점을 좁혔다.

구현은 아래와 같다. combination에 비해 코드는 훨씬 간단하다(물론 실제 permutation이 combination을 포함하고 있기에 결국 combination 코드도 작성해야 하는 상황일 가능성이 크다.)

fun permutation(
    el: List<Int>, 
    fin: List<Int> = emptyList(), 
    candidates: List<Int> = el
): List<List<Int>> {
    if (candidates.isEmpty()) {
        return listOf(fin)
    } else {
        candidiates.flatMap { permutation(el, fin + it, candidiates - it)
    }
}

flatMap을 이용한 구현이며, 이는 요소들 중 하나씩 선택하가며 순서대로 배치하는 그런 방식이다.

이 구현은 다른 blog를 서칭하다 나오는 여러 구현 들 중 가장 마음에 들어 직접 구현해보며 공부했었다.

활용

이 순열과 조합은 생각보다 쓰임이 많다. 특히 combination의 경우에는 꽤나 유용하게 코딩테스트 문제에서 활용했었다. 다만 주의사항은 명확하다. 이 combination은 특히 꽤나 무겁다. 그래서 돌리는 것 만으로도 큰 시간 복잡도를 잡아먹게 되어있다. 원소들이 너무 많을 경우에는 조합을 사용하는 것이 올바른 풀이가 아닐 수 있으니 한번 재고해보자

이번 글에서 정리해볼 내용은 다익스트라 알고리즘과 플로이드-워셜 알고리즘이다. 이 두 알고리즘은 그래프에서의 최소 "비용"을 알아내기 위해서 사용한다. 아래 여러 목차들을 통해 이 말이 무엇인지 자세히 알아보자.

간선의 가중치

그래프는 간단히 정점(노드, node)와 간선(엣지, edge)로 이루어져 있다. 가장 간단한 그래프의 형식이라면 앞서 말한 노드와 엣지 자체의 존재만 고려하면 될 것이다. 허나 많은 경우 여기에 가중치라는 개념이 추가된다. 가중치는 쉽게 말해 비용이다. A와 B를 이어주는 a 라는 간선이 있을 때, 이 a라는 간선이 k라는 가중치를 가질 수 있는 것이다. 이 경우 A->B로 갈 때 k라는 비용이 필요하게 된다. 이 개념을 인지하고 나서 다음 내용을 보자.

최단 거리

그래프는 어떻게 보면 현실 세계를 나타낼 수 있는 구조이기도 하다. 단순히 Node들을 도시, Edge 들을 도로로 볼 경우 각 도시들 사이의 거리는 해당 도시들을 잇는 도로(Edge)의 가중치가 될 것이다. 조금 감이 오는가?

이때 서울에서 부산까지의 최단 거리를 구해야 한다고 생각해보자. 서울에서 부산까지 가는 경로는 아주 많을 것이다. 많은 노드와 엣지들을 지나게 될 것 이고, 각 경로마다 거리도 다를 것이기에 우리는 그 중 가장 짧은 거리를 찾기 위해서 가중치를 모두 더해서 그 합을 비교해야 할 것이다. 자 이것이 그래프에서 마주할 수 있는 최소 비용(거리, 등 등) 문제이다. 이번 글에서 알아보고자 하는 두 가지의 알고리즘이 바로 이런 그래프의 최단 거리, 최소 비용 문제에서 사용하는 알고리즘이다.

다익스트라

다익스트라 알고리즘, Dijkstra는 다이나믹 프로그래밍(DP)를 활용한 "최단 경로 탐색 알고리즘"이다. 여기서 DP는 간단히 말해 특정 작은 문제에 대해 값을 구해놓고 활용하는 방법~ 정도로 이해해두자. 결국 이 알고리즘이 DP인 이유는 최단거리란 여러 개의 최단 거리로 이루어져 있기 때문이다. 작은 문제로 나눠서 해결할 수 있기 때문에 DP의 특징을 살릴 수 있는 것이다. 이 다익스트라 알고리즘의 특징은 다음과 같다.

1. 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로(비용)을 알려준다.
2. 이 때 음의 간선을 포함할 수 없다.(가중치 == 비용 이 음수 값인 간선)

참고 : https://m.blog.naver.com/ndb796/221234424646

구현

실제로 다익스트라 알고리즘을 구현한다면 다음과 같은 순서를 가져야 한다.

1. root node를 설정한다.
2. root node의 인접 노드에 최소 비용을 업데이트 한다.
3. 방문하지 않은 node들 중 가장 비용이 작은 노드를 선택하고 이동한다.
4. 해당 node의 인접 노드의 최소 비용을 업데이트 한다.
5. 만약 인접 노드의 비용을 업데이트 했는데 해당 노드를 아직 방문하지 않았다면 방문해야할 목록에 추가한다.(코드적 구현)
6. 모든 node를 방문할 때 까지 3~5를 반복한다.

// 인접 node map이 구현되어 있다고 가정하자.
// value인 IntArray는 key에서 해당 array의 index까지의 비용이 적혀있다. 연결되어 있지 않을 경우 0 이다.
adjs = HashMap<Int, IntArray>() 


 fun dijkstra(adjs: HashMap<Int, IntArray>, start: Int, n: Int): IntArray {
     val dist = IntArray(n, {100000*n})
    val visited = BooleanArray(n)

    val queue = PriorityQueue<Pair<Int, Int>>({a,b -> a.second-b.second})
    queue.offer(Pair(start, 0))

    while (queue.isNotEmpty()) {
        val now = queue.poll()
        if (!visited[now.first-1]) visited[now.first-1] = true
        for (i in 1..n) {
            var next = adjs.getValue(now.first)[i-1] //현재부터 i까지의 거리\
            if (next != 0) {
                if (dist[i-1] > now.second+next) {
                    dist[i-1] = now.second+next
                    if (!visited[i-1]) {
                        queue.offer(Pair(i, dist[i-1]))
                    }
                }
            }
        }
    }
    dist[start-1] = 0

    return dist
}

해당 코드를 읽어보면 이해가 될 것이다.

Time-complexity

방문하지 않은 노드들 중 최단 거리를 구하는 데에 있어 선형 탐색을 사용할 경우 O(n^2)이 되고, 위 코드와 같이 heap 자료구조 형 중 하나인 PriorityQueue를 활용할 경우 O(nlogn)으로 줄일 수 있다.

플로이드-워셜

Floyd-Warshall 알고리즘의 경우 다익스트라 알고리즘의 확장형(?) 이라고 할 수 있을 지도 모른다. 노드 까지의 최단 거리를 구한다는 목적 자체느 비슷할 수 있으나 플로이드-워셜 알고리즈만의 특징들이 있다.

1. 플로이드-워셜 알고리즘은 모든 노드간의 최단 비용(경로)를 구할 수 있다. 다익스트라가 임의의 노드로 부터 모든 노드까지 였다면, 플로이드-워셜은 전체에 대해서 이를 구한다.
2. 플로이드-워셜의 경우 음의 간선(edge)에서도 사용할 수 있다.

구현

이를 구현하기 위해선 우선 인접 노드 비용 배열을 구해야 한다. 이때 map 형태가 아닌 정말 행렬(이중 array?)의 형태로 나타내는 것을 추천한다. 또 그 상태에서 서로 인접하지 않은 node까지의 비용은 아주 큰 값(최대 비용보다 클 값)으로 설정해야 한다. 또 자기 자신으로의 비용은 0으로 한다. 이러한 초기 셋팅 후 과정은 다음과 같다.

1. 특정 노드 i를 선택한다.
2. 노드 i를 중간 노드로 하여 a -> b로 가는 비용을 업데이트 한다. 이를 좀더 자세히 설명하자면 기존의 a->b로 가는 비용과 a->i + i->b로 가는 비용을 비교하여 더 작은 것으로 업데이트 한다.
3. 12의 과정을 모든 노드(i, 1n)에 대해서 반복한다.

이를 코드로 살펴보자

    // 최종적으로 만들고자 하는 행렬의 초기화
    // 기본적으로 모든 비용을 매우 큰 값으로 설정한다.(해당 값은 특정 문제의 조건임으로 의미를 갖지 말아라.
    val dists = Array<IntArray>(n, {IntArray(n, {100000 * n})}) 

    // fares는 노드간의 연결을 의미한다. [노드a, 노드b, 비용]의 형태를 갖는다.
    for (edge in fares) {
        dists[edge[0]-1][edge[1]-1] = edge[2]
        dists[edge[1]-1][edge[0]-1] = edge[2]
    }

    // 자기로의 거리는 0으로 나타낸다.
    for (i in 0..n-1) {
        dists[i][i] = 0
    }

    // 모든 노드에 대해서 중간 노드가 되는 것을 고려하고
    for (k in 0..n-1) {
        // 두번의 for문을 통해서 모든 케이스에 대해 체크 한다.
        for (i in 0..n-1) {
            for (j in 0..n-1) {
                dists[i][j] = min(dists[i][j], dists[i][k] + dists[k][j])
            }
        }
    }

위와 같이 dists를 모두 업데이트 하고 나면 dist[i][j]가 i 노드에서 j 노드로 가는 최단 비용(거리)가 된다.

Time-complexity

위 코드에서 살펴볼 수 있듯, O(n^3)인 아주 무거운 시간 복잡도를 가지고 있다. 따라서 n이 너무 크지 않은 경우에만 활용할 수 있다.

활용

이 두 알고리즘 모두 그래프에서 활용할 수 있다. 다만 활용 조건이 좀 다르다는 것만 다시 한번 기억하고 가자.

• 시작 노드가 정해져 있는 상태에서 특정 노드 까지의 거리 1개만 확정적으로 구하면 되는 경우에는 다익스트라를 사용한다.
• 시작노드가 정해져 있지 않은 많은 경우를 고려해야 한다면 플로이드-워셜 알고리즘을 쓴다. 다만 이때 그래프의 사이즈를 한번 생각해보자.

BFS, DFS

BFS는 Breadth-First Search로 너비 우선 탐색, DFS는 Depth-First Search로 깊이 우선 탐색을 말하다. 두 탐색법은 모두 그래프에서 사용하는 방식이다. 이를 좀 더 자세히 알아보자

그래프, 트리

그래프를 간단히 말하자면 정점(Node)와 간선(Edge)들로 이루워진 자료구조의 일종을 말한다. 여러 종류들의 그래프가 있으나 그 중 가장 친숙한 것은 아마 "트리"일 것이다. 트리는 그래프의 한 일종이며 부모와 자식의 계층을 갖는 자료구조를 말한다. 여기서는 깊게 다루지 않겠다.

그래프의 탐색

이러한 그래프를 탐색하고자 할 때가 있다. 여기서의 탐색이란 하나의 정점에서 시작하여 그래프의 다른 모든 정점을 한번씩 방문하는 것을 말한다. 왜냐하면 그래프의 경우 배열과 같이 정렬되어 있지도 않고, 따라서 특정한 값을 찾기 위해서는 모든 Node를 직접 방문해야 하기 때문이다. 아무튼 이러한 목적을 갖고 그래플르 탐색하는 방법의 가장 대표적인 두가지 방법이 바로 BFS와 DFS이다.

BFS - 너비 우선 탐색

임의의 노드에서 시작하여 인접한 노드를 먼저 탐색해 나가는 방법이며, 시작 지점에 가까운 노드들을 먼저 탐색하게 된다. 일반적으로 특정한 노드나 값, 상태에 최단 거리로 도달하는 경로를 찾을 때 사용하게 된다. 그래프를 생각해본다면 시작 노드의 인근 노드를 전부 먼저 탐색한 후, 해당 노드들의 인근 노드들을 다시 모아 재차 탐색하는 형식이 될 것이다.

이를 코드에서 구현하기 위해서는 Queue를 사용하면 된다. 노드를 탐색하고, 자신과 인근한 노드들을 queue에 넣어 주는 형태로 탐색을 하면 쉽게 구현할 수 있다.

DFS - 깊이 우선 탐색

임의의 노드에서 시작하여 진행할 수 있는 끝까지 탐색을 하고 다시 돌아와 다음 선택지를 탐색하는 것을 말한다. 쉽게 설명하자면 길을 가다 여러 갈림길이 있을 때, 한 쪽으로 끝까지 가서 그 끝을 확인 한 후 다시 갈림길로 돌아와 다른 길을 선택하는 경우를 말한다. 일반적으로 A -> B 로의 경로에 있어서 그 경로의 특징(루트 or ?)을 기록하거나, 조건이 존재할 때 사용한다.

이를 코드에서 구현하기 위해서는 Stack이나 재귀함수를 사용하면 된다. stack을 사용할 경우 해당 노드를 탐색하며 나오는 인접한 노드들을 Stack에 넣어주며 진행하면 된다.(이때 순서를 헷갈릴 수 있으니 구현하고 직접 확인해 보자.) 두 번째 방식인 재귀함수를 이용하는 편이 좀 더 편리할 때가 많다. 재귀함수 내부에서 visited와 adjs(인접 리스트 or 맵)를 가지고 현재 노드에 근접한 노드에 대해서 다시 재귀함수를 부르는 식으로 말이다.

연습

실제로 코딩테스트 문제를 풀어보며 연습해보는 것을 추천한다. 나도 후에 해당 문제들을 다시 풀어보려 한다. https://school.programmers.co.kr/learn/courses/30/parts/12421

간단하게 말하자면 말 그대로 순차적인 처리를 생각하는 프로그래밍이다. 컴퓨터의 작업방식과 유사하기에 처리 속도가 상당히 빠르다는 장점이 있으며, 데이터를 중심으로 함수를 구현한다. 대표적으로 C언어가 있다.

OOP, 객체지향 프로그래밍

Object Oriented Programming의 약자인 OOP는 객체지향 프로그래밍을 뜻한다. 객체 지향의 경우 기능을 중심으로 메소드를 구현한다. 이는 절차 지향과 완전히 반대되는 개념이 아니다. 다만 무엇을 중점적으로 보고 개발하느냐의 차이이다.

SOLID

OOP의 5원칙이라고 소개되고는 하는 SOLID 이다. 객체 지향 프로그래밍 및 설계의 다섯 가지 기본 원리다~ 정도로 생각해두면 좋을 것 같다.

SRP(Single Responsibility Principle) 단일 책임 원칙

각 모듈(클래스)은 하나의 책임만을 가져야 한다는 원칙이다. 이는 해당 모듈이 변경되는 이유가 하나여야 함을 뜻한다. 책임 영역을 확실히 하는 것으로 특정 코드를 변경해야 하는 시점을 정확하게 분리해 낼 수 있고, 코드를 유지보수하기 매우 용이해진다.

-> 수정이 일어날 때 특정 클래스의 비즈니스 로직 상 변경이 아니라, 외부 클래스의 구현 변경 등으로 변경되어서는 안된다.

OCP(Open Close Principle) 개방폐쇄원칙

확장에는 열려있고, 변경에는 닫혀있어야 한다는 원칙이다. 요구사항이 변경되거나 추가되었을 때 기존 코드는 수정이 최대한 일어나지 말아야 하고, 기존 코드를 확장해서 재사용이 가능해야 한다는 의미이다. 이를 달성하기 위해서 우선 코드의 핵심적인 부분을 정리하고, 바뀌는 부분과 바뀌지 않는 부분을 확실히 분리한다. 변하지 않는 부분을 기준으로 인터페이스를 만들고, 이 인터페이스를 중점으로 추가 코드를 구현하면 됩니다.

LSP(The Liskov Substitution Principle) 리스코프 치환 원칙

하위 타입이 상위 타입을 대체할 수 있어야 한다는 뜻으로, 상위 타입을 사용하던 client가 상위 타입이 하위 타입으로 바뀌어도, 상위 타입의 인터페이스에 정의된 여러 method들을 그대로 사용하는 등 문제가 없어야 함을 의미한다.

ISP(Interface Segregation Principle) 인터페이스 분리 원칙

한 클래스가 자신이 사용하지 않는 인터페이스의 경우에는 구현하지 말아야 한다는 원리이다. 즉 애매하게 공통되는 클래스들을 하나의 인터페이스로 묶지 말고, 각각의 역할에 맞게 분리된 여러 개의 인터페이스를 사용하라는 의미이다. 복잡한 인터페이스를 여러 목적에 맞게 분리하는 것으로 이뤄낼 수 있을 것이다.

DIP(Dependency Inversion Principle) 의존 역전 원칙

고수준 모듈: 변경이 없는 추상화된 클래스(or interface) 저수준 모듈: 변하기 쉬운 구현체 클래스

저수준 모듈의 변경이 고수준 모듈의 변경을 일으키는 위계관계를 끊어버리는 역전을 의미한다. 실제로 사용 관계는 바뀌진 않지만, 추상화를 통해 이를 이뤄낼 수 있다. 일반적으로 알고있는 DI라고 생각해도 될 것 같아 길게 설명을 적지는 않으려 한다. 의존성이 역전 되는 것은 컴파일 시점, 즉 소스 코드 단계. 런타임에서는 구현체에 의존하게 된다.

OOP의 특징

Encapsulation

캡슐화라고 하며, 결합도(다른 클래스와의 연결)를 낮추는데 도움을 준다. 실제 구현이 외부로 드러나지 않게 하는 것이며, 특정 변수나 함수만을 외부로 노출시킨다.

Inheritance

부모 클래스가 자식 클래스에게 자신의 특성(속성)을 그대로 물려주는 것을 의미한다. 코드의 재사용이라는 측면에서 좋으며, 서로 관계있는 클래스들이 정의됨.

Abstraction

핵심 목적에 해당 하는 코드(변수, 메소드)를 인터페이스로 분리하여 따로 표현하는 것.

Polymorphism

overriding과 overloading을 통해서 같은 형태이지만 상황에 알맞게 다른 기능을 하게 한다.

TCP

Transmission Control Protocol의 약자로, 컴퓨터가 다른 컴퓨터와 데이터 통신을 하기 위한 프로토콜의 일종이다. OSI모형에서 L4인 Transport Layer에서 사용하는 규약이며, "가상회선 패킷 교환 방식"을 통해 통신을 한다.

TCP 3-way handshake

TCP는 연결지향 프로토콜로 신뢰성 확보를 위해 통신 전 먼저 3-way handshake를 한다. 구조는 다음과 같다. 클라이언트와 서버가 있다고 하자.(클라이언트와 서버의 분류는 먼저 요청하는 쪽이 클라이언트라고 해두자)

1. 클라이언트가 서버에 SYN 패킷을 보낸다. 이때 client의 ISN을 담아 보낸다.
2. 서버에서는 이를 확인하고 응답 ACK와 SYN 패킷을 클라이언트로 보낸다. 이때 승인 번호로 ISN + 1을 보낸다.
3. 클라이언트에서 받은 패킷에 대한 응답으로 ACK를 보내고 ESTABLISHED 상태가 된다.
4. 서버는 이 패킷을 받고 ESTABLISHED 상태가 된다.

이렇게 양 쪽이 모두 ESTABLISHED 상태가 되면 서로 신뢰성 있는 연결을 맺게 된 것이다.

TCP 4-way handshake

3-way handshake와 반대로 연결을 종료할때는 4-way handshake 과정이 발생한다.

1. 클라이언트가 서버에 FIN으로 설정된 세그먼트를 보내고, FIN_WAIT_1 상태가 된다.
2. 서버는 이를 받아 확인했다는 ACK 세그먼트를 보내고, CLOSE_WAIT 상태가 된다. 클라이언트는 해당 응답 세그먼트를 받고 FIN_WAIT_2가 된다.
3. 이후 서버가 통신을 끝내고 연결을 종료할 준비가 되면 클라이언트에 FIN 세그먼트를 보낸다.
4. 이를 받은 클리이언트는 TIME_WAIT 상태가 되고, 서버에 ACK를 보내 서버는 CLOSED 상태가 된다.
5. 클라이언트는 일정시간 동안 유지되다 CLOSE 상태로 전환되며 연결이 끝난다.

• TIME_WAIT : 그냥 연결을 끊지 않고 일정 시간을 남겨두는 것이다. 그 이유는 지연 패킷이 발생할 경우를 대비하기 위해서이다. 패킷이 모종의 이유로 뒤늦게 도착했는데, 이를 처리하지 못하게 되면 데이터 무결성 문제가 발생할 수 있기에 안전장치의 용도로 바로 연결을 닫지않고 짧은 시간동안 유지합니다.

TCP/IP

위에서 TCP에 대해 알아보았다. 그렇다면 왜 TCP/IP를 묶어서 칭하는 것일까? 이 두 프로토콜을 묶어서 자주 사용하기 때문이다. IP의 역할은 전달하고자 하는 목적지의 주소를 보고 그 경로를 정한고 올바르게 향하게 한다. 다만 이 IP는 전송의 책임을 지지 않는다. 즉 상대방이 제대로 받았는지에 대한 보장을 해주지 않는 비연결형적인 특징을 가지고 있다. !여기서 TCP가 등장한다. 위에서 알아봤듯이 TCP는 3-way handshake를 이용하며 연결지향 프로토콜로 메시지가 잘 도착했는지를 관리해줄 수 있다. 따라서 TCP와 IP를 같이 사용하는 것으로 IP의 단점을 상쇄할 수 있는 것이다.

흐름 제어

TCP/IP가 제공하는 기능(?) 중 송신측과 수신측의 TCP 버퍼 크기 차이로 인해 생기는 데이터 처리 속도 차이를 해결하는 기법이다.

stop and wait

하나씩~ 하나씩 주고받으며 처리 하는 방식이다. 매우 비효율적이다.

sliding window

어디서 많이 봐본 window를 사용하는 방식이다. window size의 경우에는 처리할 수 있는 패킷(세그먼트)의 양을 말하며 최초 window size의 경우 수신자 쪽에서 3-way handshake 과정 중에 정하게 된다. 이 window size를 통해서 송신자는 자신이 얼마까지 더 보내도 되는지를 파악하고, 수신자는 ACK에 처리가 가능한 만큼의 window size를 담아 보내 window size를 갱신시키는 것이다.

혼잡 제어

혼잡 제어의 경우 양 엔드포인트(송/수신자) 말고 그 데이터가 지나가는 네트워크 망의 혼잡도를 제어하는 기법이다. 예로 라우터가 처리할 수 있는 양을 초과하면 라우터는 데이터를 더이상 처리할 수 없고, 응답을 받지 못한 송신측은 손실이라 판단하여 계속해서 데이터를 전송하면 네트워크가 아주 혼잡해진다.

AIMD

Additive Increase & Multicative Decrease. 처음엔 패킷을 하나씩만 보내고, 문제가 없으면 window size를 증가시켜 간다. 전송이 실패할 경우 window size를 절반으로 줄인다. 이 방법의 경우 초기에 window size가 늘어나는데 너무 오랜 시간이 걸려 최고의 성능을 내기까지 시간이 걸린다.

Slow start

window size를 지수적으로 증가시키며, 혼잡이 감지되면 1로 줄인다. 수신쪽에서 보낸 ACK가 도착할때마다 증가시키기에 가면 갈수록 증가가 빨라진다.

Fast Retransmit

이 방법은 패킷을 재전송 하는 기법이다. 수신 측에서 먼저 보낸 패킷이 도착하지 않았는데 다음 패킷이 도착할 경우 도착했어야 하는 패킷의 순서를 담에 ACK를 보내준다. 송신측에서 해당 ACK를 3번 감지하면 문제가 되는 패킷을 재전송해준다. 이를 통해 송신측에서 설장한 응답 timeout이 되기 전에 패킷을 재전송 할 수 있게 된다.

Fast Recovery

혼잡상태가 되면 window size를 반으로 줄인 후 선형적으로 증가시킴. 혼잡 후에 AIMD와 같은 방식으로 동작

DB Transaction

데이터베이스에서 하나의 논리적 기능을 수행하기 위한 작업의 단위를 말하며, 여러 개의 쿼리들을 하나로 묶는 단위이다.

Transaction의 성질

Atomicity

트랜잭션과 관련하여 쿼리들이 모두 수행되거나 하나도 수행되지 않는 "All or Nothing"을 의미한다. commit과 rollback을 통해서 데이터의 무결성이 유지된다.

• commit : 여러 쿼리가 성공적이였다고 확정되는 명령어를 말하며, 트랜잭션 단위로 수행된다. 이 commit 되었다의 뜻은 영구적으로 저장되었다 라는 말과 같다.
• rollback : 에러 혹은 여러 이슈로 인해 트랜잭션으로 처리한 하나의 쿼리 묶음을 일어나기 전으로 되돌리는 것을 말한다.

또 하나의 트랜잭션 안에 외부 API가 있을 경우 rollback에 어떻게 대처할지에 대한 방법이 정해져 있어야 한다.

Consistency

허용된 방식으로만 데이터를 변경해야 한다는 것을 의미한다. 즉 항상 일관된 방식으로 트랜잭션 작업을 처리해야 한다.

Isolation

격리성이며, 여러 트랜잭션이 동시에 진행될 때 서로 끼어들 수 없다는 것을 의미한다. 이 격리성에는 여러 수준이 존재한다.

SERIALIZABLE

트랜잭션을 순차적으로 진행시키는 것을 말한다. 여러 트랜잭션이 동일한 행에 동시접근 할 수 없고, 그렇기 때문에 교차 상태가 일어날 확률이 많고, 성능이 떨어진다.

REPEATABLE_READ

하나의 트랜잭션이 수정한 행을 다른 트랜잭션이 수정하지 못한다. 다만 새로운 행이 추가될 수는 있다.

• 팬텀 리드 : phantom read, 해당 격리조건에서 일어날 수 있는 현상으로, 하나의 트랜잭션 내부에서 동일한 쿼리를 보냈을 때 그 조회 결과가 다른 경우를 말한다.

READ_COMMITTED

다른 트랜잭션이 commit한 정보에 대해서만 조회가 가능하다. 또 하나의 트랜잭션이 수정한 행을 다른 트랜잭션이 또 수정할 수 있다. 가장 많이 사용되는 격리수준으로 MySQL8.0, PostgreSQL 등의 기본값입니다.

• non-repeatable read : 한 트랜잭션 내에서 같은 행을 두 번 이상 조회하였는데, 그 데이터(값)이 다른 경우를 말한다.

READ_UNCOMMITTED

다른 트랜잭션이 commit하지 않은 행에 대해서도 다른 트랜잭션에 노출이 됩니다. 가장 격리 수준이 낮고, 데이터 무결성을 해칠 수 있으나, 조금의 손실을 무시하고 빠른 속도를 내기 위해서는 유용합니다.

• 더티리드 : dirty read, 한 트랜잭션이 실행 중일 때 다른 트랜잭션에 의해 수정되었지만 commit되지 않은 결과물을 읽을 수 있는 현상을 말한다.

Durability

트랜잭션이 성공적으로 완료되었을 경우, 그 결과는 영원히 반영되어야 하는 것을 의미한다. 이를 위해 체크섬, 저널링, 롤백 등의 기능을 제공한다.

DB Index

DB에서 데이터를 빠르게 찾기 위한 하나의 장치이다. 특정한 데이터 필드를 기반으로 인덱스를 만들 수 있는 것 같다.(?) 인덱스를 생성하게 되면 별도 메모리 공간에 데이터와 데이터의 물리적 주소를 함께 저장하고, 이때 데이터를 오름차순 정렬!!! 한다.

Index 사용의 장점

• 인덱스 테이블 스캔의 경우 정렬이 되어있기 때문에 Where 절이 효율적으로 동작한다.(검색이빠르다.)
• 정렬을 피할 수 있다. 이미 정렬되어있기 때문에
• Min, Max가 빠르다.

Index 사용의 단점(맹점?)

• index는 데이터 추가/수정에 약한다. 새롭게 데이터가 추가되면 정렬을 다시해야하며, 또 단순 원본테이블 뿐만 아니라 인덱스 테이블도 수정해줘야 되기 때문이다.
• 검색하고자 하는 양의 따라서 index 검색이 더 느릴수도 있다.
• Index를 너무 많이 만드는 것 또한 좋지 않다. 결국 Index 자체도 cost가 발생하게 되기 때문이다. 한 개의 쿼리를 위해서는 Index가 속도를 향상시킬 수 있으나, 결국 이러한 Index가 많이 쌓이면 전체적인 DB의 성능이 떨어질 수 있다.

Index 관리 구조

참고 사항 정도로 알아두자. 일반적으로 인덱스는 B+트리라는 자료구조로 이루어져 있으며, 이는 큰 대수확장성을 지녀(깊이와 리프 수의 간의 관계) 효율적으로 index를 저장해준다.

Dependency Injection의 줄임말로 말 그대로 해석하자면 "의존성 주입"이다. "의존관계를 외부에서 결정하고 주입하는 것"이며, 인터페이스를 사이에 둬서 클래스 레벨에서는 의존관계가 고정되지 않도록 하고 런타임 시에 관계를 동적으로 주입하는 방식이다.

이러한 DI가 필요한 이유

개발을 하다보면 코드간의 의존성이 생기게 된다. A가 B를 의존한다는 것은 결국 B가 변하면 A도 그에 따른 영향을 받게 된다는 것이다. 이는 지속적인 코드 유지에 있어 그다지 좋은 영향을 가져다주지 못한다. 또 여기서 추상화를 곁들이면 이야기가 한층 풍부해진다. 인터페이스를 통해 의존관계에 있는 클래스를 추상화해보면, 더 다양한 구현이 가능해지는 것을 확인해 볼 수 있다.

DI의 구현

위에서 언급했던 데로, 런타임시에 그 의존관계를 외부에서 주입하는 것으로 DI가 완성된다고 할 수 있다. 아래와 같은 코드를 예시로 들 수 있겠다.

Class Restaurant(
    food: Food
) {
    val main: Food = food
}

interface Food {
    fun cook()
    ...
}

class Pasta(): Food {
    override fun cook() {
    ~~
    }
}

class Pizza(): Food {
    override fun cook {
    ~~
    }
}

--------
val restaurant = Restaurant(Pasta())

코드적으로 살짝 문제가 있을 순 있지만(?) 일단 구현 자체는 이러한 것 같다. 결국 실제로 코드가 돌아가는 시점에 restaurant가 어떤 메인 음식을 만들지 주입하게 되고, 이렇게 되면 Dependency Injection이 실현된 것이라고 보면 되는 것 같다.

DI의 장점

1. 의존성이 줄어든다 DI를 사용하게 되면 결국 인터페이스를 사용하게 된다. 그렇다는 말은 주입되는 구현체가 변경되더라도 실제적으로 코드 수정이 많지 않게 될 가능성이 커진다. 예를 들어 위 예시에서 메뉴가 피자에서 파스타로 바뀐다 하더라도, 기존에 restaurant 객체가 사용하고 있을 수 있는 cook()과 관련해서는 수정할 이유가 없어지기 때문이다.

2. 재사용성이 높아진다. 인터페이스를 통하기 때문에 해당 인터페이스 자체를 여러 곳에서 재활용할 수 있게 된다.

3. 테스트가 수월해진다. 이는 객체를 외부에서 주입해주기 때문에 특정 객체나 인터페이스에 대한 테스트를 분리해서 진행할 수 있어, 테스트가 용이해진다.

IOC

Inversion Of Control의 줄임말로 말 그대로 해석하면 "제어의 역전"정도가 될 것 같다. 프로그래밍적으로 해당 말을 해석해보면 프로그램의 제어권이 역전되는 것을 의미한다. Spring과 같은 framework에서 IOC가 사용된다~ 라는 의미는 결국 각 객체들의 lifecycle 자체를 코드를 작성하는 개발자가 아닌 Framework가 도맡아 진행하는 것을 말하는 것이다

IOC가 없는 상황

만약 여러 객체들의 생명 주기를 직접 관리한다고 생각해보자. 작은 규모의 코드를 짜야 하는 경우에는 큰 문제가 없을 수 있다. 세개 정도의 객체를 생성하기 특정 method에서 한 개 정도는 삭제도 하고, 뭐 수정도 하고 잘 관리할 수 있을 것이다. 헌데 만약 아주 복잡한 비즈니스 로직을 적용해야 한다고 생각해보자. 세개의 객체의 생성, 수정, 삭제가 복잡하게 엮여있고, 거기에 비즈니스 로직까지 섞는 상상 말이다. 물론, 구현이 가능할 것이다. 허나 편하진 않을 것이다. 더 나아가 서비스가 아주 커져 다뤄야할 객체가 아주 많아졌다고 생각해보자. 개발자고 손수 하나하나 생성하고 삭제하고 하다보면, 반복작업도 굉장히 많아지고 그러다 실수가 나올 확률도 더 커지게 된다.

IOC가 있다면

IOC는 객체의 lifecycle 관리, 흐름 제어를 제 3자(프레임워크 등)에게 위임하는 프로그래밍 모델이다. 결국 객체를 관리해주는 역할을 따로 분리하는 것으로, 개발자는 자신이 집중해야 하는 비즈니스 로직에만 집중할 수 있게된다. 따라서 각 객체는 자신이 나중에 언제 어떻게 쓰일지에 대한 고민 없이, 자신의 기능을 구현하기만 하면 되는 것이다.

정리

IOC에 대해 정리하자면, 결국 개발자는 기계의 부품들을 정갈하고 잘 동작하도록 만들어 두는 것이다. 자신의 역할에 맞는 기능을 수행하도록 부품을 잘 만들어두면, 프레임워크가 객체들을 알맞은 시점에 생성하고, 메서드를 호출하고 또, 소멸시킨다. 이런 것이 바로 제어의 역전, IOC인 것이다.

DI와 IOC의 관계

그렇다면 이 DI와 IOC의 관계를 어떻게 보아야할까? 하나의 객체가 생성될 때 의존관계에 있을 다른 객체를 결국 "외부"에서 주입하게 되는 것이 DI인 것이고, 여기서 이 외부가 제3자가 되어 객체의 생명주기를 컨트롤할 수 있게 되어 IOC 모델이 완성된다. 결국 DI는 IOC 프로그래밍 모델을 구현하는 여러 방식 중 하나가 된다.

더 개념적으로 접근해보다면

• IOC는 독립적인 제 3자에게 객체의 생명주기를 제어하는 역할과 책임을 위임하는 프로그래밍 모델이고
• DI는 인터페이스라는 추상화를 통해서 객체를 다이나믹하게 주입해서 프로그래밍을 유연하게 할수 있게 하는 좀 더 구체적인 패턴이다. 정도가 될 것이다.

Spring에서의 IOC, DI

Spring IoC Container

스프링 프레임워크에서 객체의 생성/관리를 책임지는 컨테이너가 바로 이 IoC 컨테이너이다. 인스턴스의 생성부터 소멸까지 그 생명주기 관리를 바로 이 컨테이너가 대신 해주기 때문에, 개발자는 비즈니스 로직에 집중할 수 있게 된다.

Spring에서의 Bean

Spring을 공부하다 보면 Bean이라는 개념을 마주하게 되는데, 이 개념은 바로 IoC Container가 관리하는 오브젝트들을 칭한다.

ApplicationContext

실제로 스프링에서 IoC container 역할을 하는 것이 ApplicationContext이다. 물론 기본이 되는 IoC Container는 Bean Factory이지만 여러 기능이 추가된 ApplicationContext를 일반적으로 사용한다.

@Configuration : 설정정보를 나타내는데 사용하며 클래스에 붙힌다. 해당 annotation이 있는 class 내부의 @Bean 이 붙은 method를 호출해서 반환된 객체를 스프링 컨테이너에 등록한다.(이렇게 관리를 한다)

@Component : 해당 annotation이 붙어있는 class 자체를 Bean으로 등록해준다. (component scan을 통해서)

Spring 에서의 DI

스프링에서의 DI는 어떻게 이뤄지는가를 알아봅니다. 우선, 스프링에서는 ApplicationContext가 관리하는 Bean 만이 의존 주입이 가능합니다. 또한 이때 @Autowired라는 annotation을 활용합니다. DI를 실현하는 방식으로는 field, setter, constructor 세가지가 있으나, 이 중에서 constructor가 가장 안전한 방법이라고 여러 글에서 소개한다. 물론 나도 이 방식을 선호한다.

@Service
class AService(
    @Autowired val aRepo: ARepo
) {}

코틀린으로 작성할 경우 이와 같이 constructor에서 @Autowired annotation을 붙혀주면 해당 Type에 맞는 Bean을 탐색해서 자동으로 주입해주게 된다. 결국 @Autowired를 통해서 Spring Bean을 주입했고(DI), 그 주입을 Spring Container(IOC)가 해주는 것이기에, DI가 Spring의 핵심 개념이 되는 것이다.

네트워크에서 통신이 일어나는 과정(혹은 여러 프로토콜의 모음들)을 계층으로 나눠둔 것을 말하며, TCP/IP 4계층과 OSI 7계층이 있다.

OSI 7계층

OSI 7계층은 국제 표준화기구 IOS에서 개발한 모형이다. 아래에 가장 아랫단부터 최상단 application 까지 각 계층 별로 내용을 간단히 정리해보았다.

L1 Physical 계층

• 물리적으로 데이터를 전송하는 역할만을 맡는다.
• bit를 다룬다.
• 데이터를 전달만 하기에 알고리즘, 오류제어 기능 등이 없다.
• 케이블, 리피터, 허브, AP 등의 장비가 있다.

  L2 Data link 계층

• 물리적인 연결(직접연결)을 통한 노드 간의 정보 전송을 가능케함.
• 데이터 단위 "프레임"
• 이더넷 프레임을 통해서 에러 확인, 흐름 제어, 접근 제어를 담당.
• Physical 계층에서 오는 정보를 관리하고 '안전'하게 전달되도록 도와주는 역할
• MAC 주소를 통해 통신함.
• bridge, switch 등의 장비가 있다.

  L3 Network 계층

• IP, ARP, ICMP등의 프로토콜이 있음.
• 라우팅 기능을 맡고 있는 계층으로 목적지까지 가장 안전하고 빠르게 갈 수 있는 길을 설정하는 기능을 가지고 있음.
• 호스트 간의 통신에 관한 역할을 담당.
• 우리가 자주 말하는 IP주소가 네트워크 계층의 헤더
• 네트워크 계층에서의 데이터 단위 "패킷"
• 라우터, L3 스위치 등의 장비가 있다.

L4 Transport 계층

• TCP, UDP 등의 프로토콜이 속함.
• 프로세스들 간의 데이터 전송, 통신에 관한 역할을 담당.
• 종단 시스템에서만 구현된다.(사이 사이에 있는 라우터 이런 친구들은 네트워크 계층까지만 있음.)
• 데이터의 용량, 속도, 목적지 등을 처리함.
• 데이터 전송을 위해 PORT 번호를 사용함.
• 데이터 단위는 세그먼트(데이터그램이나 패킷)
• L4 스위치(TCP, UDP 프로토콜의 헤더를 보고 스위칭, ip와 포트 기반이다.)

L5 Session 계층

• 데이터가 통신하기 위한 논리적 연결 담당.
• 실제 네트워크 연결이 이루어진다.
• L4가지는 데이터를 전달하는 것이 주 목적이라면 여기부터는 프레세스들 간의 통신 프로토콜이다!
• 연결을 유지, 확립, 중단, 복구 등의 역할을 한다.

L6 Presentation Layer

• 데이터를 어떻게 표현할 지 정하는 역할을 하는 계층
• 파일 인코딩, 데이터 암호화/복호화

L7 Application Layer

• HTTP, FTP, DNS 등등의 프로토콜이 속함
• 유저가 접하는 Interface 역할을 함
• 최 앞단의 서비스
• L7 스위치(로드밸런서)(URL, 서버, 캐시, 쿠키 기반으로 트래픽 분산 역할을 한다.) 장비가 속한다.

TCP/IP 4계층

TCP/IP 4계층은 이러한 OSI7 계층과 비슷하면 계층 수로만 보면 좀 더 단순하다고 볼 수 있다. 이러한 TCP/IP의 각 계층은 아래와 같다.

L1 Link 계층

OSI 7계층에서 physical + data link를 한 계층이다.

L2 Internet 계층

OSI 7계층 중 Network 계층에 해당한다. 동일하게 IP주소를 통해 목적지까지 가는 경로를 설정한다(라우터 이용)

L3 Transport 계층

OSI 7계층 중 동일한 이름인 Transport 계층과 같으며, TCP혹은 UDP 프로토콜을 통해서 연결 방식을 설정하고, 발신지와 목적지를 정하게 되며, 데이터의 용량, 속도 등을 처리하게 된다.

L4 Application 계층

OSI의 application, presentation, session을 합쳐서 TCP/IP 4계층 에서는 Application 계층이라고 칭한다.

이어서 Graph, Tree, Heap, Priority Queue을 알아보자.

Graph

Graph는 Node와 Edge로 이루어져 있다. 간단히 설명하자면 점(Node)과 선(Edge)으로 그려진 지도같은 형태이며 점과 점을 선으로 잇고 있는 형태이다. Edge는 방향성을 지닐 수 있으며, 가중치 또한 가질 수 있다. 여기서 가중치란 Edge의 비용이라고 이해해도 된다.

사실 Graph 자체도 직접 구현해볼 수 있으나 실제적으로 자주 사용되는 것은 Graph 중 Tree이기에 Tree로 바로 넘어가본다.

Tree

Graph의 일종이며 Node와 Edge로 이뤄어져 있으며 tree 구조로 배열된 계층적 데이터 구조이다.

기본 개념

• parent node: 연결된 두 node 중 edge가 시작되는(출발하는)쪽 node
• child node: 연결된 두 node 중 edge가 끝나는 쪽 node
• root node : tree의 시작이 되는 node이며 parent node를 갖지 않는다.
• leaf node : node들 중 child node를 갖지 않는 node를 말한다.
• tree의 height : tree에서 leaf node들 까지의 거리 중 가장 먼 것을 의미한다.
• node의 depth : root node에서 해당 node까지 edge의 갯수를 의미한다.
• node의 level : 특정 depth를 갖는 node의 집합

이진 트리(binary-tree)

tree들 중 가장 일반적인 것이 이진 트리 입니다. 특징으로는 각 node는 child를 최대 2개까지만 가질 수 있습니다.

이진 트리의 종류

• full binary tree(정이진 트리) : 노드의 자식이 0 or 2개인 것
• complete binary tree(완전 이진 트리) : 마지막 level을 제외하고는 node가 꽉 차 있으며, 마지막 level의 경우 왼쪽부터 채워지는 트리. Heap 자료 구조가 이를 사용한다.
• perfect binary tree(포화 이진 트리) : 모든 노드가 꽉 차 있는 이진 트리이다.
• balanced binary tree(균형 이진 트리) : 왼쪽과 오른쪽 노드의 높이가 1이하인 트리. AVL tree, Red-Black tree가 이를 이용한다.(두 개 다 잘 알지는 못한다...)
• binary serach tree(이진 탐색 트리) : 각 노드의 왼쪽 하위 트리에는 node보다 작은 값들이, 오른쪽 하위 트리에는 node보다 큰 값들이 있다.

간단한 이진 트리 구현

data class Node(
    var value: Int, 
    var left: Node? = null,
    var right: Node? = null
)
data class Tree(val root: Node)

fun main() {
    val a = Node(1)
    val b = Node(2)
    val t = Tree(a)
    a.right = b
    println(t.root.right?.value)
}

Tree traversal(트리 순회)

• preorder : Root 먼저 탑색
• inorder : Root는 중간에 탐색
• postorder : Root는 마지막에 탐색
• level-order : 같은 레벨 먼저 탐색

참고자료

https://medium.com/depayse/kotlin-data-structure-tree-b8518d233f9d

Heap

complete binary tree를 기반의 자료구조 이며, 최소힙과 최대힙 두가지고 있고 해당 힙에 따라 특정한 특징을 지킨 트리이다. 최대힙의 경우 각 node의 값은 모든 자신의 자식들 중 가장 커야 하며, 각각의 자식 node들에 대해서도 재귀적으로 같은 규칙이 적용되어야 한다. 최소힙의 경우 그 반대이다.

Heap에서의 삽입

최대힙의 가정하고 설명한다.

1. Heap은 complete binary tree 기반이므로 마지막 노드의 위치에 새 요소를 넣는다.
2. 자신의 부모 node와 비교하여 더 클 경우 값을 교체한다.
3. 자신의 부모 node보다 작아질 때 까지 이를 반복한다.

Heap에서의 삭제

최대값을 제거하는 경우이다.

1. 최대값을 나타내는 root node의 값을 삭제한다.
2. 마지막 node의 값을 root node로 옮기고 마지막 node 제거
3. root node의 두 child node중 더 큰 쪽과 현재 root node의 값을 비교하여 heap의 규칙을 맞춰준다.
4. 이를 반복적으로 시행한다.

in kotlin

kotlin에서는 따로 Heap을 제공하지 않는다. 그 대신 다른 방식으로 Heap을 만나볼 수 있다. 이는 바로 priority queue이다.

Priority Queue

우선순위 큐이며 기본 queue의 경우 FIFO를 따르지만, priority queue의 경우 우선순위가 높은 요소가 가장 먼저 제공된다. 이 priority queue가 Heap을 기반으로 구현된다.

in kotlin

kotlin의 priority queue의 경우 element Type에 compareTo가 정의되어 있지 않으면 comparator를 제공해줘야 한다. 그렇지 않은 경우라도 custom comparator를 제공해 줄 수 있다.

import java.util.*

val a = PriorityQueue<Int>() 

a.addAll(arrayOf(1,6,3,8,0,4))
a.offer(11)

println(a.peek()) // 11
println(a.poll()) // 11


val b = PriorityQueue<String>() { a, b -> 
    a.length.compareTo(b.length)
}

b.addAll(arrayOf("sdf", "123123", "23424", "z"))
println(b) // [z, sdf, 23424, 123123]

지난 번에 이어 이번에 stack과 queue를 알아보자. 해당 개념들은 과거에 한번씩 다뤘었기에 개념보단 kotlin에서의 실 활용에 초점을 맞춰본다.

Stack

stack은 재귀적인 함수나, 알고리즘에서 자주 사용된다. LIFO(last in first out)의 성질을 가진 자료구조이며 삽입, 삭제는 O(1), 검색에 O(n)이 걸린다.

in kotlin

import java.util.*

val s = Stack<Int>()
s.push(3)
s.push(4)
s.push(5)
println(s) // [3,4,5]
println(s.peek()) // 5
println(s.pop()) // 5
println(s) // [3,4]

• push : stack의 맨 위에 값을 넣는다
• pop : stack의 맨 위에서 값을 뺀다
• peek : stack의 맨 위 값을 확인한다.

활용

문자열 역순 출력 등 뒤집기

Queue

Queue는 FIFO(First in First Out)이라는 Stack과는 다른 성질을 지녔다. 일반적으로 줄서기 라고 생각하면 이해가 편하다. 삽입과 삭제에는 O(1)이, 검색에는 O(n)이 걸린다.

in kotlin

kotlin에서 queue는 interface 일 뿐 클래스가 아니다. 따라서 LinkedList를 통해 initialize 해준다.

import java.util.*

val q: Queue<Int> = LinkedList()

q.add(1) // 에러 발생시 Throw Exception
q.offer(2) // 

q.element() // 1 에러 발생 시 Throw Exception
q.peek() // 1 , 가장 앞에 있는 값 확인, 에러 발생시 null return

q.remove() // 1, 에러 발생시 Throw Exception
q.poll() // 2, 에러 발생시 null return

위에서 보이듯 두 method씩 각각 같은 역할을 하나 에러 발생시의 처리가 다르다. 여기서 add는 원래 capacity가 부족할 경우 exception을 발생시키나, LinkedList()를 통해 만든 queue의 경우 해당 이슈는 발생할 가능성이 거의 없다.

활용

프로세스의 스케줄링 (먼저 들어온 것 부터), 줄서기, BFS 등

과거 파이썬을 공부 할 때 자료구조를 파이썬 기반으로 공부를 했었다. 복습하는 차원에서 Kotlin으로 관련 method들을 알아보고, 또 필요한 경우 직접 구현해보며 공부해보자

Array

array는 같은 타입의 변수들로 이루어져 있고, 일반적으론 크기가 정해져있다.

• 접근 O(1) thanks to Random Access
• 검색 O(n)
• 삭제, 추가 O(n)

인덱스로 원소에 빠르게 접근해야 할 때 유용.

use in kotlin

## initialize
val a = arrayOf(1,3,4)
val b = (3..10).toList().toTypedArray() // Array<T> 형태로 변경
val c = intArrayOf(3,4,5)
val d = Array(4) { i -> i*3 } // [0, 3, 6, 9]

## basic operations
a[2] // 4
b.get(1) // 4
c.set(3, 11)
c[3] // 11
a.first()
a.last()
a.lastIndex
a.size

## 원소 추가, 새로운 array를 만들어야함
var e = a.plus(10)

## array slice, 
val d = a.sliceArray(4..5) //[6,6]

Collections

Kotlin에서는 읽기전용 Collection과 변경 가능한 Mutable Collection을 구분하고 있다. 일반적으로 add, addAll, remove, removeAll, retainAll, clear는 Mutable Collection에서 사용할 수 있으며, contains, containsAll, isEmpty, iterator, size 등은 상관없이 사용 가능하다.

List (일반)

중복을 허용하며 순서대로 자료를 보관한다. Kotlin에서는 immutable 하기 때문에 값 추가나 변경은 불가능하다.

• 접근 O(n)
• 검색 O(n)

ArrayList

배열을 기반으로 데이터를 관리하지만, array와 달리 크기가 고정되어 있지 않다. 공식 문서를 보면 RandomAccess가 되는 MutableList이다~ 라는 것을 알 수 있다. index를 통한 접근에 많이 필요할 때 좋다.

in Kotlin

kotlin에서는 mutableListOf()의 기본 구현이 ArrayList이다.

val a = arrayListOf(3,4,5)
a.add(3)
a.remove(4) 

Time Complexity

• 접근 O(1) : array를 기반으로 구성되기에 random access가 가능하다.
• 검색 O(n)
• 삭제 O(n)
• 추가 O(1) or O(n) : array size가 남아있으면 1 아니면 n

LinkedList

LinkedList는 데이터(value)와, 다음 데이터의 주소(next)를 갖는 Node들을 연결하여 데이터를 관리한다. 맨 앞이나 맨 뒤에 데이터를 추가하거나 제거할때 유용하게 사용된다.

in Kotlin

일반적으로 LinkedList를 단방향을 의미하지만 Kotlin에서는 DLL(Double LinkedList)이기 때문에 양방향이다.

val a = LinkedList<Int>()

a.add(3)
a.addFirst(5)
a.addLast(7)
println(a)

time complexity

• 접근 O(n)
• 추가, 삭제 O(1) or O(n) : 맨 앞 or 맨 뒤의 경우 1 아니면 n
• 검색 O(n)

Set

중복을 허용하지 않는 Collection이다. 순서가 없다는 것이 특징이다.

in kotlin

val a = setOf<Int>(3,4,6)
val b = setOf<Int>(6,4,3)

a.contain(3)
b.add(5)

time complexity

HashSet을 통해 구현되어 추가, 삭제, 검색 모두 O(1)이다.

Map

key: value 형태로 저장하는 collection이다. key가 unique 하며, python에서 dictionary를 생각하면 된다.

in kotlin

kotlin에서는

val a = mapOf<String, Int>("1" to 1, "2" to 2, "3" to 3)
val b = mutableMapOf<String ,Int>()
a.get("1")
a["1"]
a.values
a.keys
b["3"] = 6

time complexity

kotlin에서는 mutableMapOf()를 하면 MutableMap은 interface 이기에 HashMap을 통해 구현이 되어 있다. 찾아보는 바에 의하면 HashMap의 storing(저장)과 retrieving(읽기) 모두 O(1)로 보인다.

마무리

간단하게 Array와 Kotlin의 Collection 들을 알아보았다. 가볍게 훑어보았다 정도로 기억해두자.

지난 글에서는 EC2를 이용해서 서버를 올리는 작업을 진행했었다. 이번에는 서버에서 docker로 구성했던 db를 RDS에 올려보려고 한다.

AWS RDS에 DB 올리기

Amazon RDS란

Amazon RDS(Amazon Relational Database Service)는 클라우드 상에서 손쉽게 DB를 설치, 운영, 확장할 수 있는 서비스를 말한다.

공식 사이트 이번 목표는 이 RDS 서비스를 이용해 내 프로젝트 내의 mysql을 운영하는 것이다.

RDS Instance 생성하기

1. AWS에서 RDS 서비스를 선택해서 들어간다.

2. 데이터베이스 생성 선택

3. MySql 8.0.31을 선택하고 프리티어 선택

4. DB 인스턴스 식별자는 말 그대로 그냥 인스턴스 이름을 설정하는 거다. 이에 더해 마스터 사용자 이름, 마스터 암호는 DB의 user와 password를 설정하는 것이다. 자신에 맞춰 설정하고 기억해두자.

5. 스토리지는 범용 SSD로 최소 값인 20GB로 설정한다.

6. 연결탭이다. 나는 앞선 글에서 EC2 Instance를 켜뒀기 때문에 해당 Instance에 연결해줘야 한다. 연결 탭에서 EC2 컴퓨팅 리소스에 연결을 선택하고 아래에서 해당 인스턴스를 선택하면 알아서 연결을 해준다!! (보안 그룹까지 다!)

7. 꼭 빼먹지 말고 추가 구성에서 DB 이름을 지정해주자. 이를 지정해야 DB가 생긴다.

코드 수정을 통한 RDS 연결

자신의 RDS Instance에 들어가보면 DB endpoint가 나온다. 이를 이용해서 셋팅을 해줘야 한다.

그를 위해 여러 파일들을 수정해주자

application.yml, application-db.yml

우선 datasource 관련 코드를 따로 파일을 빼서 정해주자. 그 이유는 내 RDS 계정과 endpoint가 나오기 때문에 따로 빼서 작성해주자

## application-db.yml
spring:
  datasource:
    url: jdbc:mysql://[자기 ENDPOINT]:3306/[자기 DB 이름]?useUnicode=true&characterEncoding=UTF-8
    driver-class-name: com.mysql.cj.jdbc.Driver
    username: [RDS ID]
    password: [RDS PASSWORD]

## application.yml
## 기존에 있던 spring: 하위의 datasource:를 전부 제거해주자.
## 또 db를 include 해주자.
spring:
    ~~
    profiles:
        ~~
        - db     

docker-compose.yml, .env

기존에 docker에 있던 mysql container도 제거해줘야 한다. 코드에서 db-mysql 파트를 싹 드러내주자. 그리고 하단 command 에서 db-mysql 대신 RDS endpoint를 적어주자. 수정한 결과물은 아래와 같다.

## docker-compose.yml
version: "3.8"

services:
  app:
    container_name: app
    build:
      context: ./
      dockerfile: Dockerfile
    ports:
      - 8080:8080
    command:
      - bash
      - -c
      - |
        ./wait-for-it.sh ${MYSQL_HOST_ENDPOINT}:3306 -s -t 100
        java -jar /app.jar


## .env
MYSQL_HOST_ENDPOINT=[자기 RDS Endpoint]

.gitignore

잊지 말고 .gitignore에 .env 파일과 application-db.yml을 추가해주자.

여기까지 작업을 맞춘 후 github에 push 해주자.

EC2에서 서버 새로 빌드하기

먼저 EC2 Instance에 접속해주자. -> ssh heyday-howwasyourday 그 후 git pull을 통해서 수정사항을 받아오고, instance 내부 프로젝트에도 .env와 application-db.yml 파일을 수동으로 추가해주자.

그 후 기존 빌드 파일과, docker-container를 깔끔하게 날리고 다시 서버를 켜주면 !! 성공적으로 서버가 켜진 것을 볼 수 있다. ㅎㅎ

성공적으로 서버가 켜진 것을 보고 난 후에 AWS RDS Instance에 들어가보자. 그러면 아래와 같이 현재 활동에 없던 연결이 생긴걸 확인할 수 있다.

마무리

이렇게 DB까지 RDS를 통해서 키는 작업을 마무리했다. 다음 스텝으로는 빌드 자동화를 구축하는 것이다. Github Action을 통해서 이뤄낼 수 있을 것이라 보이고, 이 자동화까지 하면 github master branch에 merge 하는 걸로 배포를 할 수 있게 만드려 한다.

지난 글까지 작업하여 docker-compose.yml을 통해서 "How-was-your-day" 프로젝트 서버를 키는 것 까지 완료하였다. 이번엔 컴퓨터가 아닌 AWS의 EC2 instance를 통해 서버를 배포해본다.

AWS를 통해 서버 배포하기

우선 이번 작업을 진행하며 참고한 블로그나 글들이 꽤나 많다. 각 작업들 마다 도움이 된 글들을 남겨두겠다.

AWS EC2 Instance 생성 및 설정하기

해당 파트는 https://bcp0109.tistory.com/356 글을 메인으로 참고했다.

위 티스토리 글을 메인으로 하여 진행했다. 굉장히 자세히 소개를 해주고 있어 매우 도움이 되었다. 해당 글과 다르게 진행한 부분만 정리해둔다. 이에 더불어 이 과정에서 겪은 많은 삽질과 해결들을 기록해둔다.

EC2 인스턴스 생성

• AMI은 Ubuntu 22.04를 선택했다.
• 인스턴스 유형 또한 프리티어인 t2.micro를 선택했다.

탄력적 IP

설명이 잘 나와있어 생략한다.

SSH 클라이언트로 서버 접속하기

SSH 키 설정을 해두니 확실히 편했다.

로컬 컴퓨터의 config 파일을 통해 Host 설정을 해두면 쉽게 서버에 들어갈 수 있다.

보안 그룹 설정

보안그룹의 경우 쉽게 말해 외부에서의 접근, 혹은 외부로의 접근에 있어 허용된 IP에서만 가능하도록 설정하는 것이다. "인바운드"의 경우 해당 인스턴스로 접근 하는 것이기에 자신에 맞춰 설정하면 되고 "아웃바운드"의 경우는 특별한 이슈가 없다면 기본 생성되는 "모든 트래픽"을 그대로 두면 된다.

Instance에서 프로젝트 서버를 켜기

위에서 설정한 Instance에 호스트를 통해 접속해보자. 그리고 내부에 필요한 것들을 설치하고 설정해보자.

ssh [자신의 호스트]

java 설치하기

sudo apt update
sudo apt install openjdk-17-jdk-headless

이렇게 자바를 설치하고 후에 혹시 아래 사진과 같은 에러가 gradle build시 발생한다면 다음 코드를 해보는 것을 추천한다. 이 에러는 인증서 관련 오류로 보이는데 열심히 찾아봐도 해결법이 잘 나오지 않았다. 그러다 아주 고마운 분의 stackoverflow 답글을 찾았다.

sudo dpkg --purge --force-depends ca-certificates-java
sudo apt install ca-certificates-java

요약하자면 Ubuntu machine에서 java 설치시 ca-ceertificates-java가 제대로 설치가 안되었을수 있으니 지우고 새로 깔아봐라~~ 이런 것이다. 이 분 덕분에 1시간 넘게 삽질하다 겨우 해결할 수 있었다.

Github 설치 및 git clone 해오기

이 파트는 해당 글을 참고하였다. 사실 기본 데스크탑에서도 github을 사용할 때 맨 처음 진행하는 과정이기 때문에 별로 어렵지 않게 진행할 수 있을 것이다.

Docker 및 docker-compose 설치

이 두가지 블로그 글을 추천한다.

• Docker 설치 및 설정
• docker-compose 설치(하단 docker-compose 파트만 참고)

이 파트에서 살짝 헤맸??는데 apt-get 대신에 apt를 적어서 진행했다.

첫 번째 글 처럼 instance에서 docker를 서비스에 등록해서 켜주면 준비 완료이다.

!!중요 프로젝트 키기

이제 기본적인 준비가 되었으니 프로젝트를 켜보자. 지난 글에서 docker-compose를 통해 작업을 끝마쳐두었으니 docker-compose를 통해서 켜주면 된다.

.jar 파일을 만들기

./gradlew assemble

여기서 gradlew 권한 오류가 발생할 수 있다. 그럴 땐 chmod +x graldew로 권한을 부여해주자.

docker-compose로 프로젝트 시작하기

docker-compose up

해당 command를 입력해주면 지난 글에서 봤던 것처럼 mysql 이미지를 받아오고, image를 만들고 container를 실행시켜준다. 이 과정에 오류없이 진행되었다면 의도한 대로 프로젝트 서버가 켜진 것이다.

다만 나는 이 과정에서 변수를 만났다. 읽어보니 OAuth 관련 설정이 미쳐 완료되지 않았다는 것이었다. 원인은 간단했다. google oauth 설정을 하며 따로 .gitignore에 빼뒀던 application-oauth.properties 파일을 추가해주지 않았기 때문이었다. 따라서 아래와 같은 방식으로 추가해주었다.

application-oauth.properties 추가하기(.gitignore에 넣어둔 보안이 필요한 파일 추가하기)

## clone한 자신의 프로젝트 위치로 이동.
cd how-was-your-day
cd src/main/resource
vim application-oauth.properties

vim을 통해서 해당 파일을 만들어주고 그 이후 a를 눌러 입력모드로 바꾸고, 넣어야 하는 파일의 내용을 복사해서 넣어준다. 그 후에 :wq를 통해서 쓰고 완료한다.

[추가 조언] docker-compose를 하는데 변경이 적용 안되는 것 같을 때 해결법

빠뜨렸던 properties 파일도 다시 추가했고, 이제 에러들도 해결한 거 같은데 그대로 에러가 뜰 때, 그럴 때 간과하고 있는것이 하나 있다. 바로 cache다. docker-compose에서도 cache 기능을 제공한다. 이 cache 때문에 수정을 했는데도 기존과 동일한 이미지가 만들어져서 수정이 제대로 되지 않은것이라는 착각과 함께 많은 시간을 허비하게 한다.

docker-compose build --no-cache

이 --no-cache를 옵션을 통해서 cache 없이 build를 진행하면 변경사항이 적용되어 있을 것이다.

Domain 구매해서 AWS Route 53으로 연결하기

마지막 스텝은 Domain을 사서 인스턴스 IP와 연결하는 것이다. 우리가 접속하는 거의 모든 website들은 이런식으로 도메인 주소를 사서 거기에 해당 port를 연결해두는 것이다. 그렇지 않는다면 우리는 모두 naver.com이 아니라 153.674.123.67(하나의 예시일뿐이다 ㅎㅎ)와 같은 주소로 접속을 하고 있을 것이다.

이 작업은 해당 글을 참고했다. 나는 가비아에서 도메인을 구매해서 연결했다.

어렵지 않고 따라하기만 하면 되니 넘어간다.

[추가] AWS SWAP Memory 설정하기

이 파트도 추가해둔다. 이를 찾아보게 된 이유는 instance 서버가 자꾸 죽어서이다. 접속을 해서 진행을 하는데 어쩌다 한번씩 자기 혼자 동작을 멈췄다. 이상해서 검색을 해보니 free tier로 사용하게 되면 Memory가 1GB 밖에 되지 않아서 서버 하나만 켜도 힘들어 한다는 것이었다.

AWS 공식 SWAP memory guide

공식 가이드를 보고 따라해도 좋고 내가 참고한 블로그 까지 적어두니 편한 것을 선택해서 하면 되겠다.

이것까지 하고 나면 잘 돌아가는 서버를 볼 수 있다.

결과물

여러 많은 글들을 참고하면서 결국 성공했다. 그 결과물은 다음과 같다. 꽤나 행복하다. 내가 산 howwasyourday.site 주소로 접속이 잘 되니 말이다.

마무리

이렇게 AWS EC2를 통해 배포를 마무리했고, 성공적으로 뜨는 것 까지 확인을 했다. 이제 다음 스텝은 DB를 AWS로 올려 보는 것과 배포 자동화를 구축하는 것이다. DB의 경우 아직 상세한 지식은 없으나 아마 RDS를 통해서 하는 것을 보인다. 끝까지 화이팅이다.

지난 글에서 Dockerfile로 프로젝트 구성을 했던 것에서 한번 더 업그레이드해서 docker-compose로 구성해봅니다.

docker-compose로 구성하기

docker-compose를 사용하는 이유는 지난 글에서 docker를 설정하던 걸 기억해보면 된다. 그 때는 docker image를 만들고 계속해서 직접 container를 run 하는 command를 적었어야 했다. docker-compose를 사용하면 이런 것을 자동화할 수 있다.

docker-compose.yml

docker-compose 파일은 아래와 같다.

version: "3.8"

services:
  db-mysql:
    image: mysql:8.0
    hostname: db-mysql
    container_name: db-mysql
    environment:
      MYSQL_DATABASE: mydb
      MYSQL_USER: spring
      MYSQL_PASSWORD: spring
      MYSQL_ALLOW_EMPTY_PASSWORD: "yes"
    ports:
      - 3306:3306
    volumes:
      - ./db:/var/lib/mysql
  app:
    container_name: app
    build:
      context: ./
      dockerfile: Dockerfile
    ports:
      - 8080:8080
    depends_on:
      - db-mysql
    command:
      - bash
      - -c
      - |
        ./wait-for-it.sh db-mysql:3306 -s -t 100
        java -jar /app.jar

• version : docker-compose 버전

• services : 하위에 여러 container를 선언

• db-mysql image : db image 설정 environment : 환경변수 설정 volumes : db volume 설정을 통해서 container가 down 되었다가 켜져도 db를 유지

• app build : 하위 dockerfile을 통해 Dockerfile설정 depends_on : docker-compose 제공 설정으로 설정한 service보다 container "시작"을 이후에 하는걸 보장함. 여기서 "시작"을 이후에 하는 것만 보장하기에 db-mysql이 완벽히 initialize 되는 것을 보장하지는 않음. command : 이후 코드는 아래에서 재설명

wait-for-it.sh

앞서서 나온 depends_on 설정의 한계를 극복하기 위해서 같이 사용하는 것이다. depends_on이 container의 "시작" 만을 보장해주기 때문에 이 wait-for-it.sh를 사용하여 이를 극복해준다.

실제로 depends_on만을 믿고 돌리면 spring app 이 시작되면서 mysql server가 켜지기전에 db 연결을 시도해서 spring server가 죽어버린다.

먼저 이 github으로 들어가서 [wait-for-it.sh github] (https://github.com/vishnubob/wait-for-it) wait-for-it.sh 파일을 다운받는다. 그리고 해당 파일을 Dockerfile과 같은 경로에 둔다. Dockerfile을 아래와 같이 수정한다.

ARG JAR_FILE=build/libs/*.jar
COPY ${JAR_FILE} app.jar

# wait-for-it.sh
RUN apk update && apk add bash
COPY wait-for-it.sh wait-for-it.sh
RUN chmod +x wait-for-it.sh

"# wait-for-it.sh"아래에 있는 코드가 새롭게 추가한 것이다. bash를 추가하고, COPY를 통해서 wait-for-it.sh를 추가한다. 그리고 chmod를 통해서 권한을 부여해준다.

적용 command 설명

그리고는 docker-compose.yml에 command 이후를 다시 들여다보자.

~~~ 
command :
    - bash
    - -c
    - |
      ./wait-for-it.sh db-mysql:3306 -s -t 100
      java -jar /app.jar

1. bash 실행

2. -c : 이후 실행

3. ./wait-for-it.sh db-mysql:3306 -s -t 100 wait-for-it 스크립트 실행, db-mysql:3306(호스트:포트)가 실행되는 것을 100초간 기다림 (세세한 설정은 위 깃헙 참고)(-s 옵션은 해당 포트가 준비되어야 그 다음 실행)

4. java -jar /app.jar : 기존의 Dockerfile의 ENTRYPOINT 에 있던 코드를 뺀 것으로 jar 파일을 실행한다.

실행로그

docker-compose up을 terminal에 실행하면 이미지 빌드부터 container 실행까지 한번에 된다.

사진의 4번 줄에서 보이듯 100초간 port가 준비되는 것을 기다려준다. 그 후 port가 준비되면 spring boot project가 시작된다.

마치며

docker-compose까지 작업을 마치게되었다. docker-compose up을 누르고 서버가 착착 켜지는걸 보니 기분이 꽤나 좋다. 프로젝트 코드 자체는 가소로울 수 있지만, 의미있는 작업을 한거 같다.

이 다음으로는 프로젝트를 배포까지 해보려고 한다.

시작하며

전 글에서 언급했듯이 프로젝트를 Docker container 화 시키는 과정과 그 과정에서 겪었던 여러 이슈들을 기록해둔다.

Dockerize 하기

Docker

docker는 간단히 말하면 컨테이너 방식을 통해서 프로젝트(애플리케이션)을 구축하고, 배포할 수 있게 해주는 플랫폼이라고 할 수 있다. Docker의 경우 여러 공식 문제나 잘 설명되어 있는 글들이 많다. https://www.docker.com/resources/what-container/ https://aws.amazon.com/ko/docker/

그 중에서도 하나 가장 강력한 무기라고 생각되는 점은 docker container가 라이브러리, 코드 등 애플리케이션에 포함된 모든 것들을 포함하여 환경에 구애받지 않고 항상 동일한 애플리케이션을 돌릴 수 있다는 것이다.

Docker 설치

이 작업을 하기전에 먼저 컴퓨터(노트북)에 Docker를 깔아주자. https://www.docker.com/products/docker-desktop/ desktop용으로 무료로 받을 수 있기 때문에 이를 먼저 설치해주자.

application.yml으로 변경 및 Dockerfile 작성

application.yml

우선 기존의 application.properties를 application.yml 파일로 수정해주면서 여러 설정 값들도 추가해준다.

spring:
  datasource:
    url: jdbc:mysql://db-mysql:3306/mydb?useUnicode=true&characterEncoding=UTF-8
    driver-class-name: com.mysql.cj.jdbc.Driver
    username: spring
    password: spring
  jpa:
    database-platform: org.hibernate.dialect.MySQL8Dialect
    hibernate:
      ddl-auto: update
    show-sql: true
    properties:
      hibernate:
        format_sql: true
  profiles:
    include: oauth
server:
  servlet:
    encoding:
      charset: UTF-8
      force-response: 'true'

간단히 설명을 넣는다.

• spring:datasource: -> DB에 대한 설정이 나온다. url에서 "db-mysql"은 db conatiner 이름이며, mydb가 database 이름이다. 한글 사용을 위해 unicode, encoding 관련 값을 넣어주었다.

• jpa:database-platform: -> 후에 작업을 하다 hibernate.dialect 설정이 되어있지 않다는 error를 보고 추가해주었다. 나는 mysql8.0을 쓰기에 해당 버전에 맞는 dialect를 설정해주었다.

• jpa:hibernate:ddl-auto: -> 나는 우선 프로젝트 개발 진행중이기 때문에 update로 둔다(이 옵션은 DB schema 변환이 있을 때 어떻게 처리하는가이다.)

• jpa:show-sql -> sql log가 보이도록 해준다

• jpa:properties:hiberante:format_sql -> sql이 이쁘게 보이게 해준다.

• profiles:include: oauth -> 이는 oauth용으로 만들어둔 properties 파일을 읽는 용도임으로 그렇게 중요하지는 않다.

Dockerfile

사실 docker file 자체는 아직 별게 없다.

FROM openjdk:17-alpine

ARG JAR_FILE=build/libs/*.jar
COPY ${JAR_FILE} app.jar
ENTRYPOINT ["java", "-jar", "/app.jar"]

• FROM : base 이미지를 설정하는 명령이며 꼭 있어야 하는 명령이다. 나는 17버전의 openjdk:17-alpine을 사용했다.
• ARG : 인자를 정해두는 것이며 = 을 통해 default 값을 설정해준다. 여기서는 gradle을 사용하므로 build 시 .jar이 생기는 build/libs 경로를 넣어준다.
• COPY : 파일이나 디렉토리를 이미지 내부 경로로 복사한다. 여기서는 .jar 실행파일을 app.jar로 복사한다~ 이런 의미이다.
• ENTRYPOINT : 빌드한 이미지를 컨테이너로 생성할때 실행되는 명령어. 여기서는 java jar을 실행하기 위한 명령어가 들어가있다.

이렇게까지막 적어도 별 어려움 없이 dockerfile 작성이 끝이난 것이다.

Docker container 화

우선 본 프로젝트에서는 mysql과 spring 코드 두 개를 container로 올려야 한다. 먼저 mysql을 해보자

무엇인가가 안된다면 Docker가 켜져있는지 우선 확인해보자 ㅎㅎ

network 만들기

docker 에서 container들 끼리 서로 통신을 할 때는 Docker network를 통해 수행한다. 아직 자세히는 알지 못하지만, 나는 DB와 프로젝트가 통신을 해야 하므로 이를 추가해주자

docker network create how-was-your-day-net

mysql container로 올리기

우선 mysql 이미지를 받아오자.

docker pull mysql:8.0

그 후 셋팅을 하며 container를 생성하고 실행해보자

docker run -p 3306:3306 --name db-mysql --network how-was-your-day-net -e MYSQL_ROOT_PASSWORD=root -e MYSQL_DATABASE=mydb -e MYSQL_USER=spring -e MYSQL_PASSWORD=spring -d mysql:8.0

관련 설명은 아래와 같다.

• --name: 컨테이너 이름 설정
• --network: 네트워크 연결 설정
• -p: 포트 설정
• -e: 환경변수 설정
• -d: 백그라운드로 컨테이너 실행

spring app container로 올리기

실행 파일을 먼저 만들어줘야 한다. 그 이전에 build 했던 결과물들이 있을 수 있기에 우선 이를 지우고 새로 만들어주자

## 여기서 그냥 gradle을 사용해도 되긴 한다.
./gradlew clean 
## assemble은 실행 없이 build 파일 작성
./gradlew asseble

그리고서 docker image를 만들어주자

docker build -t how-was-your-day:1.0 .

• -t: name:tag 식으로 설정.
• 맨 뒤에 온점을 잊지 말자

이미지를 만들었으면 이를 이용해서 이제 container로 올려주면 된다.

docker run -p 8080:8080 --name how-was-your-day --network how-was-your-day-net -d how-was-your-day:1.0

결과 확인

우선 terminal에서 별다른 문제 없이 돌아갔다면 docker desktop 앱을 들어가보자. 아래와 같이 images와 containers 탭에서 정상적으로 돌아가고 있다면 성공이다.

에러 처리

하지만 나도 이 과정을 처음부터 성공해내지는 못했다. 여러 힘든 점을 겪었기에 이를 처리했던 방식들을 짧게나마 남겨둔다.

3306 포트 점유 이슈

처음에 mysql container를 올리려고 할 때 마주할 수 있는 에러이다. 나는 서버를 킨 적이 없는데 3306 포트를 누가 점유하고 있다~ 라고 나온다. 이럴 땐 한번 포트 점유 체크를 해주자. cmd를 켜서 netstat -ano를 쳐주면 현재 사용중인 포트들이 나온다. 그 중에서 3306 포트가 사용중인지를 확인하고 그 pid를 체크하자. 그리고는 taskkill /f /pid [확인한pid]를 해주면 된다. 이 명령이 오류가 난다면 작업관리자를 들어가서 이름에서 우클릭을 해서 pid를 체크해 pid가 보이게 하고, 해당 pid를 직접 찾아서 종료해주면 된다.

mysql 한글 이슈...(윈도우 기준)

container 두 개가 다 켜졌고, localhost:8080에도 잘 접속이 되었다고 치자. 근데 왠걸 db와 통신하는 작업을 하자마자 에러 로그가 파파박 찍힌다. 근데 로그를 확인하니 아래와 같이 java.sql.SQLException: Incorrect string value: '\xEA\xB3\xA0\xED\x83\x9C...' for column 'name' at row 1 한글이 깨진 것과 같은 표현이 뜰 때가 있다. 이때는 mysql에 설정을 바꿔주어야 한다.

1. application.yml에서 db url 뒤에 useUnicode=true&characterEncoding=UTF-8를 추가해보기

이럼에도 안되는 경우가 있을 것이다. 나도 그러했다. 그렇다면 다음으로 넘어간다.

2. 우선 mysql을 접속해서 show variables like 'c%' 명령을 친다. 그러면 아래로 변수들이 촤라라 펼쳐질텐데, character_set 관련 값들을 보면 아마 utf8, utf8mb3 등이 아닌 latin1과 같은 값들로 설정되어 있을 것이다.

3. 실행창에서 서비스를 검색하고 들어가 mysql 을 찾아 중지해준다.

4. utf8 설정을 위해서 /ProgramData/MySQL/MySQL Server 8.0에 있는 my.ini 파일을 수정해야 한다. 만약 수정권한이 없다면 파일의 속성/보안/편집을 가서 user에게 권한을 부여하기를 바란다. my.ini를 키고 아래와 같은 값들을 넣는다. (여기서 []로 되어 있는 것들은 아마 미리 입력되어 있을 것이기에 그 아래 적힌 코드를 해당 위치에 추가해주면된다.)

   [client]
   default-character-set=utf8
   

[mysql] default-character-set=utf8

[mysqld] character-set-client-handshake = FALSE init_connect="SET collation_connection = utf8_general_ci" init_connect="SET NAMES utf8" character-set-server = utf8

5. my.ini 설정을 마쳤다면 다시 서비스로 돌아가 mysql을 실행해주자. 이때 뭔가 오류가 뜬다면 아마 my.ini 파일에 오타가 있을 가능성이 크니 다시 확인해보자.

6. mysql이 성공적으로 켜졌다면 다시 mysql을 접속해서 다시 ```show variables like 'c%'``` 명령을 친다. 아래와 같이 utf8이 잘 설정되었다면 성공이다.
![](https://velog.velcdn.com/images/heyday_7/post/475dab4d-52f3-4e4a-baf1-b7ba4c98826f/image.png)

#### mysql root 계정 로그인 이슈
이는 가장 귀찮게 했던 문제인데 해결법은 단순무식했다. ini 파일을 건들다 뭔가를 잘못건드렸는지 정확한 이유는 모르겠지만 mysql root 계정으로 로그인이 안되기 시작했다. 에러 로그는 아래와 같다.
```ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)```

이는 여러 시도를 많이 해봤는데... 결국 선택한 선택지는 mysql server만 지웠다가 다시 까는거였다. 내가 버린 한시간이 아까우니 안된다 싶으면 지웠다 까는걸 추천한다.

# 마무리
trouble shooting 때문에 글이 길어진 감이 없지 않지만 이렇게 dockerize를 성공적으로 끝마쳤다. 이제는 docker container를 켜고 끄는 식으로 쉽게 서버를 킬 수 있다. 다음으로는 docker를 좀 더 쉽게 사용하는 docker-compose를 적용해보겠다.

지난번 나의 과오를 돌아보며 JPA 관련 공부들을 했고 이를 코드로 적용시키려고 한다. 이 글은 Entity 탐구 글을 먼저 보고 오는 것이 좋으며, 이 글은 내용이나 팁 보다는 그저 작업 기록용 글이다.

작업

Entity들 수정

## User.kt
@Entity
class User(
    email: String,
    @Column(nullable = false)
    var name: String,

    @Column(nullable = false)
    var picture: String,

    @Enumerated(EnumType.STRING)
    var role: Role,
): PrimaryKeyEntity() {
    @Column(unique = true, nullable = false)
    var email = email
        protected set

    @Column(nullable = false)
    var createdAt: LocalDateTime = LocalDateTime.now()
        protected set

    @OneToMany(
        cascade = [CascadeType.PERSIST, CascadeType.REMOVE],
        fetch = FetchType.LAZY,
        mappedBy = "writer"
    )
    private val _diaries: MutableList<Diary> = mutableListOf()
    val diaries: List<Diary> get() = _diaries.toList()

    fun addDiary(diary: Diary) {
        _diaries.add(diary)
    }

    fun removeDiary(diary: Diary) {
        _diaries.remove(diary)
    }
}

enum class Role(
    val key: String,
    val title: String
) {
    ADMIN("ROLE_ADMIN", "관리자"),
    USER("ROLE_USER", "사용자")
}

## Action.kt
@Entity
@Table(name = "action")
class Action(
    @Column(nullable = false)
    var type: ActionType = ActionType.Any,

    @Column(nullable = false)
    var comment: String,
): PrimaryKeyEntity() {
    @Column(nullable = false)
    val createdAt: LocalDateTime = LocalDateTime.now()
}

enum class ActionType {
    Work, Study, Exercise, Hobby, Any
}

## Diary.kt
@Entity
class Diary(
    @Column(nullable = false)
    var title: String = "",

    @Column(nullable = false)
    var body: String = "",

    @Column(nullable = false)
    var isPrivate: Boolean = false,
    writer: User
): PrimaryKeyEntity() {
    @OneToMany(
        cascade = [CascadeType.ALL],
        orphanRemoval = true
    )
    private val _actions: MutableList<Action> = mutableListOf()
    val actions: List<Action> get() = _actions.toList()


    @ManyToOne
    @JoinColumn(name = "user_id", nullable = false)
    var writer: User = writer
        protected set

    fun addAction(action: Action) {
        _actions.add(action)
    }
    fun removeAction(action: Action) {
        _actions.remove(action)
    }
}

• 전체적으로 PrimaryKeyEntity를 상속받아 작성하였다.
• 일반 변수는 var로
• constructor 에서 받기는 하나 수정이 불가능하게 하고 싶은 변수는 protected set을 통해서 보호를
• list 들의 경우 kotlin backing properties를 이용해 정의하고, 따로 수정용 method를 추가해줬다.

Entity를 변화시켰기에 Service 등 여러 부분의 코드들도 부차적으로 수정해주었다.

DTO 작성(정리) 및 mapper 작성

해당 작업이 이 commit에서 잘 확인할 수 있다.

기존에도 DTO를 사용은 했었는데, Entity를 수정하며 확실하게 구조를 잡았다. 결정한 사항들은 다음과 같다.

• Entity는 Service단 까지, Controller에서 DTO와 Entity mapping이 일어난다.(살짝 고민인 부분이 있음)
• DTO는 Request, Response용을 분리한다.
• DTO에서는 순환참조 이슈를 해결하기 위해 필드를 조금 줄이거나, id만을 담는다.(ex: user.diaries를 dto에서는 diary id만을 담도록 작성한다.)

Comment 추가

Comment 추가 commit Diary의 Comment를 달 수 있도록 추가하였다. 만들어 가다 보니 게시판이랑 뭐가 다를까... 싶기는 하지만 뭐든 지금의 목표는 하나의 완성된 결과물을 내는 것이기에 굳이 상관하지 않는다.

Comment 기능은 현재 작성과 삭제만 된다. 수정은 구현할 수는 있지만 두 가지 고민이 생겨 멈춰두었다.

1. 가장 큰 이슈는 원하는데로 front 코드를 짜는게 머리가 아프다... comment 수정의 경우 그 바로 html 코드가 수정되서 화면 전환 없이 진행하고 싶은데 해당 내용을 다 까먹은지 오래고 다시 이걸 고민하는 시간이 살짝 아까워 멈춰두었다.
2. update를 짜는데에 고민이 생겼다. 이는 사실 comment에만 해당되는 문제는 아니다. DTO를 넘기지 service로 넘기지 않으려다 보니 update의 경우 controller -> service로 넘어갈 때 어떤 형식으로 넘기는지에 대한 고민이 아직 해결되지 않았다. Entity를 불러와서 수정해서 넘겨야할지, field들 만 넘기고 service에서 처리할지 이런 고민 말이다.

마무리

본 글은 하루동안 작업한 내용이 아니라 밀렸던 내용들을 그냥 순서대로 기록만! 해 두었다. 결국 핵심은 Entity와 DTO들을 정리했고, Comment 기능도 추가했다~ 정도이다. 다음 글에서는 바로 이어서 해당 작업까지의 결과물을 Docker container로 구동시키는 것을 진행하겠다.