{"id":4501,"date":"2024-08-28T22:15:28","date_gmt":"2024-08-28T13:15:28","guid":{"rendered":"https:\/\/itjaeneungnanum.org\/?p=4501"},"modified":"2024-08-28T22:15:29","modified_gmt":"2024-08-28T13:15:29","slug":"006-%ed%9e%99%ed%81%90heapq%eb%a5%bc-%ec%9d%b4%ec%9a%a9%ed%95%9c-%eb%ac%b8%ec%a0%9c-%ed%92%80%ec%9d%b4%ec%99%80-%ed%8c%8c%ec%9d%b4%ec%8d%ac%ec%97%90%ec%84%9c%ec%9d%98-%ed%8f%ac%ec%9d%b8%ed%84%b0","status":"publish","type":"post","link":"https:\/\/itjaeneungnanum.org\/?p=4501","title":{"rendered":"006. \ud799\ud050(heapq)\ub97c \uc774\uc6a9\ud55c \ubb38\uc81c \ud480\uc774\uc640 \ud30c\uc774\uc36c\uc5d0\uc11c\uc758 \ud3ec\uc778\ud130 \uac1c\ub150 \uc124\uba85"},"content":{"rendered":"\n<blockquote class=\"wp-block-quote\"><p>Leetcode 703. Kth Largest Element in a Stream (Easy) <\/p><\/blockquote>\n\n\n\n<p>heapq\ub294 Python\uc758 \ud45c\uc900 \ub77c\uc774\ube0c\ub7ec\ub9ac\uc5d0 \ud3ec\ud568\ub41c \ud799 \ud050(heap queue) \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c \ubaa8\ub4c8\uc785\ub2c8\ub2e4. \ud799\uc740 \ud2b9\ubcc4\ud55c \ud615\ud0dc\uc758 \uc774\uc9c4 \ud2b8\ub9ac\ub85c, \ub2e4\uc74c\uacfc \uac19\uc740 \ud2b9\uc9d5\uc744 \uac00\uc9d1\ub2c8\ub2e4:<\/p>\n\n\n\n<ol><li>\ucd5c\uc18c \ud799(min heap): \ubd80\ubaa8 \ub178\ub4dc\uc758 \uac12\uc774 \ud56d\uc0c1 \uc790\uc2dd \ub178\ub4dc\uc758 \uac12\ubcf4\ub2e4 \uc791\uac70\ub098 \uac19\uc2b5\ub2c8\ub2e4.<\/li><li>\uc644\uc804 \uc774\uc9c4 \ud2b8\ub9ac: \ub9c8\uc9c0\ub9c9 \ub808\ubca8\uc744 \uc81c\uc678\ud55c \ubaa8\ub4e0 \ub808\ubca8\uc774 \uc644\uc804\ud788 \ucc44\uc6cc\uc838 \uc788\uace0, \ub9c8\uc9c0\ub9c9 \ub808\ubca8\uc740 \uc67c\ucabd\ubd80\ud130 \ucc44\uc6cc\uc9d1\ub2c8\ub2e4.<\/li><\/ol>\n\n\n\n<p>heapq \ubaa8\ub4c8\uc758 \uc8fc\uc694 \ud2b9\uc9d5\uacfc \uc0ac\uc6a9\ubc95\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n\n\n\n<ol><li>\ub9ac\uc2a4\ud2b8\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud799\uc744 \uad6c\ud604\ud569\ub2c8\ub2e4.<\/li><li>\uac00\uc7a5 \uc791\uc740 \uc694\uc18c\uac00 \ud56d\uc0c1 heap[0]\uc5d0 \uc704\uce58\ud569\ub2c8\ub2e4.<\/li><li>\uc8fc\uc694 \ud568\uc218\ub4e4:<\/li><\/ol>\n\n\n\n<ul><li>heapq.heappush(heap, item): \ud799\uc5d0 \uc0c8\ub85c\uc6b4 \uc694\uc18c\ub97c \ucd94\uac00<\/li><li>heapq.heappop(heap): \uac00\uc7a5 \uc791\uc740 \uc694\uc18c\ub97c \uc81c\uac70\ud558\uace0 \ubc18\ud658<\/li><li>heapq.heapify(list): \uc77c\ubc18 \ub9ac\uc2a4\ud2b8\ub97c \ud799\uc73c\ub85c \ubcc0\ud658<\/li><\/ul>\n\n\n\n<p>heapq\ub294 \uc8fc\ub85c \ub2e4\uc74c\uacfc \uac19\uc740 \uc0c1\ud669\uc5d0\uc11c \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub429\ub2c8\ub2e4:<\/p>\n\n\n\n<ol><li>\uc6b0\uc120\uc21c\uc704 \ud050 \uad6c\ud604<\/li><li>\uc815\ub82c\ub41c \uc0c1\ud0dc\ub85c \uc694\uc18c\ub97c \uc720\uc9c0\ud574\uc57c \ud560 \ub54c<\/li><li>k\ubc88\uc9f8\ub85c \ud070\/\uc791\uc740 \uc694\uc18c\ub97c \ucc3e\uc744 \ub54c<\/li><\/ol>\n\n\n\n<p>\ub2e4\uc74c\uc740 \uac04\ub2e8\ud55c \uc0ac\uc6a9 \uc608\uc785\ub2c8\ub2e4.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import heapq\n\n# \ube48 \ud799 \uc0dd\uc131\nheap = &#91;]\n\n# \uc694\uc18c \ucd94\uac00\nheapq.heappush(heap, 4)\nheapq.heappush(heap, 1)\nheapq.heappush(heap, 7)\nheapq.heappush(heap, 3)\n\nprint(\"\ud799 \uc0c1\ud0dc:\", heap)\n\n# \ucd5c\uc18c\uac12 \ucd94\ucd9c\nsmallest = heapq.heappop(heap)\nprint(\"\ucd94\ucd9c\ub41c \ucd5c\uc18c\uac12:\", smallest)\nprint(\"\ud799 \uc0c1\ud0dc:\", heap)\n\n# \uae30\uc874 \ub9ac\uc2a4\ud2b8\ub97c \ud799\uc73c\ub85c \ubcc0\ud658\nnumbers = &#91;5, 8, 2, 9, 1, 3]\nheapq.heapify(numbers)\nprint(\"heapify \ud6c4 \uc0c1\ud0dc:\", numbers)\n\n# \ud799\uc5d0\uc11c \ubaa8\ub4e0 \uc694\uc18c\ub97c \uc815\ub82c\ub41c \uc21c\uc11c\ub85c \ucd94\ucd9c\nsorted_numbers = &#91;]\nwhile numbers:\n    sorted_numbers.append(heapq.heappop(numbers))\n\nprint(\"\uc815\ub82c\ub41c \uc22b\uc790:\", sorted_numbers)<\/code><\/pre>\n\n\n\n<p>\uc774 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc740 \uacb0\uacfc\uac00 \ucd9c\ub825\ub429\ub2c8\ub2e4:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\ud799 \uc0c1\ud0dc: &#91;1, 3, 7, 4]\n\ucd94\ucd9c\ub41c \ucd5c\uc18c\uac12: 1\n\ud799 \uc0c1\ud0dc: &#91;3, 4, 7]\nheapify \ud6c4 \uc0c1\ud0dc: &#91;1, 3, 2, 9, 8, 5]\n\uc815\ub82c\ub41c \uc22b\uc790: &#91;1, 2, 3, 5, 8, 9]<\/code><\/pre>\n\n\n\n<p>\uc774 \uc608\uc81c\uc5d0\uc11c \ubcfc \uc218 \uc788\ub4ef\uc774:<\/p>\n\n\n\n<ol><li><code>heappush<\/code>\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud799\uc5d0 \uc694\uc18c\ub97c \ucd94\uac00\ud569\ub2c8\ub2e4.<\/li><li><code>heappop<\/code>\uc744 \uc0ac\uc6a9\ud558\uc5ec \uac00\uc7a5 \uc791\uc740 \uc694\uc18c\ub97c \uc81c\uac70\ud558\uace0 \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li><li><code>heapify<\/code>\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc77c\ubc18 \ub9ac\uc2a4\ud2b8\ub97c \ud799\uc73c\ub85c \ubcc0\ud658\ud569\ub2c8\ub2e4.<\/li><li>\ud799\uc5d0\uc11c \uc694\uc18c\ub97c \uacc4\uc18d \ucd94\ucd9c\ud558\uba74 \uc815\ub82c\ub41c \uc21c\uc11c\ub85c \uc5bb\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/li><\/ol>\n\n\n\n<p>heapq\ub294 \ucd5c\uc18c \ud799\uc744 \uae30\ubcf8\uc73c\ub85c \uad6c\ud604\ud558\uc9c0\ub9cc, \ucd5c\ub300 \ud799\uc774 \ud544\uc694\ud55c \uacbd\uc6b0 \uc694\uc18c\ub97c \uc74c\uc218\ub85c \ubcc0\ud658\ud558\uc5ec \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n\n\n\n<figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<div class=\"ast-oembed-container\" style=\"height: 100%;\"><iframe loading=\"lazy\" title=\"\u110e\u1161\u11af\u1109\u1173\u110b\u1174 \u110b\u1161\u11af\u1100\u1169\u1105\u1175\u110c\u1173\u11b7 \u1106\u116e\u11ab\u110c\u1166\u1111\u116e\u11af\u110b\u1175(6) - \ud799\ud050(heapq)\ub97c \uc774\uc6a9\ud55c \ubb38\uc81c\ud480\uc774 \ubc0f \ud30c\uc774\uc36c\uc5d0\uc11c\uc758 \ud3ec\uc778\ud130 \uac1c\ub150 \uc124\uba85\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/fwUDjP9RVig?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/div>\n<\/div><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>Leetcode 703. Kth Largest Element in a Stream (Easy) heapq\ub294 Python\uc758 \ud45c\uc900 \ub77c\uc774\ube0c\ub7ec\ub9ac\uc5d0 \ud3ec\ud568\ub41c \ud799 \ud050(heap queue) \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud55c \ubaa8\ub4c8\uc785\ub2c8\ub2e4. \ud799\uc740 \ud2b9\ubcc4\ud55c \ud615\ud0dc\uc758 \uc774\uc9c4 \ud2b8\ub9ac\ub85c, \ub2e4\uc74c\uacfc \uac19\uc740 \ud2b9\uc9d5\uc744 \uac00\uc9d1\ub2c8\ub2e4: \ucd5c\uc18c \ud799(min heap): \ubd80\ubaa8 \ub178\ub4dc\uc758 \uac12\uc774 \ud56d\uc0c1 \uc790\uc2dd \ub178\ub4dc\uc758 \uac12\ubcf4\ub2e4 \uc791\uac70\ub098 \uac19\uc2b5\ub2c8\ub2e4. \uc644\uc804 \uc774\uc9c4 \ud2b8\ub9ac: \ub9c8\uc9c0\ub9c9 \ub808\ubca8\uc744 \uc81c\uc678\ud55c \ubaa8\ub4e0 \ub808\ubca8\uc774 \uc644\uc804\ud788 \ucc44\uc6cc\uc838 \uc788\uace0, \ub9c8\uc9c0\ub9c9 \ub808\ubca8\uc740 \uc67c\ucabd\ubd80\ud130 &hellip;<\/p>\n<p class=\"read-more\"> <a class=\"\" href=\"https:\/\/itjaeneungnanum.org\/?p=4501\"> <span class=\"screen-reader-text\">006. \ud799\ud050(heapq)\ub97c \uc774\uc6a9\ud55c \ubb38\uc81c \ud480\uc774\uc640 \ud30c\uc774\uc36c\uc5d0\uc11c\uc758 \ud3ec\uc778\ud130 \uac1c\ub150 \uc124\uba85<\/span> \ub354 \ubcf4\uae30 &raquo;<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"default","ast-global-header-display":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":""},"categories":[40],"tags":[],"_links":{"self":[{"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/posts\/4501"}],"collection":[{"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4501"}],"version-history":[{"count":1,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/posts\/4501\/revisions"}],"predecessor-version":[{"id":4502,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=\/wp\/v2\/posts\/4501\/revisions\/4502"}],"wp:attachment":[{"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4501"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4501"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/itjaeneungnanum.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4501"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}