[알고리즘] 정렬 (선택, 버블, 삽입, 퀵, 머지, 계수)

정렬(sorting)

데이터를 특정한 기준에 따라서 순서대로 나열하는 것

 

선택정렬(Selection sort)

가장작은 데이터를 찾은 후에 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 가장 작은 데이터를 찾은 후 두번째 데이터와 바꾼다. 가장 낮은 값이 맨 앞부터 정렬되며 전체 배열들이 정렬 될 때까지 이 과정을 계속 반복하여 정렬하는 과정을 선택정렬이라고 한다. 

선택정렬은 구현이 간단하지만, 시간 복잡도가 (N^2 + N) / 2 이다. 즉 빅오표기법으로 O(N^2) 이다.

선택정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적이다. 

 

선택 정렬 소스코드.py

array = [22, 50, 17, 25, 18, 32, 33, 44, 29, 8]

for i in range(len(array)):
    min_index = i  # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]

print(array)

# 결과
# [8, 17, 18, 22, 25, 29, 32, 33, 44, 50]

 

선택 정렬 소스코드.java

import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] array = new int[]{22, 50, 17, 25, 18, 32, 33, 44, 29, 8};

        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if(array[minIndex] > array[j]){
                    minIndex = j;
                }
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        System.out.println(Arrays.toString(array));
    }
}

 

 

버블정렬 (Bubble sort)

1. 버블정렬은 i(처음에는 0번째 인덱스) 인덱스부터 i+1(인접한 인덱스)와 값을 비교한다.
2. i 인덱스가 크다면 i+1인덱스와 위치를 바꾼다.
3. i+1인덱스가 크면 다음 인덱스와 인접 인덱스를 비교한다. 
4. 2-3 과정을 한번 반복하면 맨 마지막 인덱스에 리스트 중 가장 큰 값이 정렬된다.
5. 4 과정을 계속 반복하면 가장 큰 값부터 마지막 인덱스부터 처음 인덱스까지 오름차순 정렬된다.

버블 정렬은 선택정렬과 마찬가지로 전체를 비교하기 때문에 시간복잡도는 O(N^2) 이다.

 

버블 정렬 소스코드.py

array = [34, 6, 41, 16, 38, 36, 28, 19, 45, 43, 49]

for i in range(len(array)):
    for j in range(0, len(array)-i-1):
        # 만약 현재 인덱스의 값이 다음 인덱스의 값보다 클 경우 실행함.
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]

print(array)

# 출력
# [6, 16, 19, 28, 34, 36, 38, 41, 43, 45, 49]

 

 

버블 정렬 소스코드.java

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = new int[]{34, 6, 41, 16, 38, 36, 28, 19, 45, 43, 49};

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                // 현재 인덱스의 값이 다음 인덱스의 값보다 클 경우 실행
                if(array[j] > array[j + 1]){
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

 

삽입 정렬 (Insertion sort)

삽입정렬은 탐색하고 있는 현재 위치에서 맨 처음 배열까지 비교하여 자신이 들어갈 위치를 찾아 그 위치에 해당 값을 삽입하는 알고리즘이다. 

1. 두번째 인덱스(i) 부터 시작하며 첫번째 인덱스(i-1)와 값을 비교한다.
2. 두번째 인덱스(i)가 첫번째 인덱스(i-1)보다 작다면 두번째 인덱스(i) 를 첫번째 인덱스 앞에 정렬한다.
3. i를 1씩 증가시키면서 첫번째 인덱스와 i-1 인덱스 사이의 배열 중에서 현재 i인덱스의 값이 들어갈 곳을 찾는다
4. 해당 인덱스 위치에 값을 삽입한다.
5. 맨 끝 인덱스까지 같은 과정을 반복하면 삽입 정렬의 연산이 끝난다.

삽입정렬은 선택정렬에 비해 구현 난이도는 높지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다.

삽입정렬은 데이터가 거의 정렬 되어있을 때 훨씬 효율적이다. 

삽입정렬의 시간복잡도는 O(N^2) 이다. 삽입 정렬은 리스트에서 데이터가 거의 정렬되어 있는 상태라면 최선의 경우에 O(N)의 시간복잡도를 가진다.

삽입정렬은 퀵 정렬과 비교했을 때 삽입정렬이 보통 비효율적이지만 데이터가 거의 정렬된 상태라면 삽입정렬을 이용하는 것이 시간복잡도 측면에서 이득을 볼 수 있다.

 

삽입 정렬 소스코드.py

array = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

for i in range(1, len(array)):
    for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법
        if array[j] < array[j - 1]:  # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

# 출력
# [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

 

삽입 정렬 소스코드.java

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] array = new int[]{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        for (int i = 1; i < array.length; i++) {
            for (int j = i; j >= 1; j--) {
                if(array[j] < array[j-1]){
                    int temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                } else break;
            }
        }
        System.out.println(Arrays.toString(array));
    }
}

 

퀵 정렬 (Quick sort)

기준 데이터를 설정하고 그 기준보다 작은 데이터와 큰 데이터를 서로 바꿔서 정렬하는 방법.

퀵 정렬에는 피봇(Pivot)이라는 개념이 사용된다. 피봇은 한 마디로 정렬 될 기준 원소를 뜻한다. 피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있다. 최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다. 보통 배열의 첫 번째 값이나 중앙 값을 선택한다. 퀵 정렬의 동작방식은 다음과 같다. 가령 예를 들어 배열 [5, 6, 1, 4, 2, 3, 7]이 있고, 피봇을 임의로 4를 선택했다 가정하자. 이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [1, 2, 3] < 4 < [5, 6, 7]를 생성한다. 다시 왼쪽에서부터 임의의 피봇 2를 설정하여 [1] < 2 < [3]을 생성하고 오른쪽에선 임의의 피봇 6를 설정하여 [5] < 6 < [7]로 나눈다. 만약 배열 길이가 1이 된다면 가장 정렬 완료된 것이므로 분할된 배열을 합쳐 줌으로써 정렬을 마친다. 
- 출처: https://roytravel.tistory.com/328 - 

 

이 포스트에서 퀵 정렬은 호어 분할 방식을 기준으로 퀵 정렬을 정의한다. 자세한 동작방식은 아래와같다. 

1. 기준 데이터인 축(Pivot)을 정한다.
2. 축(Pivot)은 리스트에서 첫번째 값으로 정한다. 
3. low는 오른쪽으로, high는 왼쪽으로 이동하게 되는데 이 때
4. 피벗으로 설정한 첫번째 인덱스를 제외하고 두번째 인덱스와 마지막 인덱스의 값을 서로 비교한다
5. 만약 두 인덱스가 피벗값을 기준으로 low인덱스가 피벗값보다 높고 high인덱스가 피벗값 보다 낮다면 두 인덱스를 교환한다.
6. 교환하면 low를 오른쪽으로 한칸, high를 왼쪽으로 한칸 옮기고 pivot값을 기준으로 두 인덱스를 비교한다. 
7. 만약 low는 pivot보다 큰 수를 만나거나 pivot을 만나면 멈추고, 
8. high는 pivot보다 작은 수를 만나거나 pivot을 만나면 멈춘다.
9. 위의 과정을 low가 high의 오른쪽에 올때까지 반복한다. 
10. low와 pivot 값을 바꾼다.
11. pivot기준으로 작은 리스트들과 pivot기준으로 큰 리스트들로 구분된다.
12. 1-10 연산을 두 리스트에 반복한다. 
    
    

이미지 출처: https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

 

퀵 정렬의 평균 시간복잡도는 O(NlogN)이다. 최악의 경우 O(N^2)이다

퀵정렬은 데이터가 무작위로 정렬되어 있는경우 빠르게 동작할 확률이 높다

앞서 pivot을 가장 왼쪽 데이터로 삼을 때 이미 데이터가 정렬되어 있는 경우 매우 느리게 동작한다.

기준이되는 pivot 값을 랜덤으로 하거나 중간값으로 한다.

즉, pivot을 어떻게 설정하느냐에 따라 성능의 편차가 심하다.

 

퀵 정렬 소스코드.py

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        # 피벗보다 큰 데이터를 찾을 때까지 반복 
        while(left <= end and array[left] <= array[pivot]):
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -= 1
        if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

 

파이썬의 장점을 살린 퀵 정렬 소스코드.py

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

 

퀵 정렬 소스코드.java

import java.util.*;

public class Main {

    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return; // 원소가 1개인 경우 종료
        int pivot = start; // 피벗은 첫 번째 원소
        int left = start + 1;
        int right = end;
        while (left <= right) {
            // 피벗보다 큰 데이터를 찾을 때까지 반복
            while (left <= end && arr[left] <= arr[pivot]) left++;
            // 피벗보다 작은 데이터를 찾을 때까지 반복
            while (right > start && arr[right] >= arr[pivot]) right--;
            // 엇갈렸다면 작은 데이터와 피벗을 교체
            if (left > right) {
                int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            }
            // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            else {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }

    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        quickSort(arr, 0, n - 1);

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

 

병합 정렬 (Quick sort)

퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다.

차이점은 퀵 정렬이 피봇 선택 이후 피봇 기준으로 대소를 비교하는 반면, 병합 정렬은 배열을 원소가 하나만 남을 때 까지 계속 이분할 한 다음, 대소관계를 고려하여 다시 재배열 하며 원래 크기의 배열로 병합한다

시간 복잡도의 경우 최선, 평균, 최악 모두 O(NlogN) 이며 공간 복잡도의 경우 정렬된 원소를 담을 배열이 하나 필요로 하므로 O(N) 이다. 

 

머지 정렬 소스코드 - TopDown.java

import java.util.Arrays;

public class MergeSort_TopDown {

    public static void main(String[] args) {
        int[] array = new int[]{7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    // 합치는 과정에서 정렬하여 원소를 담을 임시 배열
    private static int[] sorted;

    public static void mergeSort(int[] arr) {
        sorted = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1);
        sorted = null;
    }

    // Top-Down 방식 구현
    private static void mergeSort(int[] arr, int left, int right) {
        /*
         * left == right 즉, 부분리스트가 1개의 원소만 갖고 있는 경우
         * 더 이상 쪼갤 수 없으므로 return 함
         */
        if (left == right) return;
        int mid = (left + right) / 2; // 절반 위치
        
        mergeSort(arr, left, mid); // 절반 중 왼쪽 부분리스트(left ~ mid)
        mergeSort(arr, mid+1, right); // 절반 중 오른쪽 부분리스트(mid+1 ~ right)
        
        merge(arr, left, mid, right); // 병합 작업
    }

    /**
     *
     * @param arr : 정렬할 배열
     * @param left : 배열의 시작점
     * @param mid : 배열의 중간점
     * @param right : 배열의 끝점
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int leftStart = left; // 왼쪽 부분리스트 시작점
        int rightStart = mid + 1; // 오른쪽 부분리스트의 시작점
        int index = left; // 채워넣을 배열의 인덱스

        while (leftStart <= mid && rightStart <= right) {
            /*
            왼쪽 부분리스트 leftStart 번째 원소가 오른쪽 부분리스트 rightStart 번째 원소보다 작거나 같을 경우
            왼쪽의 leftStart 번째 원소를 새 배열에 넣고 leftStart 과 index 를 1 증가시킨다.
             */
            if (arr[leftStart] <= arr[rightStart]) {
                sorted[index] = arr[leftStart];
                index++;
                leftStart++;
            }
            /*
            오른쪽 부분리스트 rightStart 원소가 왼쪽 부분리스트 leftStart 번째 원소보다 작거나 같을 경우
            오른쪽의 rightStart 번째 원소를 새 배열에 넣고 rightStart 과 index 를 1 증가시킨다.
             */
            else {
                sorted[index] = arr[rightStart];
                index++;
                rightStart++;
            }
        }

        /*
        왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (leftStart > mid)
		 = 오른쪽 부분리스트 원소가 아직 남아있을 경우
		 오른쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
         */
        if (leftStart > mid) {
            while (rightStart <= right) {
                sorted[index] = arr[rightStart];
                index++;
                rightStart++;
            }
        }

        /*
        오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (rightSide > right)
        = 왼쪽 부분리스트 원소가 아직 남아있을 경우
        왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
         */
        else {
            while (leftStart <= mid) {
                sorted[index] = arr[leftStart];
                index++;
                leftStart++;
            }
        }

        /*
        정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
         */
        for (int i = left; i <= right; i++) {
            arr[i] = sorted[i];
        }

    }
}

 

머지 정렬 소스코드 - BottomUp.java

import java.util.Arrays;

public class MergeSort_BottomUp {

    public static void main(String[] args) {
        int[] array = new int[]{7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

    // 합치는 과정에서 정렬하여 원소를 담을 임시 배열
    private static int[] sorted;

    public static void mergeSort(int[] arr) {
        sorted = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1);
        sorted = null;
    }

    // Bottom-Up 방식 구현
    private static void mergeSort(int[] arr, int left, int right) {
        /*
        1 - 2 - 4 - 8 - ... 식으로 1부터 서브리스트를 나누는 기준을 두 배씩 늘린다.

        두 부분리스트을 순서대로 병합해준다.
        예를들어 현재 부분리스트의 크기가 1(size=1)일 때
        왼쪽 부분리스트(low ~ mid)와 오른쪽 부분리스트(mid + 1 ~ high)를 생각하면
        왼쪽 부분리스트는 low = mid = 0 이고,
        오른쪽 부분리스트는 mid + 1부터 low + (2 * size) - 1 = 1 이 된다.

        이 때 high 가 배열의 인덱스를 넘어갈 수 있으므로 right 와 둘 중 작은 값이
        병합되도록 해야한다.
         */
        for (int size = 1; size <= right ; size += size) {
            for(int i = 0; i <= right - size; i += (2 * size)) {
                int low = i;
                int mid = i + size - 1;
                int high = Math.min(i + (2 * size) - 1, right);
                merge(arr, low, mid, high);		// 병합작업
            }
        }
    }

    /**
     *
     * @param arr : 정렬할 배열
     * @param left : 배열의 시작점
     * @param mid : 배열의 중간점
     * @param right : 배열의 끝점
     */
    private static void merge(int[] arr, int left, int mid, int right) {
        int leftStart = left; // 왼쪽 부분리스트 시작점
        int rightStart = mid + 1; // 오른쪽 부분리스트의 시작점
        int index = left; // 채워넣을 배열의 인덱스

        while (leftStart <= mid && rightStart <= right) {
            /*
            왼쪽 부분리스트 leftStart 번째 원소가 오른쪽 부분리스트 rightStart 번째 원소보다 작거나 같을 경우
            왼쪽의 leftStart 번째 원소를 새 배열에 넣고 leftStart 과 index 를 1 증가시킨다.
             */
            if (arr[leftStart] <= arr[rightStart]) {
                sorted[index] = arr[leftStart];
                index++;
                leftStart++;
            }
            /*
            오른쪽 부분리스트 rightStart 원소가 왼쪽 부분리스트 leftStart 번째 원소보다 작거나 같을 경우
            오른쪽의 rightStart 번째 원소를 새 배열에 넣고 rightStart 과 index 를 1 증가시킨다.
             */
            else {
                sorted[index] = arr[rightStart];
                index++;
                rightStart++;
            }
        }

        /*
        왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (leftStart > mid)
		 = 오른쪽 부분리스트 원소가 아직 남아있을 경우
		 오른쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
         */
        if (leftStart > mid) {
            while (rightStart <= right) {
                sorted[index] = arr[rightStart];
                index++;
                rightStart++;
            }
        }

        /*
        오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (rightSide > right)
        = 왼쪽 부분리스트 원소가 아직 남아있을 경우
        왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
         */
        else {
            while (leftStart <= mid) {
                sorted[index] = arr[leftStart];
                index++;
                leftStart++;
            }
        }

        /*
        정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
         */
        for (int i = left; i <= right; i++) {
            arr[i] = sorted[i];
        }

    }
}

대부분의 경우 정렬 과정은 최대한 재귀는 피하여 구현하는게 일반적이기 때문에 Bottom-Up 으로 구현하는 것이 좋다.

 

계수 정렬 (Counting sort)

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 

계수정렬은 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있다. 

1. 계수 정렬은 먼저 가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담길 수 있는 리스트를 생성한다
2. 위의 예시에서 1부터 9까지 정렬범위이므로 크기가 9인 리스트를 선언하고 리스트의 값들을 0으로 초기화한다
3. 이후 리스트를 순회하면서 해당 원소가 등장하면 1,2 과정에서 생성한 리스트 인덱스의 값을 1 증가시킨다.
4. 이후 1,2 과정에서 생성한 리스트의 인덱스 X 원소 값 을 차례로 출력하면된다.
5. 예시에서 1을 가르키는 인덱스가 값이 2가 저장되어있으므로 1을 두번 출력, 2는 7번 출력... 반복해서 출력하는 방식이다.

 

계수 정렬 소스코드.py

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

 

계수 정렬 소스코드.java

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2, 2};
        int[] countArr = new int[arr.length];

        for (int j : arr) {
            countArr[j] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
        }
        for (int i = 0; i < arr.length; i++) { // 배열에 기록된 정렬 정보 확인
            for (int j = 0; j < countArr[i]; j++) {
                System.out.print(i + " "); // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
            }
        }
    }
}

 

각 알고리즘 별 시간 복잡도와 평균 정렬 속도

출처&nbsp;https://st-lab.tistory.com/233

 

참고한 곳

https://coding-factory.tistory.com/615

https://www.digitalocean.com/community/tutorials/js-bubble-selection-insertion-sort

http://www-scf.usc.edu/~zhan468/public/Notes/sorting.html

https://devbin.kr/2020/algorithm-sort-algorithm-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

https://jbhs7014.tistory.com/180

이것이 취업을 위한 코딩테스트다 with 파이썬 - 나동빈

https://roytravel.tistory.com/328