합병 정렬은 분할 통치법(Divide and Conquer) 알고리즘을 이용한 대표적인 정렬 방법입니다. 분한 통치법은 문제를 나눌 수 없을 때까지 나눈 후, 다시 합병함으로써 문제를 푸는 방법입니다. 하양식 접근 법으로, 상위의 값을 구하기 위해, 아래로 내려가면서 답을 구합니다. 대표적으로 퀵 정렬과 합볍 정렬이 있습니다.

합병 정렬은 우선 리스트에 하나의 값만 남을때까지 반으로 쪼갭니다. 쪼갠 후, 각 리스트의 첫번째째 원서를 서로 비교해서, 더 작은 값을 새로운 리스트에 추가하면서 쪼갠 리스트들을 합병하는 과정을 거칩니다. 결국, 정렬된 리스트가 완성이 됩니다.

Pseudo Code

파이썬(Python)

def merge(left, right):
    lp = 0
    rp = 0
    sorted_list = []

    # left랑 righr에 둘 다 정렬이 되지 않았을때
    while lp < len(left) and rp < len(right):
        if left[lp] < right[rp]:
            sorted_list.append(left[lp])
            lp = lp + 1
            continue
        elif left[lp] > right[rp]:
            sorted_list.append(right[rp])
            rp = rp + 1

    # right의 데이터는 모두 정렬이 됐는데 left에는 정렬되지 않은 데이터가 있을때
    if lp < len(left) and rp >= len(right):
        while lp < len(left):
            sorted_list.append(left[lp])
            lp = lp + 1

    # left의 데이터는 모두 정렬이 됐는데 right에는 정렬되지 않은 데이터가 있을때
    if lp >= len(left) and rp < len(right):
        while rp < len(right):
            sorted_list.append(right[rp])
            rp = rp + 1

    #print(sorted_list)
    return sorted_list

def split_list(data):
    if len(data)<= 1:
        return data
    partition = int(len(data)/2)
    left = split_list(list(data[0:partition]))
    right = split_list(list(data[partition:]))

    return merge(left, right)

자바(Java)

public class MergeSort {

    public List<Integer> merge_sort(Integer[] data) {
        List<Integer> data_list = List.of(data);

        return splitAndMergeList(data_list);
    }

    private List<Integer> splitAndMergeList(List<Integer> data_list) {
        int size = data_list.size();

        if (size <= 1) {
            return data_list;
        }

        int partition = size / 2;
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            if (i < partition) {
                left.add(data_list.get(i));
            } else {
                right.add(data_list.get(i));
            }
        }

        return merge_lists(splitAndMergeList(left), splitAndMergeList(right));
    }

    private List<Integer> merge_lists(List<Integer> left, List<Integer> right) {
        List<Integer> sorted_list = new ArrayList<>();
        int lp = 0;
        int rp = 0;
        int lSize = left.size();
        int rSize = right.size();

        while (lp < lSize && rp < rSize) {
            if (left.get(lp) < right.get(rp)) {
                sorted_list.add(left.get(lp++));
            } else {
                sorted_list.add(right.get(rp++));
            }
        }

        while (lp < lSize) {
            sorted_list.add(left.get(lp++));
        }
        while (rp < rSize) {
            sorted_list.add(right.get(rp++));
        }

        return sorted_list;
    }

}

시간 복잡도

리스트를 쪼개는 과정에서, 무조건 각 리스트를 반으로 쪼개기 때문에, 데이터 n개에 대해서 높이가 $logn$인 이진 트리가 생성이 됩니다. 이때, 각 단계에서 n개의 데이터를 비교하기 때문에, 각 단계에서 걸리는 시간은 O(n) 입니다. 그렇기 때문에 시간 복잡도는 O(n) * O($logn$) 으로써, O(n $logn$)이 됩니다.

퀵 정렬에서는 먼저 기준점(Pivot)을 하나 정하고, pivot보다 작으면 left 배열에, pivot보다 크면 right 배열에 삽입합니다. 이때, pivot은 첫번째 데이터로 정하면 됩니다. 그 다음으로는 left와 right 배열에 대해서도 똑같이 각각 pivot을 정하고 pivot의 값을 기준으로 left와 right로 값들을 모읍니다. 결국 left와 right의 크기가 1이 될때까지 합니다. 마지막으로, left+pivot+right 을 리턴함으로써 최종적으로 정렬된 데이터를 반환합니다.

Pseudo Code

파이썬(Python)

def quickSort(data):
    if len(data) <= 1:
        return data

    pivot = data[0]
    left = []
    right = []

    for d in data:
        if d < pivot:
            left.append(d)
        elif d > pivot:
            right.append(d)
        else:
            continue

    return quickSort(left) + [pivot] + quickSort(right)

자바(Java)

public class QuickSort {

    public List<Integer> quick_sort(List<Integer> data) {
        if (data.size() <= 1) {
            return data;
        }

        int pivot = data.get(0);

        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();

        List<Integer> sorted_list = new ArrayList<>();

        data.forEach(d -> {
            if (d < pivot) {
                left.add(d);
            } else if (d > pivot) {
                right.add(d);
            } else {
                return;
            }
        });

        sorted_list.addAll(quick_sort(left));
        sorted_list.add(pivot);
        sorted_list.addAll(quick_sort(right));

        return sorted_list;
    }
}

시간복잡도

평군 시간복잡도는 O(n log n) 입니다. 왜냐하면, n개의 데이터를 결국 이진 트리처럼 나누게 되며, n개의 데이터에 대해서 높이가 h 일때, h = $log n$인데, 각 높이/깊이마다 n개의 데이터가 있고, n개의 데이터 모두 비교를 하기 떄문에 각 높이/깊이에서 O(n)의 시간이 걸립니다. log n의 높이에 대해서 O(n)의 시간이 걸리므로, 시간복잡도는 O(n $logn$)이 됩니다.

하지만, 최악의 경우에는 O($n^2$)이 됩니다. 왜냐하면, 만약에 각 높이에서 pivot이 나머지 모든 값들보다 크거나 작으면, 결국 left 또는 right 한쪽으로만 n-1개의 데이터가 쌓이게 됩니다. 그러면 결국 트리의 높이는 n이 됩니다. 높이 n에 대해서 n번의 비교가 이루어지므로, O($n^2$)이 됩니다.

크기가 작은 부분 문제를 해결 한 후, 점점 크기를 증가시켜서 부분적으로 문제 해결을 함으로써 최종 무제를 해결하는 알고리즘 입니다. 상향식 접근법으로, 가장 작은 크기의 해답을 구하는 것으로 시작으로, 조금씩 더 큰 문제의 해답을 구하고, 해당 결과값들로 상위 문제들을 푸는 방식입니다. 이때, memoization 기법을 사용합니다. Memization 기법이란, 이전에 문제의 값을 저장함으로써, 다음에 이전에 계산한 값을 필요로 할때 다시 계산하지 않고 저장한 값을 사용하도록해서 실행 속도를 빠르게 해주는 기법입니다. 동적 계획법(Dynamic Programming/DP)를 이용해서 푸는 가장 대표적인 문제는 피보나치 수열입니다.

0. 피보나치 수열

(https://www.fun-coding.org/00_Images/Fibonacci.png)

def myFibo_dp(num):
    cache = [i for i in range(num+1)]

    for i in range(2, num+1):
        cache[i] = cache[i-1] + cache[i-2]

    return cache[num]   

1. 백준 11726: 2×n 타일링

https://www.acmicpc.net/problem/11726 해당 문제는 단순한 문제로써, n의 값이 1부터 5일때까지만 계산해 보아도, 패턴을 찾고 점화식을 구할수 있습니다. 점화식은 n >=3 일때, F(n) = F(n-1) + F(n-2) 입니다.

def cal_comb(n):
    if n <= 2:
        return n
    cache = [0 for i in range(n+1)]
    cache[1] = 1
    cache[2] = 2

    for i in range(3, n+1):
        cache[i] = cache[i - 1] + cache[i - 2]

    return cache[n]%10007

n = int(input())
print(cal_comb(n))

2. 백준 9461: 파도반 수열(Padovan Sequence)

https://www.acmicpc.net/problem/9461 판도반 수열 또한 n의 값을 1부터 시작해서 n의 값을 1씩 늘려가면서 값들을 확인해보면 점화식을 찾을 수 있습니다. 1 <= n <= 3 일때, F(n) = 1. 3 < n <= 5 일때, F(n) = 2. 5 < n 일때, F(n) = F(n-1) + F(n-5).

def padovan_sequence(n):
    if n <= 3:
        return 1
    elif n <= 5:
        return 2
    cache = [0 for i in range(n+1)]
    cache[1] = 1
    cache[2] = 1
    cache[3] = 1
    cache[4] = 2
    cache[5] = 2

    for i in range(6, n+1):
        cache[i] = cache[i-1] + cache[i-5]

    return cache[n]

t = int(input())
for i in range(t):
    n = int(input())
    print(padovan_sequence(n))

3. 백준 1904: 01타일

https://www.acmicpc.net/problem/1904 해당 문제의 점화식은, 1 <= n <= 2 일때, F(n) = n. 2 < n 일떄, F(n) = F(n-1) + F(n-2) 입니다.

def tiles(n):
    if n <= 2:
        return n

    cache = [0 for i in range(n+1)]
    cache[1] = 1
    cache[2] = 2

    for i in range(3, n+1):
        cache[i] = (cache[i-1]+ cache[i-2])%15746

    return cache[n]

n = int(input())
print(tiles(n))```

가장 기본적인 정렬들인 버블 정렬, 삽입 정렬, 선택 정렬을 알아보고 파이썬(python)으로 구현해보도록 하겠습니다.

버블 정렬(Bubble Sort)

가장 기초적인 정렬로, 저장된 모든 데이터에 대해서 앞 뒤로 인접한 데이터와 비교해서 자리를 바꿔주면서 데이터를 정렬하는 알고리즘 입니다.

오른차순으로 데이터를 정렬한다고 했을때, 데이터의 가장 앞의 값부터 정렬을 시작합니다. 앞에서 시작해서 하나씩 바로 뒤에 인접해 있는 값이랑 비교를 합니다. 비교 했을때, 뒤에 있는 값보다 현재의 값이 더 크면, 서로의 위치를 바꿔줍니다. 이렇게하면, 정렬되지 않은 값들 중에서 최대값이 뒤에서부터 차례대로 정렬이 됩니다.

구현하기(파이썬)

def bubble_sort(arr):
    size = len(arr)
    for i in range(size-1):
        swap = False
        for j in range(size-i-1):
            if arr[j] > arr[j+1]:
                tmp = arr[j+1]
                arr[j+1] = arr[j]
                arr[j] = tmp
                swap = True
        if swap == False:
            break
    return arr

시간복잡도

n개의 데이터에 대해서 정렬되지 않은 모든 데이터들끼리 한번씩은 비교를 해야되기 때문에 이중 중첩 반복문을 실행하게 됩니다. 그렇기 때문에, 시간복잡도는 O($n^2$)이 됩니다.

삽입 정렬(Insertion Sort)

자신의 위치보다 앞에 있는 값들과 비교를 하면서 자리를 찾아주는 정렬 입니다. 자신의 값보다 앞에 있는 값들이랑 하나씩 비교 했을때, 자신의 값보다 작은 값이 있으면, 해당 작은 값 바로 뒤가 자신의 위치로 정해집니다. 자신의 위치보다 앞에 있는 데이터들과 값들을 비교해서, 자신보다 값이 크면 서로 위치를 바꿔주면서(swap) 자리를 찾습니다. 결국 자신보다 작은 값을 찾으면 swap을 멈추고, 해당 자리가 최종 위치가 됩니다.

구현하기(파이썬)

def insertion_sort(data):
    size = len(data)

    # 배열의 앞에서 부터 모든 데이터에 대해서 자기보다 앞에 저장된 데이터들이랑 비교
    # 비교 했을때 자신의 값보다 크면 swap
    # 비교 했을때 자신의 값보다 작으면 최종 위치 확정
    for i in range(size):
        for j in range(i, 0, -1):
            if i == j:
                continue

            if data[j] < data[j-1]:
                tmp = data[j-1]
                data[j-1] = data[j]
                data[j] = tmp
            else:
                break

    return data

시간복잡도

삽입 정렬은 모든 n개의 데어터들에 대해서 앞에 있는 데이터들에 대해서 값들을 비교하게 됩니다. n개의 데이터가 1번부터 n번까지 데이터가 저장되어 있고, 현재 데이터의 위치가 i일때, 최악의 경우 i-1번의 비교를 해야됩니다. 그렇기 때문에 n개의 데이터에 대해서 시간복잡도는 O($n^2$)이 됩니다.

선택 정렬(Selection Sort)

첫 번째 데이터부터 탐색을 시작하면서, 현재 탐색하는 위치부터 뒤에 있는 데이터 중 최소값을 찾습니다. 찾은 후, 최소값이 저장된 위치와 현재 위치를 바꿔줌으로써, 앞에서부터 최소값이 차례대로 정렬되도록 합니다.

구현하기(파이썬)

def selection_sort(data):
    size = len(data)

    for i in range(size):
        min_idx = i
        for j in range(i+1, size):
            if data[j] < data[min_idx]:
                min_idx = j
        # Swap
        tmp = data[i]
        data[i] = data[min_idx]
        data[min_idx] = tmp

    return data

시간복잡도

선택 정렬도 결국 모든 n개의 데이터들에 대해서 자신의 위치보다 뒤에 있는 모든 데이터들과 비교를 하기때문에 시간복잡도는 O($n^2$)이 됩니다.

삽입 정렬 vs. 선택 정렬?

삽입 정렬과 선택 정렬 모두 시간복잡도는 O($n^2$)으로 같습니다. 그렇가면 어떤 방식으로 이용해서 정렬을 해야 될까요? 사실 둘 다 좋은 정렬 방법은 아닙니다. Merge Sort, Quick Sort 등 더 복잡하지만 더 빠른 정렬 방식들이 있끼 때문입니다. 하지만, 구현이 단순하고 데이터의 양이 적을 경우에는 사용할만한 정렬 방법들 입니다.

• 삽입 정렬은 초기 리스트가 순서대로 많이 정렬된 경우에 더 적합한 방법입니다.
• 선택 정렬은 데이터들을 swap 하는데 비용이 클 경우 더 적합합니다. 왜냐하면, 삽입 정렬은 여러번의 swap을 통해서 자리를 찾지만, 선택 정렬은 정렬되지 않은 데이터들 중에서 최소값과 한번만 swap이 일어나기 때문에, swap이 일어나는 횟수가 더 적기 때문입니다.

힙 이란, 데이터의 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 입니다. 완전 이진 트리는 새로운 노드를 추가할때 무조건 왼쪽 최하단에서 부터 순차적으로 노드를 추가하는 이진 트리입니다. (이진 트리는 부모 노드가 최대 2개의 자식만 가질수 있는 트리)

항상 왼쪽 하단에 새로운 데이터를 추가한 후, 부모 노드와 비교해서 새로 추가한 노드의 최종 위치를 찾아 줍니다.. Max Heap의 경우 부모 노드가 자신의 값보다 작으면 서로 위치를 바꿔줌으로써 root에는 항상 최대값이 유지 됩니다. Min Heap은 자신 보다 부모 노드가 크면 서로 바꿈으로써, root에 항상 최소값을 유지합니다. 이때, 완전 이진 트리는 무조건 노드를 최하단에 추가하기 때문에 데이터를 배열에 넣어도 부모와 자식간의 인덱스를 계산하기 편합니다. (https://www.fun-coding.org/00_Images/completebinarytree.png)

힙 구현하기(파이썬)

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)

힙은 단순히 배열로 구현이 가능하기 때문에 배열로 선언해 줍니다. 선언 후, 첫번째 데이터를 넣을때, 나중에 부모와 자식 간의 인덱스 계산을 편하게 하기 위해 인덱스 0에는 None 값을 넣고, 인덱스 1부터 데이터를 넣기 시작합니다.

부모와 자식간의 인덱스 계산하기

• 1. 부모 노드 인덱스 == 자식 노드 인덱스 // 2
• 2. 왼쪽 자식 노드 인덱스 == 2 * 부모 노드 인덱스
• 3. 오른쪽 자식 노드 인덱스 == 2 * 부모 노드 인덱스 + 1

노드 추가하기

Max Heap 일때 새로운 노드를 추가하는 것을 보도록 하겠습니다. (https://www.fun-coding.org/00_Images/heap_insert.png) 사진에는 노드 20을 힙에 추가합니다. 이때, 노드 20은 먼저 맨 마지막 위치에 추가합니다. 추가한 후, 부모 노드와 비교해서, 부모 노드보가 값이 크면 부모 노드와 위치를 바꿔줍니다. 부모 노드가 자신보다 크거나, root 노드가 되었을 경우부터 비교를 멈추고, 새로 추가한 노드의 최종 위치가 정해집니다.

구현하기(파이썬)

    def move_up(self, inserted_idx):
        if inserted_idx <= 1: # 인덱스 값이 1이면 이미 root -> 부모 노드가 없으므로 메서드 탈출
            return False

        parent_idx = inserted_idx // 2
        if self.heap_array[inserted_idx] > self.heap_array[parent_idx]: # 자신이 가진 값이 부모 노드의 값보다 클 경우
            return True
        else:
            return False

    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True

        self.heap_array.append(data)

        inserted_idx = len(self.heap_array) - 1 # 마지막 데이터의 인덱스 값 가져오기

        while self.move_up(inserted_idx): # 추가된 데이터의 차리를 찾아주기
            parent_idx = inserted_idx // 2 # 부모 노드의 인덱스 == 자신의 인덱스 // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx] # SWAP
            inserted_idx = parent_idx # 자신의 인덱스 값 갱신

        return True

새로운 노드를 추가할때, 먼저 배열의 마지막 인덱스에 추가를 합니다. 추가 후, 위에서 알아본 부모 노드와 자식 노드 간의 인덱스 계산 방식을 통해 부모 노드를 찾아서 값을 비교 합니다. 값 비교 후, 자신의 값이 부모 노드의 값이 더 크면 서로의 위치를 바꿔 줍니다(swap). 자기 자신이 root 노드가 되거나, 부모 노드보다 값이 작아질때까지 위치를 바꿔줍니다.

노드 삭제하기

힙은 저장된 데이터들의 최대값 또는 최소값을 바로 접근 할 수 있도록 하는 데이터 구조임으로, 힙에서 데이터 삭제는 root 노드에서만 하도록 합니다. 그렇기 때문에, root 노드를 삭제 했을때, root 노드에는 항상 최대값 또는 최소값이 유지되도록 하는 것이 중요하며, 삭제된 root 노드를 대체할 노드가 최대값 또는 최소값이 되도록 해야 합니다. (https://www.fun-coding.org/00_Images/heap_remove.png)

Root 노드를 대체할 찾기 위해서 먼저 힙의 마지막 노드를 root로 이동시켜줍니다. 이동 시킨 후, 노드를 추가할때와 반대로 생각하면 됩니다. 이동 시킨 노드를 root에서 시작해서 아래로 내려가면서 위치를 찾아주는것 입니다. 이때, 자신의 값과 자식 노드들의 값들을 비교해서, Max Heap의 경우에는 자식 노드들 중 더 큰 값을 가진 노드를 찾고, 찾은 자식 노드가 자기 자신보다 값이 크면 서로 위치를 바꿔줍니다. 이렇게, 자기 자신이 Leaf Node가 될때까지, 또는 자식 노드들 모두 자기 자신보다 값이 작을때까지 반복해줍니다. Min Heap의 경우 자식 노드들 중 더 작은 값을 가진 노드와 비교하며, 자기 자신의 값이 자식 노드보다 더 작으면 위치를 바꿔줍니다.

구현하기(파이썬)

    def pop(self):
        if len(self.heap_array) <= 1:
            return None

        # root(최대값) 반환
        returned_data = self.heap_array[1]

        # 마지막 노드를 root로 이동
        self.heap_array[1] = self.heap_array[-1] # 가장 마지막 노드를 root로 옮기기 (-> 동시에 pop 된 데이터도 삭제됨)
        del self.heap_array[-1] # 가장 마지막 노드를 root로 옮겼으므로, 마지막 노드가 있었던 위치에 있던 노드는 삭제
        popped_idx = 1

        # root로 옮긴 새로운 노드의 최종 자리를 찾아줌 -> 새로운 노드의 값이 자식 노드의 값보다 커질때까지 실행 || 자식이 없을때까지
        # 자식 노드의 값이 더 크면 swap && 인덱스 값 갱신
        while True:
            left_child_popped_idx = popped_idx * 2
            right_child_popped_idx = popped_idx * 2 + 1

            # case1: 왼쪽 자식도 없을때(왼쪽 자식이 없으면 오른쪽 자식도 없음)
            if left_child_popped_idx >= len(self.heap_array):
                    return returned_data
            # case2: 오른쪽 자식 노드만 없을 때
            elif right_child_popped_idx >= len(self.heap_array): 
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]: # 부모 노드의 값보다 왼쪽 자식 값이 더 클때
                    self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx
                    continue
                else: # 부모 노드의 값이 더 크므로 차리 찾기 완료
                    return returned_data
            # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
            else:
                if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]: # 왼쪽 노드와 오른쪽 노드의 값 비교
                    if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]: # 자식 노드의 값 > 부모 노드의 값
                        self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[left_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = left_child_popped_idx
                        continue
                    else: # 부모 노드의 값이 더 크므로 차리 찾기 완료
                        return returned_data
                else:
                    if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]: # 자식 노드의 값 > 부모 노드의 값
                        self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[right_child_popped_idx], self.heap_array[popped_idx]
                        popped_idx = right_child_popped_idx
                        continue
                    else: # 부모 노드의 값이 더 크므로 차리 찾기 완료
                        return returned_data

        return returned_data

0. 힙의 크기 1보다 작거나 같으면, root만 남아 있는 힙이로써, 위치를 더 찾을 필요가 없습니다
1. Root(인덱스 1)의 값을 반환
2. 힙에서 마지막 인덱스에 있는 값을 root(인덱스 1)로 이동
3. 자식 노드가 있는지 없는지 확인:
   • 3-1. 자식 노드가 없으면 최종 위치
   • 3-2. 자식 노드가 하나만 있으면, 자식 노드와 값을 비교해서 위치를 바꿀지 말지 결정
   • 3-3. 자식 노드가 두 개 있으면, 자식 노드 중 더 큰 값을 가진 노드를 먼저 찾음. 더 큰 값을 가진 자식 노드와 자기 자신을 비교해서 위치를 바꿀지 말지 결정

시간복잡도

힙의 경우, 배열로 저장하더라도 사실은 트리로 표현한 것이기 때문에, 높이 h에 대해서 시간 복잡도는 최악의 경우 O(h)입니다. 이때, n개의 노드에 대해서 h = log n 이므로, 시간 복잡도는 O(log n)이 됩니다. 데이터를 추가할때, 최악의 경우, leaf node부터 root node까지 탐색을 해야하기 때문입니다. 삭제를 할때도, root node를 삭제한 후 최악의 경우, 대체할 노드를 root node부터 leaf node까지 탐색을 해야합니다.

값을 저장하고 있는 노드(Node)들이 Branch로 연결되어 있는 데이터 구조입니다. 가장 위에 있는 루트 노드(Root Node)에서 시작해서 밑으로 갈 수록 연결되어 있는 노드들이 많아지면서, 거꾸로 봤을때 나무 같기 때문에 트리라고 부릅니다. (http://www.fun-coding.org/00_Images/tree.png)

용어:

• Node: 트리에서 데이터를 저장하는 기본 요소
• Root Node 또는 Root: 트리에서 가장 위에 있는 노드 (탐색의 시작점)
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node(부모 노드): 어떤 노드의 바로 위에 연결된 노드
• Child Node(자식 노드): 어떤 노드의 바로 하위에 연결된 노드
• Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
• Sibling (Brother Node): 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진 탐색 트리(Binary Search Tree)

(https://www.mathwarehouse.com/programming/images/binary-search-tree/binary-search-tree-insertion-animation.gif) 하나의 부모 노드에 대해서 가질 수 있는 최대의 자식 노드가 2개로 이루어진 트리입니다. 이진 탐색 트리에서 무조건 지켜야되는 규칙으로는 부모 노드보다 값이 작은 자식 노드는 왼쪽 자식 노드, 부모 노드보다 값이 큰 노드는 오른쪽 자식 노드로 저장해야 된다는 것 입니다.

노드 추가하기

    def insert(self, value):
        node = self.root

        while True:
            if node.value <= value:
                if node.right == None:
                    node.right = Node(value)
                    return
                else:
                    node = node.right
            else:
                if node.left == None:
                    node.left = Node(value)
                    return
                else:
                    node = node.left

노드를 추가하기 위해서는 노드가 저장되어야 하는 위치를 찾아줘야합니다. 루트 노드로 시작해서 Leaf Node가 나올때까지 트리의 하단으로 이동을 합니다. 이때, 현재 탐색 중인 노드의 값과 추가할려는 값을 비교해서, 추가할 값이 더 크면 오른쪽 자식으로 이동, 값이 더 작으면 왼쪽 자식으로 이동하면서 Leaf Node를 찾습니다. *Leaf Node를 찾으면, 해당 노드보다 추가할려는 값이 작으면 추가할려는 값은 찾은 Leaf Node의 왼쪽 자식이되고, 값이 더 크면 오른쪽 자식이 됩니다. *

만약에 숫자들 2,3,4,7,8,1,6를 적혀 있는 순서 대로 값을 추가해서 이진 탐색 트리를 생성하면 다음과 같은 트리가 생성될 것 입니다.

노드 삭제하기

이진 탐색 트리에서 노드를 추가하는 것은 간단하지만, 삭제하는 것은 조금 더 복잡하니다. 왜냐하면, 노드를 삭제한 후, 삭제할 노드의 자리를 대체할 노드를 찾아서 위치를 바꿔줘야하기 때문입니다. 노드를 삭제할 때 고려해야되는 Case들을 3개로 나눠서 보도록 하겠습니다.

Case 1: 삭제할 노드가 Leaf Node 일때

이러한 Case는 간단합니다. Leaf Node이면 자식 노드가 없으므로, 삭제할 노드를 자신의 하위에 있는 서브 트리 중의 노드 하나로 대체할 필요가 없기 때문입니다. 노드를 삭제하고, 삭제한 부모 노드의 자식 노드만 갱신시켜주면 됩니다. (http://www.fun-coding.org/00_Images/tree_remove_leaf.png)

         # Case 1
        if node.left == None and node.right == None: # 삭제할 노드가 Leaf Node 일때
            if parent.left.value == node.value: # 부모 기준 삭제될 노드가 왼쪽 자식 일때 -> 왼쪽 자식은 삭제되므로 None으로 갱신
                parent.left = None
                return True
            if parent.right.value == node.value:# 부모 기준 삭제될 노드가 오른쪽 자식 일때 -> 오른쪽 자식은 삭제되므로 None으로 갱신
                parent.right = None
                return True
            return False

Case 2: 삭제할 노드가 자식 노드 하나를 갖고 있을때

Case 2 같은 경우에는, 원하는 노드를 삭제한 후, 삭제한 노드의 자릴 자식 노드로 대체하고, 삭제한 노드의 부모 노드의 자식 노드를 갱신시켜주면 됩니다. 삭제한 노드의 유일한 자식 노드로 대체 할 경우, 자식 노드의 하위 서브 트리도 그대로 유지되고, 이진 탐색 트리의 규칙에도 어긋나지 않기 때문에 고려할 부분들이 많지 않습니다. 삭제할 노드가 부모 노드의 왼쪽 자식인지 오른쪽 자식인지, 그리고 삭제할 노드가 왼쪽 자식만 있는지 오른쪽 자식만 있는지 확인하면 됩니다. (http://www.fun-coding.org/00_Images/tree_remove_1child.png)

        # Case 2
        if node.left != None and node.right == None: # 삭제할 노드가 왼쪽 자식만 갖고 있을때
            if parent.left != None:
                if parent.left.value == node.value: # 삭제할 노드가 부모 노드의 왼쪽 자식일때
                    parent.left = node.left
                    return True
            if parent.right != None:
                if parent.right.value == node.value: # 삭제할 노드가 부모 노드의 오른쪽 자식일때
                    parent.right = node.left
                    return True
            return False
        elif node.left == None and node.right != None: # 삭제할 노드가 오른쪽 자식만 갖고 있을때
            if parent.left != None:
                if parent.left.value == node.value: # 삭제할 노드가 부모 노드의 왼쪽 자식일때
                    parent.left = node.right
                    return True
            if parent.right != None:
                if parent.right.value == node.value: # 삭제할 노드가 부모 노드의 오른쪽 자식일때
                    parent.right = node.right
                    return True
            return False

Case 3: 삭제할 노드가 자식 노드 두개를 갖고 있을때

(http://www.fun-coding.org/00_Images/tree_remove_2child.png)

이진 탐색 트리에서 노드를 삭제할때 고려할것이 가장 많은 Case 입니다. 그러한 이유는 이진 탐색 트리의 규칙 때문입니다. 값을 추가할때, 특정 노드보다 추가할 값이 크면 오른쪽 자식으로, 값이 작으면 왼쪽 자식으로 저장하는 규칙 때문에 자기 자신의 노드보다 오른쪽 서브 트리에 있는 모든 노드들은 자기 자신보다 값들이 무조건 커야하고, 반대로 왼쪽 서브 트리에 있는 모든 노드들은 값들이 작아야 합니다. 다음 트리를 한 번 보도록 하겠습니다. (http://www.fun-coding.org/00_Images/tree_remove_2child_code_left.png) 보다시피, 현재 자기 자신이 15 노드라고 했을때, 15보다 왼쪽에 있는 노드들은 모두 15보다 작고, 오른쪽에 있는 노드들은 모두 15보다 큽니다. 이러한 규칙은 노드를 삭제한 이후에도 유지되어야 하기 때문에 삭제한 노드를 대체할 노드를 찾는것이 가장 큰 문제점 입니다. 만약, 위의 트리에서 노드 15를 삭제하고 노드 17로 대체하면, 17의 오른쪽에는 노드 16이 여전히 있습니다. 하지만, 노드 17의 오른쪽에 있는 노드들은 모두 17보다 커야하기 때문에 16은 오른쪽에 있으면 안됩니다. 그렇기 때문에, 규칙을 유지하면서 대체할 노드를 찾는 것이 가장 중요합니다.

대체할 노드를 찾는 방법은 두가지가 있습니다.

• 1. 삭제할 노드의 오른쪽 서브트리에서 가장 작은 노드로 대체하기(-> 위의 트리에서는 16)
• 2. 삭제할 노드의 왼쪽 서브트리에서 가장 큰 노드로 대체하기(-> 위의 트리에서는 14) 위의 두가지 방식으로 찾은 노드들로 대체하면 이진 탐색 트리의 규칙을 유지할 수 있습니다. 저희는 1번 방식을 통해 대체할 노드를 찾아보도록 하겠습니다.

1번 방식으로 노드를 찾는 방법은 다음과 같습니다:

1. 삭제할 노드의 오른쪽 자식을 찾습니다.
2. 삭제할 노드의 오른쪽 자식으로 부터 Leaf Node가 나올때까지 계속 왼쪽 자식으로 이동합니다.
3. 이렇게 찾은 Leaf Node는 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 노드가 될 것 입니다.

삭제할 노드가 A, 대체할 노드를 B, A의 부모 노드를 C, A의 왼쪽 자식 노드를 D, A의 오른쪽 자식 노드를 E라고 하겠습니다. A를 B로 대체하기 위해서는 C->B를 가르키고, B->D && B->E를 자식 노드들로 가르키도록 하면 됩니다.

        # Case 3
        if node.left != None and node.right != None: # 자식 노드가 왼쪽 오른쪽 자식 모두 있을때
            replacement = node.right
            replacement_parent = node

            while replacement.left != None: # 오른쪽 서브 트리에서 가장 작은 노드 찾기; B 찾기
                replacement_parent = replacement
                replacement = replacement.left

            replacement_parent.left = replacement.right #대체한 노드의 부모 노드의 자식 노드 갱신하기

            # 대체할 노드의 자식들 갱신 시켜주기
            replacement.left = node.left # B->D 가르키기
            replacement.right = node.right # B->E 가르키기

            if parent.left != None:
                if parent.left.value == node.value: # 삭제한 노드가 부모 노드의 왼쪽 자식일때
                    parent.left = replacement # 삭제한 노드의 부모 노드의 자식 노드 갱신하기; C->B 가르키기
                    return True
            if parent.right != None:
                if parent.right.value == node.value: # 삭제한 노드가 부모 노드의 오른쪽 자식일때
                    parent.right = replacement # 삭제한 노드의 부모 노드의 자식 노드 갱신하기; C->B 가르키기
                    return True
            return False

시간 복잡도

트리의 depth/높이를 h라고 했을때, 시간 복잡도는 O(h)가 됩니다. 이때, 트리가 n개를 가지고 있으면 h = log n 에 가깝기 때문에 시간 복잡도는 O(log n)이 됩니다. 하지만, 이는 평균 시간 복잡도를 뜻합니다.

이진 탐색 트리는 최악의 경우 O(n)의 시간 복잡도를 가지게 됩니다. 왜냐하면, root에 n개의 값들 중 가장 작은 값이 들어가고, 추후에 추가되는 값들이 이전에 추가된 값들 보다 모두 큰 값이 들어오면 결국 모든 노드는 오른쪽 자식만 갖게 됩니다. (http://www.fun-coding.org/00_Images/worstcase_bst.png) 이런 경우에는 결국 배열과 동일하기 처음부터 순차적으로 하나씩 탐색해서 원하는 값을 찾게되기 때문에 시간 복잡도는 O(n)이 됩니다. 이렇게 한쪽으로만 데이터가 추가되는 것을 방지하기 위해 AVL 트리(Tree) 처럼 좌우로 균형을 맞춰주는 트리가 있습니다.

해쉬 테이블(Hash Table)은 저장할 데이터(Value)와 매칭되는 키(Key) 값을 Key-Value 형태로 같이 저장하는 데이터 구조로써, 원하는 데이터를 찾기 위해서 처음부터 순차적으로 배열을 훑어야하는 문제점을 해결합니다. 원하는 데이터를 찾고 싶은 경우, 데이터와 매칭되는 키 값을 통해 바로 원하는 데이터를 반환 받을 수 있습니다. 데이터를 저장하거나 읽기 빠르므로, 검색, 저장, 삭제, 읽기가 많이 일어나는 경우 사용하기 용이합니다. (https://www.fun-coding.org/00_Images/hash.png)

용어

• 해쉬(Hash): 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) 또는 해쉬 주소(Hash Address): Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간

구현하기(파이썬)

hash_table = list([0 for i in range(8)])

def get_key(key):
    return hash(key) # hash() -> 파이썬에 제공해주는 Hash Key 값을 반환해주는 함수

def hash_function(key):
    return key % 8

def save_data(key, value):
    hash_address = hash_function(get_key(key))
    hash_table[hash_address] = value

def read_data(key):
    hash_address = hash_function(get_key(key))
    return hash_table[hash_address]

• hash_table : 크기가 8인 해쉬 테이블
• def get_key(key) : 파이썬에서 제공해주는 hash() 메서드를 이용해서 키 값을 해쉬로 변환
• def hash_function(key) : 해쉬 값을 해쉬 테이블에 저장할 위치인 해쉬 주소로 변환
• def save_data(key, value) : 저장할 Key-Value 값을 받아서, 키 값은 해쉬 주소로 변환하고, 변환된 해쉬 주소에 Value 값을 저장
• def read_data(key): 찾고 싶은 데이터의 키 값을 해쉬 주수로 반환하고, 해쉬 테이블에서 해당 주소의 값을 가져와서 찾고자 하는 데이터 반환

문제점:

해쉬 테이블의 가장 큰 문제점은 같은 해쉬 주소에서 다수의 데이터를 저장하고자 할때 충돌이 일어난다는 문제점입니다. 위의 코드에서 해쉬 테이블의 크기는 8인데, 만약 저장하고자하는 데이터의 갯수가 8개를 초과하게 되면 무조건 충돌이 일어납니다. 또한, 적은 양의 데이터를 저장할려고해도, 해쉬 주소는 겹칠수 있기 때문에 이러한 경우에도 충돌이 일어납니다. 다음으로는 충돌이 일어나지 않는 해결 방법 두가지를 알아보도록 하겠습니다.

충돌 해결 #1: Chaining 기법

해당 방식은 Open Hashing 기법 중 하나입니다. Open Hashing이란, 해쉬 테이블 외의 공간을 이용해서 데이터를 저장하는 방식입니다. Chaining 기법은 각 해쉬 주소마다 다수의 데이터를 저장할 수 있도록 하며, 각 데이터를 키-데이터 값으로 저장합니다. C언어서는 연결 리스트, Java에서는 ArrayList<>()로 구현 가능 합니다.

구현하기(파이썬)

hash_table = list([0 for i in range(8)]) # 해쉬 테이블의 값들을 0으로 초기화해서 선언

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8


def save_data(data, value):
    key = get_key(data)
    hash_key = hash_function(key)

    if hash_table[hash_key] == 0:
        hash_table[hash_key] = [[key, value]]
    else:
        for v in hash_table[hash_key]:
            if v[0] == key: # 이미 버킷에 같은 Key 값을 가진 데이터가 있을때 Value를 업데이트 해줌
                v[1] = value
                return

        hash_table[hash_key].append([key, value]) # 버킷에 같은 Key 값을 가진 데이터가 없으면 데이터를 추가해줌

def read_data(data):
    key = get_key(data)
    hash_key = hash_function(key)

    if hash_table[hash_key] != 0:
        for v in hash_table[hash_key]:
            if v[0] == key:
                return v
        return "Data Not Found"
    else:
        return "Data Not Found"

• def save_data(data,value)에서 먼저 해당 해쉬 주소에 값이 저장되어 있는지 확인 합니다. 해쉬 주소에 저장된 값이 없으면 Key-Value 값을 가진 튜플을 배열에 저장 시킵니다. 이렇게 함으로써, 같은 해쉬 주소에 다수의 값이 저장될때 [[Key, Value], [Key, Value], [Key, Value]...] 로 값들이 저장될 수 있도록 합니다. 먄약 해쉬 주소에 이미 저장된 값들이 있으면, 같은 Key 값을 가진 튜플이 있는지 확인 합니다. 만약 있으며 Value 값을 갱신 시켜주고, 값이 없으면 새로운 [Key-Value] 값을 추가해줍니다.

• def read_data(data) 에서는 먼저 Key 값을 해쉬랑 해쉬 주소로 변환합니다. 그 다음으로 해쉬 테이블에서 해당하는 해쉬 주소에 저장된 튜플들을 순회하면서, 해쉬를 Key 값으로 가진 튜플이 있는지 확인합니다. 일치하는 튜플이 있을 경우 Value를 반환합니다.

충돌 해결 #2: Linear Probing 기법

Linear Probing 기법은 Closed Hashing 기법 중 하나로써, 해쉬 테이블 외의 추가의 저장공간을 필요로 하지 않기 때문에 저장공간 활용도를 높일 수 있습니다. Linear Probing 기법은 데이터를 저장할려고 할때 충돌이 일어나면, 해당 해쉬 주소로 부터 순차적으로 하나씩 다음 주소를 확인해서 빈 공간을 찾습니다. 그렇게 맨 처음으로 나온 빈 공간에 충돌이 일어났었던 데이터를 저장하는 기법입니다.

구현하기(파이썬)

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    key = get_key(data)
    hash_key =  hash_function(key)

    hash_size = len(hash_table)
    for k in range(hash_key, hash_key+hash_size):
        if hash_table[k % hash_size] == 0:
            hash_table[k % hash_size] = [key, value]
            return
        elif hash_table[k % hash_size][0] == key:
            hash_table[k % hash_size][1] = value # Key 값이 같으면 Value를 업데이트 해줌
            return

    return "Hash Table is Full"

def read_data(data):
    key = get_key(data)
    hash_key = hash_function(key)

    hash_size = len(hash_table)
    for k in range(hash_key, hash_key+hash_size):
        if hash_table[k % hash_size] == 0:
            continue
        if hash_table[k % hash_size][0] == key:
            return hash_table[k % hash_size]

    return "Data Not Found"

먼저, 데이터와 매칭되는 해쉬 주소에 데이터 저장을 시도합니다. 충돌이 일어나면 하나씩 다음 주소를 탐색해서 빈 공간을 찾고, 데이터를 저장합니다. 이때, 저장하는 데이터는 Key-Value 값인데, 그러한 이유는 데이터를 찾을때 Key 값이 필요하기 때문입니다. 데이터를 찾기 위해서는 우선 Key 값에 매칭되는 해쉬 주소를 확인합니다. 이때, 해당 해쉬 주소의 Key 값을 확인한 후, 일치하면 Value를 반환합니다. 일치하지 않을 경우, 하나씩 다음 해쉬 주소의 Key 값을 확인하면서, 일치하는 Key 값이 나올때까지 탐색합니다.

시간 복잡도

저장과 읽기를 할 때, 충돌이 일어나지 않으면 시간 복잡도는 O(1)이 됩니다. 왜냐하면, 충돌이 없을 경우 정확히 하나의 해쉬 주소를 보면 되기 때문입니다. 하지만, N개의 데이터를 저장하거나 읽을때, 모든 데이터에 대해서 충돌이 일어나면 시간 복잡도는 O(n)이 됩니다. 왜냐하면, 모든 데이터에 대해 충돌이 일어나면, 결국 배열에 순차적으러 N개의 데이터를 저장하거나 읽는 것과 똑같이 실행되기 때문입니다.

연결 리스트에서는 데이터를 노드(Node) 단위로 저장합니다. 노드에는 데이터와 자기 자신의 노드와 연결되어 있는 다른 노드(들)의 주소 값을 저장하고 있습니다. 연결 리스트에서 맨 첫번째 노드를 Head라고 지칭하고, 마지막에 있는 노드를 Tail이라고 지칭합니다. 배열과의 차이점은, 배열은 연관된 데이터들을 순차적으로 적재하지만, 연결 리스트에서는 각각 따로 저장하고 서로의 주소를 저장하고 있으므로, 주소를 참조해서 다음 데이터를 접근합니다. (단일 연결 리스트: https://www.fun-coding.org/00_Images/linkedlist.png) 주로 연결 리스트는 C언어에서 사용 되는 데이터 구조이지만, 파이썬에서도 구현 가능합니다.

(C언어로 이중 연결 리스트 구현했던 코드)

typedef struct Day
{
    struct Day *llink;
    char DofW[10];
    struct Day *rlink;
}day;

typedef struct List
{
    day *rlink;
}linked_list;
linked_list *createList()
{
    linked_list *a;
    a = (linked_list *)malloc(sizeof(linked_list));
    return a;
}
day *addNode(char *p)
{
    day *a;
    a = (day *)malloc(sizeof(day));
    strcpy(a->DofW, p);

    return a;
}
void addLeftLink(day *ptmp, day *arr)
{
    arr->llink = ptmp;
}
void addMon(day *mon, linked_list *first)
{
    day *tmp = first->rlink; // tmp == arr[0]
    tmp->llink = mon;

    mon->rlink = first->rlink;
    first->rlink = mon;
    mon->llink = NULL;
}
void printList(linked_list *first)
{
    day *a = first->rlink;

    if (first->rlink != NULL)
    {
        printf("%s\n", a->DofW);
        while (a->rlink != NULL)
        {
            a = a->rlink;
            printf("%s\n", a->DofW);
        }
    }
}
void printListRev(day *arr)
{
    day *a = arr;

    while(a->rlink != NULL)
    {
        a = a->rlink;
    }
    printf("%s\n", a->DofW);
    while (a->llink != NULL)
    {
        a = a->llink;
        printf("%s\n", a->DofW);
    }

}
void deleteFirstNode(linked_list *first)
{
    day *del = first->rlink, *a = first->rlink;

    a = a->rlink;
    a->llink = NULL;
    first->rlink = a;

    free(del);
}
int main()
{
    day *arr, *mon, *ptmp;
    linked_list *first;
    char tmp[4][10];

    first = createList();

    strcpy(tmp[0], "화");
    strcpy(tmp[1], "수");
    strcpy(tmp[2], "목");
    strcpy(tmp[3], "월");

    arr = addNode(tmp[0]);
    first->rlink = arr;
    arr->llink = NULL;

    ptmp = arr;
    arr->rlink = addNode(tmp[1]);
    arr = arr->rlink;
    addLeftLink(ptmp, arr);

    ptmp = arr;
    arr->rlink = addNode(tmp[2]);
    arr = arr->rlink;
    arr->rlink = NULL;
    addLeftLink(ptmp, arr);

    printList(first);

    mon = addNode(tmp[3]);
    addMon(mon, first);

    printf("\n");
    printList(first);

    printf("\n");
    printListRev(arr);

    deleteFirstNode(first);

    printf("\n");
    printList(first);

    printf("\n");
    printListRev(arr);

    return 0;
}

단일 연결 리스트

단일 연결 리스트는 노드가 한 방향으로만 접근 할 수 있는 연결 리스트입니다. 즉, 노드가 자신의 다음 노드의 주소를 가지고 있어서 다음 노드를 접근 할 수 있지만, 자신의 이전 노드의 주소는 갖고 있지 않아서 이전 노드는 접근하지 못하는것 입니다.

노드(Node):

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

노드에서 data는 저장할 데이터를 가지고 있으며, next에는 다음 노드의 주소를 저장합니다.

연결 리스트 구현하기:

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)

    def add(self, data): # 제일 마지막에 새로운 노드 추가하기
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

    def desc(self): # Head부터 순회해서 모든 노드의 데이터 출력하기
        node = self.head
        while node:
            print (node.data)
            node = node.next

    def delete(self, data): # 특정 data 값을 가진 노드 삭제하기
        if self.head == '':
            print ('해당 값을 가진 노드가 없습니다.')
            return
        if self.head.data == data: # 경우의 수1: self.head를 삭제해야할 경우 - self.head를 바꿔줘야 함
            temp = self.head # self.head 객체를 삭제하기 위해, 임시로 temp에 담아서 객체를 삭제했음
            self.head = self.head.next # 만약 self.head 객체를 삭제하면, 이 코드가 실행이 안되기 때문!
            del temp
        else:
            node = self.head
            while node.next: # 경우의 수2: self.head가 아닌 노드를 삭제해야할 경우
                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next       
                    del temp                         
                    pass                             
                else:
                    node = node.next

    def search_node(self, data): # 특정 data 값을 가진 노드 찾기
        node = self.head
        while node:
            if node.data == data:
                return node
            else:
                node = node.next

여기서 가장 눈여겨볼 메서드는 delete(self, data) 메서드 입니다. 해당 메서드는 연결 리스트에서 특정 값을 가진 노드를 삭제하는 것인데요, 이때 고려해야될 것들이 있습니다.

첫번째는, 연결 리스트에서의 노드를 삭제하면, 삭제한 노드 기준으로 이전 노드들과 이후의 노드들이 연결이 끊어지기 때문에, 연결이 끊어지지 않도록 해야합니다. 그렇게 하기 위해서는 *삭제한 노드 직전 노드의 next가 삭제한 노드의 next를 가르키고 있도록 하면 됩니다.즉, A->B->C로 연결된 리스트에서 B를 삭제하면, A->C가 되도록 노드 A의 next가 노드 C를 가르키도록 하는데, 이때 노드 C의 주소는 노드 B의 next에 저장되어 있는 주소 입니다. *

두번째로 고려할 것은, 삭제하는 데이터가 Head일떄 입니다. 이때는 삭제후, Head를 갱신시켜줘야 합니다. A->B->C로 연결되어 있고, 노드 A가 Head이며 노드 A를 삭제할때는 Head가 노드 B가 되도록 갱신시켜줘야 하는데, 노드 B의 주소는 노드 A의 next에 있는 주소입니다. 이때, 단일 리스트에서는 이전 노드로 이동을 못하기 때문에 삭제할 값을 찾을때 현재 노드의 data를 보는 것이 아니라, 현재 노드가 가르키고 있는 다음 노드의 data 값을 기준으로 탐색합니다.

                if node.next.data == data:
                    temp = node.next
                    node.next = node.next.next       
                    del temp                         
                    pass                             
                else:
                    node = node.next

이중 연결 리스트

이중 연결 리스트는 단일 연결 리스트에서 자신의 이전 노드를 접근하지 못하는 문제점을 해결한 데이터 구조입니다. (https://www.fun-coding.org/00_Images/doublelinkedlist.png)

노드(Node):

class Node:
    def __init__(self, data, prev=None, next=None):
        self.prev = prev
        self.data = data
        self.next = next

단일 연결 리스트에서의 노드와 마찬가지로, data는 데이터를 저장하고 next에는 다음 노드의 주소를 저장합니다. 다만, 이중 연결 리스트에서는 이전 노드의 주소를 저장하는 prev 변수가 추가 됐습니다.

이중 연결 리스트:

class NodeMgmt:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def insert_before(self, data, before_data): # 특정 값 이전에 노드 추가
        if self.head == None:
            self.head = Node(data)
            return True            
        else:
            node = self.tail
            while node.data != before_data:
                node = node.prev
                if node == None:
                    return False
            new = Node(data)
            before_new = node.prev
            before_new.next = new
            new.next = node
            return True
    def insert_after(self, data, search_data): # 특정 값 이후에 노드 추가
        node = self.tail 

        while True:
            if node.data == search_data:
                break
            node = node.prev
        new = Node(data)

        if node.next == None:
            self.tail = new

        new.next = node.next
        new.prev = node
        node.next = new

    def insert(self, data):
        if self.head == None:
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            new = Node(data)
            node.next = new
            new.prev = node
            self.tail = new

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

이중 연결 리스트에서 노드를 추가 할때는 next와 prev 둘 다 갱신을 해줘야 하며, 노드가 맨 처음 또는 맨 마지막에 추가됨에 따라서 각각 Head와 Tail을 갱신시켜줘야 되는 것을 유의해야 합니다.

결과 확인하기:

double_linked_list = NodeMgmt(0)
for data in range(1, 10):
    double_linked_list.insert(data)

double_linked_list.insert_before(-1, 0) # 0(첫번째 노드) 이전에 -1 추가하기
double_linked_list.insert_before(8.5, 9) # 9 이전에 8.5 추가하기
double_linked_list.insert_after(2.5, 2) # 2 이후에 2.5 추가하기
double_linked_list.insert_after(9.5, 9) # 9(마지막 노드) 이후에 9.5 추가하기

double_linked_list.desc()

결과: -1 0 1 1.5 2 2.5 3 4 5 6 7 8 8.5 9 9.5

스택은 한쪽에서만 데이터를 접근(추가 & 제거) 할 수 있는 구조이며, LIFO(Last-In-First-Out)/FILO(First-In-Last-Out) 정책에 의해 데이터가 적재(PUSH)되거나 제거(POP) 됩니다. 바닥에 책을 쌓는 것을 생각하면 될거 같습니다. 바닥에 책을 하나씩 차곡차곡 쌓으면 가장 먼저 쌓은 책이 가장 아래에 있고, 책을 치울떄는 가장 나중에 쌓은 위에서부터 치웁니다. (http://www.fun-coding.org/00_Images/stack.png) 스택에서 데이터가 적재되는 것을 Push, 제거되는 것을 Pop 이라고 합니다.

구현하기(파이썬)

data_stack = list()

data_stack.append(1)
data_stack.append(2)

print(data_stack.pop()) # 2 출력

파이썬에서는 리스트에 대해서 append와 pop을 제공하기 때문에 쉽게 사용할 수 있습니다. Append랑 Push랑 같은 개념으로, append()를 하면 해당 리스트의 마지막 인덱스(index)에 값을 적재합니다. pop()을 하면 리스트에서 가장 마지막 인덱스(index)의 값을 반환하고, 리스트에서 해당 값은 제거합니다.

push(), pop() 구현해보기

def push(data):
    stack_list.append(data)

def pop():
    data = stack_list[-1] # index -1 == 리스트에서의 마지막 인덱스
    del stack_list[-1]
    return data

말 그대로, 먼저 들어온 순서대로 먼저 나간다는 것을 뜻합니다. 음식점에서 줄을 서서 밥을 먹는 것을 생각해보면 됩니다. 줄을 서서, 가장 먼저 줄을 섰던 사람이 제일 먼저 식당을 입장하듯, 먼저 들어온 데이터 순서 그대로 먼저 데이터가 사용/출력된다는 것을 뜻합니다. (https://www.fun-coding.org/00_Images/queue.png)

LIFO(Last-In-Frist-Out)

FIFO와 마찬가지로, 말 그대로 해석하면 됩니다. 늦게 들어온 데이터 일수록, 먼저 사용/출력된다는 뜻입니다. LIFO는 다음에 볼 스택(Stack)와 연관이 깊으므로, 스택에서 한번 더 다루도록 하겠습니다.

용어

• Enqueue: 큐(Queue)에 데이터를 적재

• Dequeue: 큐(Queue)에서 데이터를 꺼내기

구현하기(파이썬)

파이썬에서 큐를 구현하기 위해서는 queue 라이브러리를 사용해야합니다. 해당 라이브러리에서는 총 3가지의 큐를 제공합니다.

1. Queue(): 가장 일반적인 큐(FIFO)
2. LifoQueue(): LIFO 큐
3. PriorityQueue(): 큐에 적재되는 데이터마다 우선순위가 정해지고, 우선 순위에 따라서 데이터가 Dequeue 됩니다 (put() == Enqueue, get() == Dequeue)

Queue():

import queue

data_queue = queue.Queue() # First - in - Frist - out

data_queue.put("funcoding") # 'funcoding' Enqueue
data_queue.put(1) # 1 Enqueue
print(data_queue.qsize()) # 큐의 크기 출력 -> 2

print(data_queue.get()) # Dequeue -> 'funcoding' 출력
print(data_queue.get()) # Dequeue -> 1 출력

1보다 'funcoding'이 먼저 큐에 적재되었으므로, Dequeue를 할때도 'funcoding'이 먼저 큐에서 나옵니다.

LifoQueue():

import queue
data_Lqueue = queue.LifoQueue() # Last - in - First - out

data_Lqueue.put("funcoding")
data_Lqueue.put(1)

print(data_Lqueue.get()) # Dequeue -> 1 출력
print(data_Lqueue.get()) # Dequeue -> 'funcoding' 출력

1보다 'funcoding'이 먼저 큐에 적재되었지만, LIFO이므로 Dequeue시 나중에 적재된 1이 먼저 큐에서 나오게 됩니다.

PriorityQueue():

import queue

data_Pqueue = queue.PriorityQueue()

data_Pqueue.put((10, "korea")) # put((우선순위, 데이터)) -> 우선순위 숫자가 낮을 수록 우선순위가 높은 것; (우선순위, 데이터) -> 튜플
data_Pqueue.put((5, 1))
data_Pqueue.put((15, "china")) # 1, 'korea', 'china' 순서로 큐에 적재

print(data_Pqueue.get()) # Dequeue -> (5, 1) 출력
print(data_Pqueue.get()) # Dequeue -> (10, 'korea') 출력
print(data_Pqueue.get()) # Dequeue -> (15, 'china') 출력

PriorityQueue에서는 우선순위에 따라서 Dequeue 됩니다. 데이터를 적재할때 우선순위를 정해주는데, 이때 숫자가 낮을수록 우선순위는 높은것 입니다. 그러므로, Deuque시에는 1, 'korea', 'china' 순으로 큐에서 데이터가 나오게 됩니다.

Enqueue, Dequeue 직접 구현해보기

def enqueue(data):
    queue_list.append(data)

def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

QueryDSL를 이용해서 동적 쿼리를 생성하는 방식들을 보도록 하겠습니다.

Method #1: Boolean Builder

     @Test
    void booleanBuilder() {

        String usernameParam = "MemberA";
        Integer ageParam = 25;

        //SELECT *FROM member WHERE username = "MemberA" AND age = 25;
        List<Member> result = searchMember1(usernameParam, ageParam);
        System.out.println("result.get(0) = " + result.get(0));

        Assertions.assertThat(result.size()).isEqualTo(1);
    }

    private List<Member> searchMember1(String usernameParam, Integer ageParam) {

        BooleanBuilder builder = new BooleanBuilder();
        if (usernameParam != null) {
            builder.and(member.username.eq(usernameParam));
        }
        if (ageParam != null && ageParam >= 0) {
            builder.and(member.age.eq(ageParam));
        }

        return factory
                .selectFrom(member)
                .where(builder)
                .fetch();
    }

BooleanBuilder를 통해서 파라미터 값이 존재 할때 조건에 WHERE 조건에 추가되도록 합니다. BooleanBuilder를 통해 로직에 따라서 WHERE에 추가할 조건들을 지정해 줄 수 있으며, WHERE에 해당 BooleanBuilder를 넣으면 조건에 맞에 WHERE문이 처리 됩니다.

Method #2: 조건 나열하기

    @Test
    void WhereParam() {

        String usernameParam = "MemberA";
        Integer ageParam = 25;

        List<Member> result = searchMember2(usernameParam, ageParam);
        System.out.println("result.get(0) = " + result.get(0));

        Assertions.assertThat(result.size()).isEqualTo(1);
    }

    private List<Member> searchMember2(String usernameParam, Integer ageParam) {
        return factory
                .selectFrom(member)
                .where(usernameEq(usernameParam), ageEq(ageParam)) //where(null)이면 무시 됨 -> ex: where(null, member.username.eq("MemberA")) 이면 null은 무시되고, username = "MemberA" 조건만 추가됨
                .fetch();
    }

    private BooleanExpression usernameEq(String usernameParam) {
        // NULL이 아니면 WHERE 조건 추가됨; NULL 이면 NULL을 그대로 반환
        return usernameParam != null ? member.username.eq(usernameParam) : null;
    }
    private BooleanExpression ageEq(Integer ageParam) {
        // NULL이 아니면 WHERE 조건 추가됨; NULL 이면 NULL을 그대로 반환
        return ageParam != null ? member.age.eq(ageParam) : null;
    }

QueryDSL에서 WHERE 문에 조건들을 추가할때 원하는 조건들을 그대로 나열해서 작성할 수 있는 특성을 이용한 방식입니다. 대신, where()에서 null 값은 무시되다는 특징을 이용해서 로직에 따라서 WHERE에 조건을 추가할지, 아니면 null을 추가할지 정해줍니다.

QueryDSL에서 DTO로 변환해서 값을 반환하는 것을 알아보도록 하겠습니다.

DTO(MemberDTO)

@Data
@ToString(of = {"id", "username", "age"})
public class MemberDTO {

    private Long id;
    private String username;
    private int age;
    private Team team;

    public MemberDTO() {

    }

    public MemberDTO(String username, int age) {
        this.username = username;
        this.age = age;
    }
}

Method #1: Setter

    @Test
    void findDtoBySetter() {
        //Setter로 값을 가져옴
        List<MemberDTO> result = factory
                .select(Projections
                        .bean(MemberDTO.class, member.username, member.age))
                .from(member)
                .fetch();

        Assertions.assertThat(result).extracting("username", "age")
                .containsExactly(new Tuple("MemberA", 25),
                        new Tuple("MemberB", 35),
                        new Tuple("MemberC", 45),
                        new Tuple("MemberD", 55));
    }

DTO에서의 Setter을 사용해서 값들을 주입해주는 방식입니다. SELECT에서 Projections.bean(DTO.class, parameter...) 을 이용해서 원하는 DTO에 원하는 값들을 주입합니다. 이때, 값을 가져오는 엔티티에서의 속성 이름이랑 DTO에서의 속성 이름이 같아서 매칭되는 속성에 값들이 주입되는 점을 주의하시면 됩니다. 또한, DTO에 Setter가 있어야 작동하는 점도 주의하시면 됩니다.

Method #2: Field

    @Test
    void findDtoByField() {
        //값들을 바로 속성 값으로 넣어줌
        List<MemberDTO> result = factory
                .select(Projections
                        .fields(MemberDTO.class, member.username, member.age))
                .from(member)
                .fetch();


        Assertions.assertThat(result).extracting("username", "age")
                .containsExactly(new Tuple("MemberA", 25),
                        new Tuple("MemberB", 35),
                        new Tuple("MemberC", 45),
                        new Tuple("MemberD", 55));
    }

DTO의 Field에 값들 바로 주입하는 방식입니다. SELECT에서 Projections.fields(DTO.class, parameter...) 을 이용해서 원하는 DTO에 원하는 값들을 주입합니다. 이때, 값을 가져오는 엔티티에서의 속성 이름이랑 DTO에서의 속성 이름이 같아서 매칭되는 속성에 값들이 주입되는 점을 주의하시면 됩니다.

Method #3: Constructor

    @Test
    void findDtoByConstructor() {
        List<MemberDTO> result = factory
                .select(Projections
                        .constructor(MemberDTO.class, member.username, member.age))
                .from(member)
                .fetch();

        Assertions.assertThat(result).extracting("username", "age")
                .containsExactly(new Tuple("MemberA", 25),
                        new Tuple("MemberB", 35),
                        new Tuple("MemberC", 45),
                        new Tuple("MemberD", 55));
    }

Projections.constructor(DTO.class, parameters...) 를 통해 DTO의 생성자들을 통해서 값들을 주입하는 방식입니다. 이 방식은 순수 JPA에서 DTO로 값들을 반환할때랑 비슷한 방식입니다. 해당 방식을 사용할 경우에는, 목적에 맞는 생정자가 필요한 점을 주의하시면 됩니다.

Entity랑 DTO의 속성 값이 다를때는?

첫번째 방식과 두번째 방식은 Entity의 속성 값과 DTO에서의 속성 값이 같을때 사용 가능합니다. 다를 경우에는 오류가 발생하는데, 다를 경우의 해결방법을 보도록 하겠습니다.

DTO(UserDTO)

@Data
public class UserDTO {

    private String name;
    private int age;

    public UserDTO() {
    }

    public UserDTO(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

Entity에서의 username이 UserDTO는 name으로 변경 됐습니다. username을 name에 넣는 방식을 보도록 하겠습니다.

Solution:

    @Test
    void findByUserDto() {
        List<UserDTO> result = factory
                .select(Projections.fields(UserDTO.class, member.username.as("name"), member.age))
                .from(member)
                .fetch();

        Assertions.assertThat(result).extracting("name", "age")
                .containsExactly(new Tuple("MemberA", 25),
                        new Tuple("MemberB", 35),
                        new Tuple("MemberC", 45),
                        new Tuple("MemberD", 55));

    }

별칭을 지정해 주는 as(alias)을 이용해서 오류를 해결합니다. 만약에 as(alias)로 별칭을 지정해 주지 않으면, UserDTO에는 username과 매칭되는 속성 값이 없기 때문에 name에는 null 값이 저장됩니다. 그렇기 때문에, as(alias)를 이용해서 member.username이 UserDTO의 name과 매칭된다는 것을 알려줍니다.(member.username.as("name")). 또 다른 해결방안은 세번째 방식이였던 생성자를 통해 속성 값들을 주입시켜주는 방식입니다.

+ Subquery

    @Test
    void findByUserDtoSubQueryAlias() {
        QMember subMember = new QMember("sub");

        List<UserDTO> result = factory
                .select(Projections.fields(UserDTO.class,
                        member.username.as("name"),
                        ExpressionUtils.as(JPAExpressions
                                .select(subMember.age.max())
                                .from(subMember), "age")))
                .from(member)
                .fetch();

        Assertions.assertThat(result).extracting("name", "age")
                .containsExactly(new Tuple("MemberA", 55),
                        new Tuple("MemberB", 55),
                        new Tuple("MemberC", 55),
                        new Tuple("MemberD", 55));

    }

해당 예제는 member.username -> UserDTO.name, 그리고 member.age의 최댓값 -> UserDTO.age 로 변환하는 방법입니다. 여기서 눈 여겨 볼 것은 member.age의 최댓값을 서브쿼리로 가져와야 되는데, 서브쿼리로 받은 값에도 별칭을 지정해주는 것 입니다. ExpressionUtils.as(JPAExpressions.select(subMember.age.max()).from(subMember), "age"))) 서브쿼리를 이용해서 최댓값을 가져오는 것은 앞서 서브쿼리에서 봤던 것과 같은데, 여기서 "age" 로 별칭을 지정해 줄 수 있다는 것이 중요한 부분입니다.

    @Test
    void subQuery() {
        factory = new JPAQueryFactory(em);
        QMember member = QMember.member;
        QMember subMember = new QMember("sub"); // 서브쿼리 안에 있는 Member는 Alias 를 다르게 해줘야 하기 때문에 new QMember(name) 으로 Alias를 설정해서 생성

        List<Member> result = factory
                .selectFrom(member)
                .where(member.age.eq(
                        JPAExpressions
                                .select(subMember.age.max())
                                .from(subMember)
                ))
                .fetch();
        //eq 외 gt, goe 등등 모두 사용 가능

        Assertions.assertThat(result).extracting("age")
                .containsExactly(55);

    }

SELECT *FROM member WHERE age = (SELECT max(sub.age) FROM member sub);

WHERE Subquery + IN

    @Test
    void subQueryIn() {
        factory = new JPAQueryFactory(em);
        QMember member = QMember.member;
        QMember subMember = new QMember("sub"); // 서브쿼리 안에 있는 Member는 Alias 를 다르게 해줘야 하기 때문에 new QMember(name) 으로 Alias를 설정해서 생성

        List<Member> result = factory
                .selectFrom(member)
                .where(member.age.in(
                        JPAExpressions
                                .select(subMember.age)
                                .from(subMember)
                                .where(subMember.age.gt(40))
                ))
                .fetch();

        Assertions.assertThat(result).extracting("age")
                .containsExactly(45, 55);

    }

SELECT * FROM member WHERE age IN (SELECT sub.age FROM member sub WHERE sub.age > 40);

SELECT Subquery

    @Test
    void subQuerySelect() {
        factory = new JPAQueryFactory(em);
        QMember member = QMember.member;
        QMember subMember = new QMember("sub"); // 서브쿼리 안에 있는 Member는 Alias 를 다르게 해줘야 하기 때문에 new QMember(name) 으로 Alias를 설정해서 생성

        List<Tuple> result = factory.select(member.username,
                        JPAExpressions
                                .select(subMember.age.avg())
                                .from(subMember))
                .from(member)
                .fetch();

        for (Tuple tuple : result) {
            System.out.println("tuple = " + tuple);
        }


        Assertions.assertThat(result.get(0).get(1, Double.class)).isEqualTo(40);
    }

SELECT member.username, (SELECT avg(sub.age) FROM member sub) FROM member;

주의할 점: *1. * 서브쿼리를 사용할때는 각각 다른 Alias로 해줘야 하는데, QueryDSL에서는 Q 엔티티를 생성할때 Alias를 지정해 줄 수 있습니다. 예를 들어, Member에 대해서 서브쿼리를 실행할 경우에는, new QMember("A")으로 SQL에서 'Member as A'/'Member A'와 같은 효과를 줄 수 있습니다. *2. * JPA JPQL에서 기본적으로 from에서의 서브쿼리는 지원하지 않습니다. 그렇기 때문에 QueryDSL에서도 from에서 서브쿼리를 실행 할 수 없습니다.

QueryDSL에서 JOIN을 하는 방식과, 각 JOIN을 했을때의 차이점들을 보도록 하겠습니다.

Inner Join

    @Test
    void join1() {
        factory = new JPAQueryFactory(em);
        QTeam team = QTeam.team;
        QMember member = QMember.member;

        /**
         * select member0_.member_id as member_i1_0_, member0_.created_date as created_2_0_, member0_.last_modified_date as last_mod3_0_, member0_.age as age4_0_, member0_.team_id as team_id6_0_, member0_.username as username5_0_
         * from member member0_
         * inner join team team1_
         * on member0_.team_id=team1_.team_id
         * where team1_.name='TeamA';
         */
        List<Member> members = factory.selectFrom(member)
                .join(member.team, team) // join() == innerJoin(); leftJoin, rightJoin()도 가능
                .where(team.name.eq("TeamA"))
                .fetch();

        Assertions.assertThat(members)
                .extracting("username")
                .containsExactly("MemberA", "MemberB", "MemberC");
    }

처리되는 쿼리문:

select member0_.member_id as member_i1_0_, member0_.created_date as created_2_0_, member0_.last_modified_date as last_mod3_0_, member0_.age as age4_0_, member0_.team_id as team_id6_0_, member0_.username as username5_0_
from member member0_
inner join team team1_
on member0_.team_id=team1_.team_id
where team1_.name='TeamA';

Outer Join

    @Test
    void join2() {
        factory = new JPAQueryFactory(em);
        QTeam team = QTeam.team;
        QMember member = QMember.member;

        List<Tuple> resultLeftJoin = factory
                .select(member, team)
                .from(member)
                .leftJoin(member.team, team)
                .on(team.name.eq("TeamA"))
                .fetch();

        Assertions.assertThat(resultLeftJoin.size()).isEqualTo(4);
    }

처리되는 쿼리문:

select member0_.member_id as member_i1_0_0_, team1_.team_id as team_id1_1_1_, member0_.created_date as created_2_0_0_, member0_.last_modified_date as last_mod3_0_0_, member0_.age as age4_0_0_, member0_.team_id as team_id6_0_0_, member0_.username as username5_0_0_, team1_.created_date as created_2_1_1_, team1_.last_modified_date as last_mod3_1_1_, team1_.name as name4_1_1_
from member member0_
left outer join team team1_
on member0_.team_id=team1_.team_id and (team1_.name='TeamA');

Inner Join vs. Outer Join

Inner Join:

(SELECT m., t. FROM member m JOIN team t ON m.team_id=t.id AND t.name = 'TeamA';) tuple = [Member(id=3, username=MemberA, age=25), Team(id=1, name=TeamA)] tuple = [Member(id=4, username=MemberB, age=35), Team(id=1, name=TeamA)] tuple = [Member(id=5, username=MemberC, age=45), Team(id=1, name=TeamA)]

Outer Join:

(SELECT m., t. FROM member m LEFT JOIN team t ON m.team_id=t.id AND t.name = 'TeamA';) tuple = [Member(id=3, username=MemberA, age=25), Team(id=1, name=TeamA)] tuple = [Member(id=4, username=MemberB, age=35), Team(id=1, name=TeamA)] tuple = [Member(id=5, username=MemberC, age=45), Team(id=1, name=TeamA)] tuple = [Member(id=6, username=MemberD, age=55), null]

Inner Join의 경우 조인하는 테이블(Team)이 조건에 맞는 경우들의 값들만 반환하며, Outer Join의 경우 조인 당하는 테이블(Member)의 모든 값들을 반환하는데, 조건이 맞을 경우 Team의 값들도 같이 보여주며, 조건에 맞지 않을경우 null을 반환합니다. 해당 내용은 SQL에서의 JOIN과 관련된 내용이므로, 더 자세한 설명은 SQL의 JOIN을 학습하시면 됩니다.

JOIN FETCH

    @Test
    void fetchJoinYes() {
        factory = new JPAQueryFactory(em);
        QMember member = QMember.member;
        QTeam team = QTeam.team;

        em.flush();
        em.clear();

        Member findMember = factory
                .selectFrom(member)
                .join(member.team, team).fetchJoin()
                .fetchFirst();

        boolean isLoaded = emf.getPersistenceUnitUtil().isLoaded(findMember.getTeam()); //로딩이 된 엔티티인지 아닌지 알려줌
        Assertions.assertThat(isLoaded).isTrue();
    }

QueryDSL에서 JOIN FETCH를 하고 싶은 경우, fetchJoin()을 추가하면 됩니다. JOIN FETCH에 관한 내용은 https://velog.io/@k_ms1998/JPA-JPQL-%EC%A1%B0%EC%9D%B8JOIN 을 참고하시면 됩니다.

QueryDSL을 이용해서 MySQL에서 제공하는 함수들 사용과 Group By를 사용하는 것을 보도록 하겠습니다.

함수 + Group By

    @Test
    void groupBy() {
        factory = new JPAQueryFactory(em);
        QTeam team = QTeam.team;
        QMember member = QMember.member;

        List<Tuple> result = factory.select(team.name, member.age.avg(), member.count())
                .from(member)
                .join(member.team, team) // member LEFT JOIN team
                .groupBy(team.name)
                .having(member.age.avg().goe(25)) // having도 사용 가능
                .fetch();
        for (Tuple tuple : result) {
            System.out.println("tuple = " + tuple);
        }

    Tuple tupleA = result.get(0); //tuple = [TeamA, 35.0, 3]
    Tuple tupleB = result.get(1); //tuple = [TeamB, 55.0, 1]

    Assertions.assertThat(tupleA.get(member.age.avg())).isEqualTo(35);
    Assertions.assertThat(tupleB.get(member.age.avg())).isEqualTo(55);

groupBy()를 통해 Grouping을 할 수 있으며, having()도 사용할 수 있습니다. 사용 가능한 함수들은 member.count(), member.age.sum(), member.age.avg(), member.age.max(), member.age.min() 등등이 있습니다. member.age.avg()를 할 경우, Member의 age의 평균 값을 가져옵니다.

    @Test
    void queryDslOrderBy() {
        /**
         * 회원 정렬 순서:
         * 1. 회원 나이 내림차순 DESC
         * 2. 회원 이름 오름차순 ASC
         * => select *from member order by age desc, username asc;
         */
        em.persist(new Member("MemberE", 35));
        em.persist(new Member(null, 35));

        factory = new JPAQueryFactory(em);
        QMember member = QMember.member;

        List<Member> members = factory
                .select(member)
                .from(member)
                .orderBy(member.age.desc(), member.username.asc().nullsLast()) // nullsLast() -> null일 경우 마지막 순서로 가져옴; nullsFirst() -> null일 경우 처음으로 가져옴
                .fetch();

    }

orderBy()로 Order By를 처리할 수 있습니다. 이때, 쿼리문과 비슷하게 orderBy() 안에 복수의 Column들을 상대로 어떻게 정렬할지 정할 수 있습니다. 해당 예제에서는 Member의 age를 내림차순으로 정렬하고, age가 같을 경우 username을 오름차순으로 정렬합니다. 또한, 해당 Column의 값이 NULL일 경우, 해당 튜플을 맨 처음으로 보여줄지(nullsFirst()) 또는 맨 마지막으로 보여줄지(nullsLast()) 지정할 수 있습니다.

Paging

    @Test
    void queryDslPaging() {
        factory = new JPAQueryFactory(em);
        QMember member = QMember.member;

        List<Member> members = factory.selectFrom(member)
                .offset(1)
                .limit(2)
                .fetch();


        Assertions.assertThat(members.size()).isEqualTo(2);
        Assertions.assertThat(members.get(0).getUsername()).isEqualTo("MemberC");
    }

쿼리문 'SELECT *FROM member LIMIT 2 OFFSET 1;' 가 실행됩니다. 페이징 같은 경우에는 매우 직관적으로 사용이 가능합니다.

QueryDSL에서 쿼리문을 처리한 후 반환되는 데이터를 조회하는 방법들을 보겠습니다.

// Member 테이블에는 총 4개의 튜플, Team 테이블에는 총 1개의 튜플이 저장되어 있습니다
    @Test
    void queryDslProjectionBasic() {
        factory = new JPAQueryFactory(em);
        QMember member = QMember.member;
        QTeam team = QTeam.team;

        List<Member> membersFetch = factory
                .selectFrom(member)
                .fetch();

        Team teamFetchOne = factory
                .selectFrom(team)
                .fetchOne();

        Member membersFetchFirst = factory
                .selectFrom(member)
                .fetchFirst();

        Long memberCount = factory
                .select(member.count())
                .from(member)
                .fetchOne();

        Assertions.assertThat(membersFetch.size()).isEqualTo(4);
        Assertions.assertThat(teamFetchOne.getName()).isEqualTo("TeamA");
        Assertions.assertThat(membersFetchFirst).isInstanceOf(Member.class);
        Assertions.assertThat(memberCount).isEqualTo(4);
    }

1. fetch(): ** 쿼리문을 처리 한 후, 반환되는 값들을 그대로 리스트로 가져옵니다. 이떄, 반환되는 데이터가 없으면 빈 리스트(Empty List)가 반환됩니다. *2. fetchOne(): * 단 하나의 데이터를 조회합니다. 쿼리문에 의해 반환되는 데이터가 0개 이면 NULL 반환, 1개이면 정상, 그리고 **2개 이상일 경우에는 NonUniqueResultException가 발생합니다. 3. fetchFirst(): ** limit(1).fetchOne()과 동일하며, 항상 한개의 데이터만 조회됩니다. **4-1. fetchResult(): 페이징 정보 포함 & count 쿼리도 같이 실행됩니다. But, deprecated. 4-2. fetchCount(): 쿼리를 count 쿼리로 변경해서, count 값일 반환합니다. But, deprecated. 4-3. fetch + count:

        Long memberCount = factory
                .select(member.count())
                .from(member)
                .fetchOne();

buildscript {
    ext {
        queryDslVersion = "5.0.0"
    }
}


plugins {
    id 'org.springframework.boot' version '2.6.7'
    id 'io.spring.dependency-management' version '1.0.11.RELEASE'
    id "com.ewerk.gradle.plugins.querydsl" version "1.0.10"    //querydsl 추가
    id 'java'
}

group = 'study'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = '11'

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    implementation 'org.springframework.boot:spring-boot-starter-data-jpa'
    implementation 'org.springframework.boot:spring-boot-starter-web'

    implementation "com.querydsl:querydsl-jpa:${queryDslVersion}"
    implementation "com.querydsl:querydsl-apt:${queryDslVersion}"

    implementation 'com.github.gavlyukovskiy:p6spy-spring-boot-starter:1.5.8'

    compileOnly 'org.projectlombok:lombok'
    runtimeOnly 'com.h2database:h2'
    annotationProcessor 'org.projectlombok:lombok'
    testImplementation 'org.springframework.boot:spring-boot-starter-test'
}

tasks.named('test') {
    useJUnitPlatform()
}

//querydsl 추가 시작
def querydslDir = "$buildDir/generated/querydsl"

querydsl {
    jpa = true
    querydslSourcesDir = querydslDir
}
sourceSets {
    main.java.srcDir querydslDir
}
compileQuerydsl{
    options.annotationProcessorPath = configurations.querydsl
}
configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
    querydsl.extendsFrom compileClasspath
}
//querydsl 추가 끝

확인하기

QueryDSL 라이브러리가 제대로 설치 됐는지 확인하기 위해서 Test 엔티티 하나를 추가합니다.

@Entity
@Getter
@Setter
public class TmpEntity {
    @Id
    @GeneratedValue
    private Long id;
}

엔티티를 생성한 후, IntelliJ 기준 우측 상단에 있는 Gradle 탭을 누르면 해당 메뉴가 뜹니다. 해당 메뉴에서 'compileQuerydsl' 을 실행합니다. 실행하면, build.gradle 에서 설정한 경로('def querydslDir = "$buildDir/generated/querydsl"')에 파일이 생성됩니다.

사진처럼 Q+엔티티 이름의 클래스가 생성되면 정상적으로 QueryDSL이 설치가 완료된 것입니다.

API 요청이 들어올때, 요청의 파라미터 값으로 바로 페이징 하는 방법을 알아보도록 하겠습니다

Controller

@RestController
@RequiredArgsConstructor
public class MemberController {

    private final MemberDataRepository memberRepository;

    @GetMapping("/members")
    public Page<MemberDTO> list(@PageableDefault(size = 15) Pageable pageable) {
        Page<Member> findMembers = memberRepository.findControllerBy(pageable);
        return findMembers.map(m -> new MemberDTO(m));
    }

}

GET /members로 요청을 보낼때 파라미터 값으로, page, size, sort을 보내주면, 자동으로 Pageable의 조건으로 들어가서, 페이징 조건에 따라서 데이터를 반환 받을 수 있습니다.

1. /members?page=1 -> page = 1 값을 자동으로 pageable에 넣어서 파라미터로 넘겨줍니다 (이때, DEFAULT의 size 값은 20으로 넘어갑니다)
2. /members?page=1&size=5 -> page = 1, size = 5 값을 자동으로 pageable에 넣어서 파라미터로 넘겨줍니다.
3. /members?page=1&size=5&sort=id,desc -> page = 1, size = 5, id를 내림차순으로 정렬하는 값을 자동으로 pageable에 넣어서 파라미터로 넘겨줍니다.
   • @PageableDefault로 페이징할 조건들의 기본값들을 지정해 줄 수 있습니다. (page, size, sort)

지금까지 봐왔던 예시에서는 모든 엔티티들의 PK들이 @GeneratedValue를 사용해서 자동으로 Long 타입으로 부여되도록 했습니다. 하지만, 실무에서는 이런 방식으로만 PK를 부여하기에는 한계가 있습니다. 회원정보의 PK를 Unique하게 하기 위해서 UUID로 설정을 하게 되기만 하더라도 회원정보 엔티티의 PK는 String으로 해줘야 합니다. 이런 경우에 발생하는 성능적인 문제와 해결 방법을 보도록 하겠습니다.

문제가 생기는 이유

@GeneratedValue를 사용해서 DB에서 자동으로 PK값을 순차적으로 부여해줄 경우, JPA에서 바로 persist()를 호출 한 후, DB에 값이 저장된 후에 PK값이 부여됩니다. 그러나, @GeneratedValue를 사용하지 않아서 개발자가 직접 PK값을 부여해주는 경우, PK값이 부여된 상태에서 DB로 값이 넘어가게 됩니다. 이때, PK값이 부여됐기 때문에, JPA는 merge()를 호출합니다. merge()를 호출할 경우, DB에 접근을 해서 동일한 PK 값을 가진 데이터가 있는 지 먼저 확인을 한 후, 데이터가 없을 경우에 새로운 데이터로 인지하고 저장을하게 됩니다. 그렇기 때문에, 데이터를 저장하기 전에 추가로 DB를 접근하기 때문에 비효율 적입니다. 이런 문제를 해결하기 위해서 Persistable을 사용합니다.

엔티티( +BaseEntity)

DataBaseTimeEntity

@EntityListeners(AuditingEntityListener.class)
@Getter
@MappedSuperclass // BaseEntity의 속성들을 상속 받는 엔티티 들이 속성 값들로 가질수 있도록 해줌
public class DataBaseTimeEntity {

    @CreatedDate
    @Column(updatable = false) //해당 값을 한번 생성하면 변할수 없도록 해줌
    protected LocalDateTime createdDate;

    @LastModifiedDate
    protected LocalDateTime lastModifiedDate;

}

Item

@Entity
@Getter
public class Item extends DataBaseTimeEntity implements Persistable<String>{

    @Id
    private String id;

    protected Item() {
    }

    public Item(String id) {
        this.id = id;
    }

    /**
     * Persistable 을 상속 받아서 isNew() 메서드에서 해당 엔티티가 새로운 엔티티인지 아닌지를 판별해 줄 수 있다.
     * 새로운 엔티티이면, createdDate가 NULL이기 때문에, createdDate가 NULL인지 아닌지에 따라서 판별하도록하면 편리합니다.
     */
    @Override
    public boolean isNew() {
        return this.createdDate == null;
    }
}

위에서 살펴본 문제를 해결하기 위해서 엔티티에 Persistable<ID>를 상속받습니다(ID는 PK값의 타입). Persistable은 getId()와 isNew() 메서드를 가지고 있으며, isNew()에서는 저장할려는 엔티티가 DB에 존재하는지 존재하지 않는지 판별해주는 메서드 입니다. 이때, isNew()는 오버라이딩해서 개발자가 직접 로직을 구현해 주면 됩니다. 추천드리는 방법은 createdDate를 확인하는것 입니다. createdDate는 엔티티가 DB에 존재하지 않는 엔티티라면 null 값을 가지고 있습니다. 그렇기 떄문에 null 값을 갖고 있으면 새로운 엔티티라는 것을 알 수 있습니다.

결과:

• Scenario #1: Item.id -> Long && @Generated Value:

1.insert into item (id) values (?);

• Scenario #2: Item.id -> String without Persistable: 1.select item0_.id as id1_0_0_ from item item0_ where item0_.id=?;
  2. insert into item (id) values (?);
  • Scenario #3: Item.id -> String w/ Persistable:
  1. insert into item (id) values (?);
  *보다시피, Persistable을 사용하지 않았을때에는 DB에 해당 PK값을 가진 엔티티가 있는 확인을 하는 쿼리문이 추가로 실행됩니다. *