\uc548\ub155\ud558\uc138\uc694! \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc54c\uace0\ub9ac\uc998 \uc911 \ud558\ub098\uc778 \uc0bd\uc785 \uc815\ub82c(Insertion Sort)<\/strong>\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc0bd\uc785 \uc815\ub82c\uc740 \uac04\ub2e8\ud558\uace0 \uc774\ud574\ud558\uae30 \uc26c\uc6b4 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c, \ud2b9\ud788 \ub370\uc774\ud130\uac00 \uac70\uc758 \uc815\ub82c\ub418\uc5b4 \uc788\ub294 \uacbd\uc6b0 \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4. \ucf54\ud2c0\ub9b0(Kotlin) \ud504\ub85c\uadf8\ub798\ubc0d \uc5b8\uc5b4\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc0bd\uc785 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc0bd\uc785 \uc815\ub82c\uc740 \ub9ac\uc2a4\ud2b8\ub97c \uc815\ub82c\ud560 \ub54c, \ub370\uc774\ud130\ub97c \ud558\ub098\uc529 ‘\uc0bd\uc785’\ud558\uc5ec \uc815\ub82c\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \uac01 \uc694\uc18c\ub97c \uc815\ub82c\ub41c \ub9ac\uc2a4\ud2b8\uc640 \ube44\uad50\ud558\uc5ec \uc801\uc808\ud55c \uc704\uce58\uc5d0 \uc0bd\uc785\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \uce74\ub4dc \uc815\ub82c\uacfc \uc720\uc0ac\ud558\uc5ec, \uac01 \uce74\ub4dc\ub97c \uc815\ub82c\ub41c \uc0c1\ud0dc\ub85c \uc720\uc9c0\ud558\uba70 \uce74\ub4dc\ub97c \ud558\ub098\uc529 \ucd94\uac00\ud574 \ub098\uac00\ub294 \ubaa8\uc2b5\uc744 \ub5a0\uc62c\ub9ac\uc2dc\uba74 \ub429\ub2c8\ub2e4.<\/p>\n \uc0bd\uc785 \uc815\ub82c\uc758 \ud3c9\uade0 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n\u00b2)<\/strong>\uc785\ub2c8\ub2e4. \ucd5c\uc545\uc758 \uacbd\uc6b0\uc5d0\ub3c4 O(n\u00b2)\uc774\uba70, \ucd5c\uc120\uc758 \uacbd\uc6b0\ub294 O(n)\uc785\ub2c8\ub2e4. \uc774\ub294 \ub9ac\uc2a4\ud2b8\uac00 \uac70\uc758 \uc815\ub82c\ub41c \uacbd\uc6b0\uc5d0 \uc0c1\ub300\uc801\uc73c\ub85c \uc131\ub2a5\uc774 \uc6b0\uc218\ud568\uc744 \uc758\ubbf8\ud569\ub2c8\ub2e4.<\/p>\n \uc0bd\uc785 \uc815\ub82c\uc740 \ucd94\uac00\uc801\uc778 \uc800\uc7a5 \uacf5\uac04\uc744 \ud544\uc694\ub85c \ud558\uc9c0 \uc54a\uae30 \ub54c\ubb38\uc5d0, \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(1)\uc785\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \ucf54\ud2c0\ub9b0\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc0bd\uc785 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uba3c\uc800, \uc0bd\uc785 \uc815\ub82c\uc758 \uae30\ubcf8 \uad6c\uc870\ub97c \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \n – \uc6b0\ub9ac\uac00 \uad6c\ud604\ud55c \uc0bd\uc785 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc2e4\uc81c\ub85c \ud14c\uc2a4\ud2b8\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c\uc740 \ud14c\uc2a4\ud2b8 \ucf54\ub4dc\ub97c \ud3ec\ud568\ud55c \uc804\uccb4 \uc608\uc81c\uc785\ub2c8\ub2e4.<\/p>\n \n – \uc0bd\uc785 \uc815\ub82c\uc740 \ub2e4\uc591\ud55c \ubcc0\ud615\uc744 \ud1b5\ud574 \ud6a8\uc728\uc131\uc744 \ub192\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \ub370\uc774\ud130\ub97c \uc0bd\uc785\ud560 \uc704\uce58\ub97c \ucc3e\ub294 \uacfc\uc815\uc5d0\uc11c \uc774\uc9c4 \ud0d0\uc0c9\uc744 \uc0ac\uc6a9\ud55c\ub2e4\uba74, \uc0bd\uc785\ud558\ub294 \uc791\uc5c5\uc744 \ucd5c\uc801\ud654\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n \n – \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc0bd\uc785 \uc815\ub82c\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uace0, \ucf54\ud2c0\ub9b0\uc73c\ub85c \uc9c1\uc811 \uad6c\ud604\ud574 \ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc0bd\uc785 \uc815\ub82c\uc740 \uac04\ub2e8\ud558\uba74\uc11c\ub3c4 \uc720\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc774\uba70, \ud2b9\ud788 \ub370\uc774\ud130\uac00 \uc801\uac70\ub098 \uac70\uc758 \uc815\ub82c\ub41c \uc0c1\ud0dc\uc77c \ub54c \ub9e4\uc6b0 \uc720\uc6a9\ud569\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \ub300\ub7c9\uc758 \ub370\uc774\ud130\ub97c \ub2e4\ub8f0 \ub54c\ub294 \ub354 \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\uc774 \uc88b\uc2b5\ub2c8\ub2e4. \uc774\ub807\uac8c \ub2e4\uc591\ud55c \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc774\ud574\ud558\uace0 \uc801\uc6a9\ud560 \uc218 \uc788\uc5b4\uc57c, \ub354\uc6b1 \ub098\uc740 \ud504\ub85c\uadf8\ub798\ubc0d \uae30\uc220\uc744 \uac16\ucd94\uac8c \ub420 \uac83\uc785\ub2c8\ub2e4.<\/p>\n \n – \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud574\uc124\uc11c \uac10\uc0ac\ud569\ub2c8\ub2e4! \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \ub2e4\ub978 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574 \ud559\uc2b5\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"1. \uc0bd\uc785 \uc815\ub82c\uc774\ub780?<\/h2>\n
1.1 \uc54c\uace0\ub9ac\uc998 \uac1c\uc694<\/h3>\n
\n
2. \uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
2.1 \uacf5\uac04 \ubcf5\uc7a1\ub3c4<\/h3>\n
3. \uc0bd\uc785 \uc815\ub82c \uad6c\ud604\ud558\uae30<\/h2>\n
3.1 \uae30\ubcf8 \uc0bd\uc785 \uc815\ub82c \uad6c\ud604<\/h3>\n
fun insertionSort(arr: IntArray) {\n for (i in 1 until arr.size) {\n val key = arr[i]\n var j = i - 1\n \n \/\/ key\ubcf4\ub2e4 \ud070 \uc694\uc18c\ub97c \uc624\ub978\ucabd\uc73c\ub85c \uc774\ub3d9\n while (j >= 0 && arr[j] > key) {\n arr[j + 1] = arr[j]\n j--\n }\n arr[j + 1] = key\n }\n }<\/code><\/pre>\n3.1.1 \ucf54\ub4dc \uc124\uba85<\/h4>\n
insertionSort<\/code> \ud568\uc218\ub294 \uc815\uc218 \ubc30\uc5f4 arr<\/code>\uc744 \ubc1b\uc544 \uc815\ub82c\ud569\ub2c8\ub2e4.
\n – \uccab \ubc88\uc9f8 \uc694\uc18c\ub294 \uc774\ubbf8 \uc815\ub82c\ub41c \uac83\uc73c\ub85c \uac04\uc8fc\ud558\ubbc0\ub85c, \ub450 \ubc88\uc9f8 \uc694\uc18c\ubd80\ud130 \uc2dc\uc791\ud558\uc5ec \ubc18\ubcf5\ud569\ub2c8\ub2e4. ( for (i in 1 until arr.size)<\/code> \uad6c\ubb38 \uc0ac\uc6a9)
\n – \ud604\uc7ac \ucc98\ub9ac\ud558\uace0 \uc788\ub294 \uc694\uc18c\ub97c key<\/code>\ub85c \uc800\uc7a5\ud558\uace0, \uc774 \uc694\uc18c\ubcf4\ub2e4 \ud070 \uc694\uc18c\ub97c \ucc3e\uc544 \uc624\ub978\ucabd\uc73c\ub85c \uc774\ub3d9\uc2dc\ud0b5\ub2c8\ub2e4.
\n – while<\/code> \ub8e8\ud504\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc62c\ubc14\ub978 \uc704\uce58\ub97c \ucc3e\uc544 key<\/code>\ub97c \uc0bd\uc785\ud569\ub2c8\ub2e4.\n <\/p>\n3.2 \uc0bd\uc785 \uc815\ub82c\uc744 \ud14c\uc2a4\ud2b8\ud574\ubcf4\uc790<\/h3>\n
fun main() {\n val arr = intArrayOf(5, 3, 1, 4, 2)\n println(\"\uc815\ub82c \uc804 \ubc30\uc5f4: ${arr.joinToString(\", \")}\")\n \n insertionSort(arr)\n \n println(\"\uc815\ub82c \ud6c4 \ubc30\uc5f4: ${arr.joinToString(\", \")}\")\n }<\/code><\/pre>\n3.2.1 \ud14c\uc2a4\ud2b8 \ucf54\ub4dc \uc124\uba85<\/h4>\n
main<\/code> \ud568\uc218\uc5d0\uc11c \uc815\ub82c\ud560 \ubc30\uc5f4\uc744 \uc815\uc758\ud558\uace0 \ucd9c\ub825\ud569\ub2c8\ub2e4.
\n – insertionSort<\/code> \ud568\uc218\ub97c \ud638\ucd9c\ud55c \ud6c4, \uc815\ub82c\ub41c \ubc30\uc5f4\uc744 \ub2e4\uc2dc \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/p>\n4. \uc0bd\uc785 \uc815\ub82c\uc758 \uc7a5\ub2e8\uc810<\/h2>\n
4.1 \uc7a5\uc810<\/h3>\n
\n
4.2 \ub2e8\uc810<\/h3>\n
\n
5. \ub2e4\uc591\ud55c \ubcc0\ud615<\/h2>\n
fun insertionSortBinary(arr: IntArray) {\n for (i in 1 until arr.size) {\n val key = arr[i]\n var left = 0\n var right = i - 1\n \n \/\/ \uc774\uc9c4 \ud0d0\uc0c9\uc744 \uc774\uc6a9\ud574 key\uc758 \uc0bd\uc785 \uc704\uce58\ub97c \ucc3e\uc74c\n while (left <= right) {\n val mid = left + (right - left) \/ 2\n if (arr[mid] > key) right = mid - 1\n else left = mid + 1\n }\n \n \/\/ \ucc3e\uc740 \uc704\uce58\uc5d0 key \uc0bd\uc785\n for (j in i downTo left + 1) {\n arr[j] = arr[j - 1]\n }\n arr[left] = key\n }\n }<\/code><\/pre>\n5.1 \uc774\uc9c4 \uc0bd\uc785 \uc815\ub82c \uc124\uba85<\/h4>\n
insertionSortBinary<\/code> \ud568\uc218\ub294 \uae30\uc874 \uc0bd\uc785 \uc815\ub82c\uacfc \ube44\uc2b7\ud558\uc9c0\ub9cc, \uc694\uc18c\ub97c \uc0bd\uc785\ud560 \uc704\uce58\ub97c \ucc3e\ub294 \uacfc\uc815\uc5d0\uc11c \uc774\uc9c4 \ud0d0\uc0c9\uc744 \uc0ac\uc6a9\ud569\ub2c8\ub2e4.
\n – \uc774\uc9c4 \ud0d0\uc0c9\uc744 \ud1b5\ud574 \uc801\uc808\ud55c \uc0bd\uc785 \uc704\uce58\ub97c \ucc3e\uc544 \ud6a8\uc728\uc131\uc744 \ub192\uc774\ub294 \ud6a8\uacfc\uac00 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n6. \uc815\ub9ac<\/h2>\n
7. \ucc38\uace0 \uc790\ub8cc<\/h2>\n
\n – \ucf54\ud2c0\ub9b0 \uacf5\uc2dd \ubb38\uc11c
\n – \ub2e4\uc591\ud55c \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc758 \ube44\uad50 \ubd84\uc11d\n <\/p>\n