{"id":71,"date":"2015-11-12T03:56:57","date_gmt":"2015-11-12T03:56:57","guid":{"rendered":"http:\/\/sungjin.noip.me\/?p=71"},"modified":"2015-11-12T03:56:57","modified_gmt":"2015-11-12T03:56:57","slug":"edxintroduction-to-computer-science-and-programming-using-python-week52","status":"publish","type":"post","link":"http:\/\/mukgee.com\/?p=71","title":{"rendered":"[EDX]Introduction to Computer Science and Programming Using Python-Week5(2)"},"content":{"rendered":"

week5 – lecture 10<\/p>\n

Search \uc54c\uace0\ub9ac\uc998\uc5d0 \uad00\ud55c \uac15\uc758\uc774\ub2e4<\/p>\n

\uba3c\uc800 Simple\ud55c \ubc29\ubc95\uc774 \uc18c\uac1c\ub418\ub294\ub370 search\ub97c \uc704\ud574\uc11c \uc8fc\uc5b4\uc9c4 L(L\uc740 list\ub77c\uace0 \uac00\uc815\ud55c\ub2e4)\uc758 \uae38\uc774\ub9cc\ud07c for\ubb38\uc744 \ub3cc\uba74\uc11c \uc77c\uce58\ud558\ub294 \uac83\uc774 \uc874\uc7ac\ud558\ub294\uc9c0 \ucc3e\ub294 \ubc29\ubc95\uc774\ub2e4. \uc2ec\ud50c \uac80\uc0c9\uc758 \ubcf5\uc7a1\ub3c4\ub294 O(len(L))<\/span> \uc774\ub41c\ub2e4. \u00a0\uc120\ud615 \uc758 \ubcf5\uc7a1\ub3c4\ub294 \uc5c4\uccad \ub098\uc058\uc9c0\ub294 \uc54a\uc9c0\ub9cc \ub354 \ub098\uc740 \ubc29\ubc95\uc744 \uace0\ub824\ud574\ubcf8\ub2e4.<\/p>\n

“I need to know, can I do better?”<\/strong><\/p>\n

*\uc774\ud558\u00a0len(L)\uc740 N\uc73c\ub85c \ud45c\ud604\ud55c\ub2e4<\/h5>\n

\uc774\ubd84\uac80\uc0c9(Binary Search)\ub97c \uc774\uc6a9\ud55c\ub2e4\uba74 \uac80\uc0c9 \uc54c\uace0\ub9ac\uc998\uc740 O(log(N))\ub85c \ud5a5\uc0c1<\/span> \ub420 \uc218 \uc788\ub2e4. \u00a0\ud558\uc9c0\ub9cc Binary Search\uc758 \uacbd\uc6b0\ub294 \uc815\ub82c(sorting)\uc774 \ub418\uc5b4\uc57c \uac00\ub2a5<\/span>\ud558\ub2e4\ub294 \ubb38\uc81c\uac00 \uc787\ub2e4. \uadf8\ub807\ub2e4\uba74? sorting \uc744 \uc704\ud55c cost\ub294 \uc5b4\ub5a4\uac00? \uadf8\ub798\uc11c sorting \uc54c\uace0\ub9ac\uc998\uc744 \uc54c\uc544\ubcf8\ub2e4.<\/p>\n

sorting \uc54c\uace0\ub9ac\uc998\uc5d0\ub294 \ub2e4\uc591\ud55c \ubc29\ubc95\uc774 \uc788\uc9c0\ub9cc(\uc544\ub9c8 \uc815\ubcf4\ucc98\ub9ac\uae30\uc0ac \uacf5\ubd80\ud558\uba74\uc11c \ubd24\ub358 \uae30\uc5b5\uc774….) \uc774\ubc88 \uac15\uc758\uc5d0\uc11c\ub294 \uc120\ud0dd\uc815\ub82c(selection sort)\uc640 \ud569\ubcd1\uc815\ub82c(merge sort)\uac00 \ub4f1\uc7a5\ud55c\ub2e4.<\/p>\n

\uba3c\uc804 \uc120\ud0dd\uc815\ub82c<\/strong><\/span>\uc774\ub2e4. \uc774\uc81c Big O \ud45c\uae30\ubc95\uc744 \ubc30\uc6b4\uc774\uc0c1 \uc874\uc7ac\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud574\uc11c\ub294 \ubcf5\uc7a1\ub3c4\ub97c \uacc4\uc0b0\ud574\uc11c Big O \ud45c\uae30\ubc95\uc73c\ub85c \ud45c\uc2dc\ud55c\ub2e4. \uadf8\ub798\uc11c \uc5b4\ub5a4 \uc54c\uace0\ub9ac\uc998\uc774 \ud6a8\uc728\uc801\uc778\uc9c0 \ube44\uad50\ud558\ub294\ub370 \uc120\ud0dd\uc815\ub82c\uc740 \ubcf5\uc7a1\ub3c4\uac00 O(N^2)<\/strong> \uc774\ub2e4. \uc774\ub7f0…<\/p>\n

\uadf8\ub7fc sorting \ud558\uace0 \uac80\uc0c9\ud558\uba74 O(N^2) + O(log(N))<\/strong> … \uadf8\ub0e5 \uc2ec\ud50c\ud55c \ubc29\ubc95\uc73c\ub85c O(N)\uc774 \ub0ab\ub2e4<\/strong>. <\/span><\/p>\n

\uadf8\ub7fc \uc5ec\uae30\uc11c \ub05d\uc778\uac00?<\/p>\n

\uac1c\ubc1c \uacbd\ub825 2\ub144\ubc16\uc5d0 \uc548\ub418\uc9c0\ub9cc \uc88b\uc740 \uac1c\ubc1c\uc790\uac00 \ub418\uae30 \uc704\ud574\uc11c\ub294 \ud56d\uc0c1 \ubb3c\uc5b4\ubd10\uc57c\ud55c\ub2e4\uace0 \uc0dd\uac01\ud55c\ub2e4.<\/p>\n

“I need to know, can I do better?”<\/strong><\/p>\n

\ud569\ubcd1\uc815\ub82c<\/strong><\/span>(merge sort)\uc758 \ubcf5\uc7a1\ub3c4\ub294 \uc5bc\ub9c8\uc778\uac00? \ud569\ubcd1\uc815\ub82c\uc740 L\uc744 \ucabc\uac1c\uc11c \uac01\uac01 sorting\ud55c\ub2e4\uc74c\uc5d0 \ud569\uce58\ub294 \ubc29\ubc95\uc778\ub370 \uacb0\ub860\ub9cc \uc774\uc57c\uae30\ud558\uba74 O(N*log(N))<\/strong>\uc774\ub2e4.<\/p>\n

\uadf8\ub807\ub2e4\uba74???<\/p>\n

\ud569\ubcd1\uc815\ub82c\ub85c sorting \ud558\uace0 \uac80\uc0c9\ud558\uba74? \u00a0\u00a0O(n*log(n)) + O(k*log(n))<\/strong><\/span> \u00a0– k\ub294 \uac80\uc0c9 \ud69f\uc218<\/p>\n

\uadf8\ub807\ub2e4. \uc2ec\ud50c \uac80\uc0c9 O(N)\ubcf4\ub2e4 \ud569\ubcd1\uc815\ub82c\uc774\ud6c4 \uc774\ubd84\uac80\uc0c9\uc774 \ub354 \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc774\ub2e4.<\/p>\n

\ud2b9\ud788 \uac80\uc0c9\uc744 \uc5ec\ub7ec\ubc88 \uc2e4\ud589\ud574\uc57c \ud560 \uacbd\uc6b0 sorting \uc744 \uc704\ud55c cost\ub294\u00a0amortize cost(\uc0c1\ud658\ube44\uc6a9)\uc774\ub2e4.\u00a0<\/strong><\/p>\n

\uadf8\ub7fc \uc704\uc758 \ubc29\ubc95\ubcf4\ub2e4 \ub354 \ub098\uc740 \ubc29\ubc95\uc740 \uc5c6\ub294\uac00?<\/p>\n

Hash<\/strong><\/span> \uac00 \ub098\uc628\ub2e4.<\/p>\n

Hash \ub780 key \ub97c \uac00\uc9c0\ub294 \ub370\uc774\ud130 \uad6c\uc870\uc778\ub370 key\ub97c int\ub85c \ubcc0\ud658\ud574\uc11c index\ub85c \uc0ac\uc6a9\ud55c\ub2e4. \ub530\ub77c\uc11c Hash \ub85c \uc800\uc7a5\ub41c \ub370\uc774\ud130\uc758 \uacbd\uc6b0 \uac80\uc0c9 \ubcf5\uc7a1\ub3c4\ub294 O(1)\uc774\ub2e4.<\/p>\n

\uc774\ub7f0<\/p>\n

\uc55e\uc120 \ubc29\ubc95 \ubcf4\ub2e4 \ube44\uad50\ud560 \uc218 \uc5c6\uc744 \ub9cc\ud07c \ud6a8\uc728\uc801\uc774\ub2e4.<\/p>\n

\uc5b4\ub5a4 \uac80\uc0c9 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud574\uc57c\ud560 \uc9c0\ub294 \uc54c\uc544\uc11c \ud310\ub2e8\ud558\uc790.<\/p>\n

“I need to know, can I do better?”<\/strong><\/span><\/p>\n

 
\n<\/p>\n

\uc9c4\ud589\uc911\uc778 \ud504\ub85c\uc81d\ud2b8\uc5d0\uc11c DB\uc5d0\uc11c where \uc808\ub85c \uac80\uc0c9 \ucffc\ub9ac\ub97c \uc644\uc131\ud558\ub294 \uac83\uc774 \uc544\ub2cc \ub370\uc774\ud130\ub97c \uc804\ubd80 \ubd88\ub7ec\uc628 \ub4a4 javascript \uc5d0\uc11c indexOf\ub85c \uac80\uc0c9\ud558\ub294 \ucf54\ub4dc\ub97c \ub9cc\ub4e4\uc5b4\ub450\uc5c8\ub2e4.<\/p>\n

\uc774 \uac15\uc758\ub97c \ubc14\ud0d5\uc73c\ub85c \ube44\ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc744 \uac1c\uc120\ud574\uc57c\uaca0\ub2e4.<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

week5 – lecture 10 Search \uc54c\uace0\ub9ac\uc998\uc5d0 \uad00\ud55c \uac15\uc758\uc774\ub2e4 \uba3c\uc800 Simple\ud55c \ubc29\ubc95\uc774 \uc18c\uac1c\ub418\ub294\ub370 search\ub97c \uc704\ud574\uc11c \uc8fc\uc5b4\uc9c4 L(L\uc740 list\ub77c\uace0 \uac00\uc815\ud55c\ub2e4)\uc758 \uae38\uc774\ub9cc\ud07c for\ubb38\uc744 \ub3cc\uba74\uc11c \uc77c\uce58\ud558\ub294 \uac83\uc774 \uc874\uc7ac\ud558\ub294\uc9c0 \ucc3e\ub294…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":""},"categories":[3],"tags":[11,29,53],"aioseo_notices":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/71"}],"collection":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=71"}],"version-history":[{"count":0,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/71\/revisions"}],"wp:attachment":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=71"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=71"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=71"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}