{"id":26928,"date":"2024-10-27T11:53:42","date_gmt":"2024-10-27T11:53:42","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=26928"},"modified":"2024-11-26T07:26:00","modified_gmt":"2024-11-26T07:26:00","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-%ec%b9%b4%eb%93%9c-%ec%a0%95%eb%a0%ac%ed%95%98%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/26928\/","title":{"rendered":"\uc790\ubc14 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uce74\ub4dc \uc815\ub82c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

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

\n \ub2f9\uc2e0\uc740 \uce74\ub4dc \uc815\ub9ac \uc804\ubb38\uac00\uc785\ub2c8\ub2e4. \uac01 \uce74\ub4dc\uc5d0\ub294 1\ubd80\ud130 N\uae4c\uc9c0\uc758 \uc22b\uc790\uac00 \uc801\ud600\uc788\uc2b5\ub2c8\ub2e4.
\n \uadf8\ub7ec\ub098 \uce74\ub4dc\ub4e4\uc740 \uc11e\uc778 \uc0c1\ud0dc\uc785\ub2c8\ub2e4. \ub2f9\uc2e0\uc758 \ubaa9\ud45c\ub294 \uc8fc\uc5b4\uc9c4 \uce74\ub4dc\ub4e4\uc744 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.
\n \ub2f9\uc2e0\uc740 \uac01 \uce74\ub4dc\ub97c \ud55c \ubc88\uc5d0 \ud55c \uc7a5\uc529 \uc120\ud0dd\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc120\ud0dd\ud55c \uce74\ub4dc\uc758 \uc22b\uc790\ub97c \uae30\uc900\uc73c\ub85c
\n \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud574\uc57c \ud569\ub2c8\ub2e4. \ucd5c\uc18c\ud55c\uc758 \ube44\uad50 \ud69f\uc218\ub85c \uce74\ub4dc\ub97c \uc815\ub82c\ud574\uc57c \ud569\ub2c8\ub2e4.<\/strong>\n<\/p>\n

\uc785\ub825<\/h3>\n

\n \uccab\uc9f8 \uc904\uc5d0 \uce74\ub4dc\uc758 \uac1c\uc218 N(1 \u2264 N \u2264 10^6)\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.
\n \ub458\uc9f8 \uc904\uc5d0 N\uac1c\uc758 \uc815\uc218 A1, A2, …, AN(1 \u2264 Ai \u2264 10^9)\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.
\n \uc774 \ubc30\uc5f4\uc740 \uce74\ub4dc\uc758 \uc22b\uc790\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4.\n <\/p>\n

\ucd9c\ub825<\/h3>\n

\n \uc120\ucd9c\ub825\uc5d0 \uac01 \uce74\ub4dc\uc758 \uc22b\uc790\ub97c \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\uc5ec \ud55c \uc904\uc5d0 \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n

\ubb38\uc81c \ud574\uacb0 \uc804\ub7b5<\/h2>\n

\n \uce74\ub4dc \uc815\ub82c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \uc5ec\ub7ec \uac00\uc9c0 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \ud2b9\ud788, \ud035 \uc815\ub82c<\/strong>\uc774\ub098 \ubcd1\ud569 \uc815\ub82c<\/strong>\uacfc \uac19\uc740 \ud6a8\uc728\uc801\uc778 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud558\uba74 \uc88b\uc2b5\ub2c8\ub2e4.
\n \uc774 \ub17c\uc758\uc5d0\uc11c\ub294 \ubcd1\ud569 \uc815\ub82c<\/strong>\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n

\ubcd1\ud569 \uc815\ub82c(Merge Sort)<\/h3>\n

\n \ubcd1\ud569 \uc815\ub82c\uc740 \ub098\ub204\uc5b4 \uc815\ubcf5(Divide and Conquer) \uc54c\uace0\ub9ac\uc998\uc758 \uc77c\uc885\uc73c\ub85c,
\n \ub2e4\uc74c\uacfc \uac19\uc740 \ub2e8\uacc4\ub97c \uac70\uccd0 \uc815\ub82c\ud569\ub2c8\ub2e4:\n <\/p>\n

    \n
  1. \ubc30\uc5f4\uc744 \ubc18\uc73c\ub85c \ub098\ub215\ub2c8\ub2e4.<\/li>\n
  2. \uac01 \ubc18\uc744 \uc7ac\uadc0\uc801\uc73c\ub85c \uc815\ub82c\ud569\ub2c8\ub2e4.<\/li>\n
  3. \uc815\ub82c\ub41c \ub450 \ubc30\uc5f4\uc744 \ubcd1\ud569\ud558\uc5ec \ucd5c\uc885\uc801\uc73c\ub85c \uc815\ub82c\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n

    \uc790\ubc14 \ucf54\ub4dc<\/h3>\n
    \n        \npublic class CardSorting {\n    public static void main(String[] args) {\n        int[] cards = {3, 2, 5, 4, 1}; \/\/ \uc608\uc81c \uc785\ub825\n        mergeSort(cards, 0, cards.length - 1);\n        System.out.println(\"\uc815\ub82c\ub41c \uce74\ub4dc:\");\n        for (int card : cards) {\n            System.out.print(card + \" \");\n        }\n    }\n\n    public static void mergeSort(int[] array, int left, int right) {\n        if (left < right) {\n            int mid = (left + right) \/ 2;\n\n            mergeSort(array, left, mid);\n            mergeSort(array, mid + 1, right);\n\n            merge(array, left, mid, right);\n        }\n    }\n\n    public static void merge(int[] array, int left, int mid, int right) {\n        int n1 = mid - left + 1;\n        int n2 = right - mid;\n\n        int[] L = new int[n1];\n        int[] R = new int[n2];\n\n        for (int i = 0; i < n1; i++) {\n            L[i] = array[left + i];\n        }\n        for (int j = 0; j < n2; j++) {\n            R[j] = array[mid + 1 + j];\n        }\n\n        int i = 0, j = 0;\n        int k = left;\n        while (i < n1 && j < n2) {\n            if (L[i] <= R[j]) {\n                array[k] = L[i];\n                i++;\n            } else {\n                array[k] = R[j];\n                j++;\n            }\n            k++;\n        }\n\n        while (i < n1) {\n            array[k] = L[i];\n            i++;\n            k++;\n        }\n\n        while (j < n2) {\n            array[k] = R[j];\n            j++;\n            k++;\n        }\n    }\n}\n        <\/code>\n    <\/pre>\n
    \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
    \n        \ubcd1\ud569 \uc815\ub82c\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294
    \n        O(N log N)<\/strong>\uc785\ub2c8\ub2e4. \uc774\ub294 \uc815\ub82c\ub41c \ub450 \uac1c\uc758 \ubc30\uc5f4\uc744 \ud569\uce58\ub294 \uac83\uc774 O(N)\uc774\uace0, \ubc30\uc5f4\uc744 \uacc4\uc18d \ubc18\uc73c\ub85c \ub098\ub204\ub294 \uac83\uc774 log N\uc5d0 \ud574\ub2f9\ud558\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4.
    \n        \ub530\ub77c\uc11c \ub300\uaddc\ubaa8 \uce74\ub4dc \ub370\uc774\ud130\uc5d0 \ub300\ud574\uc11c\ub3c4 \ud6a8\uc728\uc801\uc73c\ub85c \uc815\ub82c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n    <\/p>\n
    \ub9c8\ubb34\ub9ac<\/h2>\n
    \n        \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \uce74\ub4dc \uc815\ub82c \ubb38\uc81c\ub97c \ubcd1\ud569 \uc815\ub82c\uc744 \ud1b5\ud574 \ud574\uacb0\ud574\ubcf4\uc558\uc2b5\ub2c8\ub2e4.
    \n        \uc790\ubc14\ub97c \uc0ac\uc6a9\ud55c \ubcd1\ud569 \uc815\ub82c\uc758 \uad6c\ud604\uc744 \ud1b5\ud574 \ub2e4\uc591\ud55c \ub370\uc774\ud130 \uad6c\uc870\uc640 \uc54c\uace0\ub9ac\uc998\uc758 \uc911\uc694\uc131\uc744 \uc774\ud574\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
    \n        \uc55e\uc73c\ub85c\ub3c4 \uc774\ub7ec\ud55c \ubb38\uc81c\ub4e4\uc744 \uc9c0\uc18d\uc801\uc73c\ub85c \ub2e4\ub8e8\uc5b4 \uc790\ubc14 \ud504\ub85c\uadf8\ub798\ubc0d \uc2e4\ub825\uc744 \uac00\ub2e4\ub4ec\uc5b4\ubcf4\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.\n    <\/p>\n
    \ub354 \uc77d\uc5b4\ubcfc \uc790\ub8cc<\/h2>\n