{"id":26786,"date":"2024-10-27T11:52:42","date_gmt":"2024-10-27T11:52:42","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=26786"},"modified":"2024-11-26T07:30:13","modified_gmt":"2024-11-26T07:30:13","slug":"%ec%9e%90%eb%b0%94-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%eb%b3%91%ed%95%a9-%ec%a0%95%eb%a0%ac","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/26786\/","title":{"rendered":"\uc790\ubc14 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ubcd1\ud569 \uc815\ub82c"},"content":{"rendered":"

<\/p>\n

\uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud480\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc591\ud55c \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc774\ud574\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \uc774 \uae00\uc5d0\uc11c\ub294 \ubcd1\ud569 \uc815\ub82c\uc758 \uac1c\ub150\uacfc \uc790\ubc14 \ucf54\ub4dc \uad6c\ud604\uc744 \ud1b5\ud574 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\ub2e4\uc74c\uacfc \uac19\uc740 \uc815\uc218 \ubc30\uc5f4\uc774 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \ubcd1\ud569 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc774\uc6a9\ud558\uc5ec \ubc30\uc5f4\uc744 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\uc2dc\uc624.<\/p>\n

\uc785\ub825: [38, 27, 43, 3, 9, 82, 10]\n\ucd9c\ub825: [3, 9, 10, 27, 38, 43, 82]<\/code><\/pre>\n
\ubcd1\ud569 \uc815\ub82c\uc774\ub780?<\/h2>\n
\ubcd1\ud569 \uc815\ub82c(Merge Sort)\uc740 \ubd84\ud560 \uc815\ubcf5(Divide and Conquer) \uc54c\uace0\ub9ac\uc998\uc758 \uc77c\uc885\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ub300\uccb4\ub85c \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4:<\/p>\n
    \n
  1. \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\uc744 \ubc18\uc73c\ub85c \ub098\ub215\ub2c8\ub2e4.<\/li>\n
  2. \uac01 \ubd80\ubd84 \ubc30\uc5f4\uc744 \uc7ac\uadc0\uc801\uc73c\ub85c \uc815\ub82c\ud569\ub2c8\ub2e4.<\/li>\n
  3. \uc815\ub82c\ub41c \ub450 \ubd80\ubd84 \ubc30\uc5f4\uc744 \ubcd1\ud569\ud558\uc5ec \ud558\ub098\uc758 \uc815\ub82c\ub41c \ubc30\uc5f4\ub85c \ub9cc\ub4ed\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    \ubcd1\ud569 \uc815\ub82c\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n log n)\uc774\uba70, \uc548\uc815\uc801\uc778 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c \ubd84\ub958\ub429\ub2c8\ub2e4.<\/p>\n
    \ubcd1\ud569 \uc815\ub82c\uc758 \uad6c\ud604 \uacfc\uc815<\/h2>\n
    1. \ubc30\uc5f4 \ubd84\ud560<\/h3>\n
    \ubc30\uc5f4\uc744 \uacc4\uc18d\ud574\uc11c \ubc18\uc73c\ub85c \ub098\ub204\uc5b4 \uc791\uc740 \ubc30\uc5f4\ub85c \ub098\uac11\ub2c8\ub2e4. \uc774 \ub2e8\uacc4\ub294 \ubc30\uc5f4\uc758 \ud06c\uae30\uac00 1\uc774 \ub420 \ub54c\uae4c\uc9c0 \uacc4\uc18d\ub429\ub2c8\ub2e4.<\/p>\n
    2. \ubcd1\ud569 \ubc0f \uc815\ub82c<\/h3>\n
    \uac01\uac01\uc758 \ubd84\ud560\ub41c \ubc30\uc5f4\ub4e4\uc774 \uc815\ub82c\ub418\uba74, \uc774\ub4e4\uc744 \ub2e4\uc2dc \ud569\uce58\ub294 \uacfc\uc815\uc774 \ud544\uc694\ud569\ub2c8\ub2e4. \uc774 \ub54c \ub450 \ubc30\uc5f4\uc744 \ube44\uad50\ud558\uc5ec \uc815\ub82c\ub41c \uc0c1\ud0dc\ub85c \ubcd1\ud569\ud569\ub2c8\ub2e4.<\/p>\n
    3. \uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h3>\n
    \uc774\uc81c \ubcd1\ud569 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc790\ubc14\ub85c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n
    public class MergeSort {\n    public static void main(String[] args) {\n        int[] arr = {38, 27, 43, 3, 9, 82, 10};\n        System.out.println(\"\uc815\ub82c \uc804: \" + java.util.Arrays.toString(arr));\n        mergeSort(arr, 0, arr.length - 1);\n        System.out.println(\"\uc815\ub82c \ud6c4: \" + java.util.Arrays.toString(arr));\n    }\n\n    public static void mergeSort(int[] arr, int left, int right) {\n        if (left < right) {\n            int mid = (left + right) \/ 2;\n\n            \/\/ \uc67c\ucabd \ubc18 \uc815\ub82c\n            mergeSort(arr, left, mid);\n            \/\/ \uc624\ub978\ucabd \ubc18 \uc815\ub82c\n            mergeSort(arr, mid + 1, right);\n            \/\/ \ubcd1\ud569\n            merge(arr, left, mid, right);\n        }\n    }\n\n    public static void merge(int[] arr, int left, int mid, int right) {\n        \/\/ \uc67c\ucabd\uacfc \uc624\ub978\ucabd \ubd80\ubd84\uc758 \ud06c\uae30 \uacc4\uc0b0\n        int n1 = mid - left + 1;\n        int n2 = right - mid;\n\n        \/\/ \uc784\uc2dc \ubc30\uc5f4 \uc0dd\uc131\n        int[] L = new int[n1];\n        int[] R = new int[n2];\n\n        \/\/ \uc784\uc2dc \ubc30\uc5f4\uc5d0 \ub370\uc774\ud130 \ubcf5\uc0ac\n        System.arraycopy(arr, left, L, 0, n1);\n        System.arraycopy(arr, mid + 1, R, 0, n2);\n\n        \/\/ \ubcd1\ud569\ud558\ub294 \uacfc\uc815\n        int i = 0, j = 0, k = left; \/\/ i\ub294 \uc67c\ucabd \ubc30\uc5f4 \uc778\ub371\uc2a4, j\ub294 \uc624\ub978\ucabd \ubc30\uc5f4 \uc778\ub371\uc2a4\n        while (i < n1 && j < n2) {\n            if (L[i] <= R[j]) {\n                arr[k++] = L[i++];\n            } else {\n                arr[k++] = R[j++];\n            }\n        }\n\n        \/\/ \ub0a8\uc544 \uc788\ub294 \uc694\uc18c \ubcf5\uc0ac\n        while (i < n1) {\n            arr[k++] = L[i++];\n        }\n\n        while (j < n2) {\n            arr[k++] = R[j++];\n        }\n    }\n}<\/code><\/pre>\n
    \ucf54\ub4dc \uc124\uba85<\/h2>\n
    \uc704 \ucf54\ub4dc\ub294 \ubcd1\ud569 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c \uac83\uc785\ub2c8\ub2e4. \uac01 \ubd80\ubd84\uc744 \uc0b4\ud3b4\ubcf4\uba74:<\/p>\n