{"id":33556,"date":"2024-11-01T09:17:47","date_gmt":"2024-11-01T09:17:47","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33556"},"modified":"2024-11-01T11:47:38","modified_gmt":"2024-11-01T11:47:38","slug":"python-coding-test-course-2-n-tile-filling","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33556\/","title":{"rendered":"Python Coding Test Course, 2 N Tile Filling"},"content":{"rendered":"<div class=\"blog-post\">\n<p>In today&#8217;s world, where programming and algorithms are becoming increasingly important, many companies require algorithm and coding tests as a prerequisite for employment. One of the popular problems is <strong>2*N Tile Filling<\/strong>. In this article, I will analyze the problem and explain the process of solving it in detail. Through this problem, we will also learn the concept of dynamic programming (DP) and look at a Python code implementation using it.<\/p>\n<h2>Problem Description<\/h2>\n<p>The problem is as follows:<\/p>\n<blockquote>\n<p>Find the number of ways to fill a 2 x n rectangular space with tiles of size 1 x 2 or 2 x 1.<\/p>\n<p>For example, when n=3, the tiles can be filled in the following ways:<\/p>\n<ul>\n<li>3 vertical 1 x 2 tiles<\/li>\n<li>1 horizontal 1 x 2 tile and 2 vertical tiles<\/li>\n<li>2 horizontal 1 x 2 tiles and 1 vertical tile<\/li>\n<li>1 2 x 1 tile and 2 1 x 2 tiles<\/li>\n<li>3 vertical 2 x 1 tiles<\/li>\n<\/ul>\n<\/blockquote>\n<p>The solution to this problem can be approached through dynamic programming. The key is to recursively divide the problem based on how each tile is placed and avoid duplicate calculations by storing results using the memoization technique.<\/p>\n<h2>Approach to Problem Solving<\/h2>\n<p>This problem can be solved based on the following rules:<\/p>\n<ul>\n<li>Base case: For n=1, only the method of placing a 1 x 2 tile vertically is possible. Therefore, the number of cases is 1.<\/li>\n<li>More general case: For n=2, there are two ways: either to place 2 horizontal 1 x 2 tiles or to place 1 vertical 2 x 1 tile. Thus, the number of cases is 2.<\/li>\n<li>Recursive relationship: For n > 2, it can be divided in two ways:\n<ol>\n<li>Place a 1 x 2 tile and fill the remaining 2 x (n-1) space<\/li>\n<li>Place a 2 x 1 tile and fill the remaining 2 x (n-2) space<\/li>\n<\/ol>\n<p>            Therefore, the recursive relation can be expressed as:<br \/>\n            <strong>f(n) = f(n-1) + f(n-2)<\/strong>\n<\/li>\n<\/ul>\n<h2>Dynamic Programming Implementation<\/h2>\n<p>Now, let\u2019s write a Python code to solve the problem using dynamic programming (DP) based on the recursive relationship above.<\/p>\n<pre><code>\ndef tile_fill(n):\n    # Initialize the DP array.\n    dp = [0] * (n + 1)\n    \n    # Set the base cases.\n    dp[0] = 1  # The case of filling nothing\n    if n >= 1:\n        dp[1] = 1  # The case of placing a 1 x 2 tile vertically\n    \n    # Fill the DP array.\n    for i in range(2, n + 1):\n        dp[i] = dp[i - 1] + dp[i - 2]\n    \n    return dp[n]\n    <\/code><\/pre>\n<h3>Code Explanation<\/h3>\n<p>In the above code, we first initialize the DP array from 0 to n. After setting the values for f(0) and f(1) as base cases, we proceed to fill the values from f(2) to f(n) using a loop. Ultimately, the value of <code>dp[n]<\/code> represents the number of ways to fill the 2 x n rectangle.<\/p>\n<h2>Time Complexity Analysis<\/h2>\n<p>The time complexity of this algorithm is O(n). This is because in each iteration, the DP array only repeats as many times as the number of elements in the n structure. The space complexity is also O(n).<\/p>\n<h2>Summary<\/h2>\n<p>In this article, we learned how to utilize dynamic programming techniques through the <strong>2*N Tile Filling Problem<\/strong>. By defining the problem, deriving solutions through repetitive formulas, and implementing this in code, we were able to develop algorithmic thinking. Similar problems may appear in actual coding tests, so it is advisable to practice consistently.<\/p>\n<h2>Problem Variations and Applications<\/h2>\n<p>If the given rectangular size were to change from 2 x N to another form, for example, to 3 x N, think about how you would approach it. Practicing variations of problems will significantly help in deepening algorithmic thinking.<\/p>\n<p>In conclusion, when solving algorithm problems, it is important to decompose the problem and explore possible solutions. The 2*N tile filling problem is a good example of how to embody that kind of thinking.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>In today&#8217;s world, where programming and algorithms are becoming increasingly important, many companies require algorithm and coding tests as a prerequisite for employment. One of the popular problems is 2*N Tile Filling. In this article, I will analyze the problem and explain the process of solving it in detail. Through this problem, we will also &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33556\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Python Coding Test Course, 2 N Tile Filling&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[145],"tags":[],"class_list":["post-33556","post","type-post","status-publish","format-standard","hentry","category-python-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Python Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/atmokpo.com\/w\/33556\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Python Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"In today&#8217;s world, where programming and algorithms are becoming increasingly important, many companies require algorithm and coding tests as a prerequisite for employment. One of the popular problems is 2*N Tile Filling. In this article, I will analyze the problem and explain the process of solving it in detail. Through this problem, we will also &hellip; \ub354 \ubcf4\uae30 &quot;Python Coding Test Course, 2 N Tile Filling&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33556\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:17:47+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:47:38+00:00\" \/>\n<meta name=\"author\" content=\"root\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:site\" content=\"@bebubo4\" \/>\n<meta name=\"twitter:label1\" content=\"\uae00\uc4f4\uc774\" \/>\n\t<meta name=\"twitter:data1\" content=\"root\" \/>\n\t<meta name=\"twitter:label2\" content=\"\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04\" \/>\n\t<meta name=\"twitter:data2\" content=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33556\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33556\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Python Coding Test Course, 2 N Tile Filling\",\"datePublished\":\"2024-11-01T09:17:47+00:00\",\"dateModified\":\"2024-11-01T11:47:38+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33556\/\"},\"wordCount\":537,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Python Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33556\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33556\/\",\"name\":\"Python Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:17:47+00:00\",\"dateModified\":\"2024-11-01T11:47:38+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33556\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33556\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33556\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Python Coding Test Course, 2 N Tile Filling\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/atmokpo.com\/w\/#website\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/atmokpo.com\/w\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"ko-KR\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\",\"name\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"url\":\"https:\/\/atmokpo.com\/w\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"contentUrl\":\"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png\",\"width\":400,\"height\":400,\"caption\":\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\"},\"image\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/bebubo4\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\",\"name\":\"root\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"ko-KR\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g\",\"caption\":\"root\"},\"sameAs\":[\"http:\/\/atmokpo.com\/w\"],\"url\":\"https:\/\/atmokpo.com\/w\/author\/root\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Python Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/atmokpo.com\/w\/33556\/","og_locale":"ko_KR","og_type":"article","og_title":"Python Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"In today&#8217;s world, where programming and algorithms are becoming increasingly important, many companies require algorithm and coding tests as a prerequisite for employment. One of the popular problems is 2*N Tile Filling. In this article, I will analyze the problem and explain the process of solving it in detail. Through this problem, we will also &hellip; \ub354 \ubcf4\uae30 \"Python Coding Test Course, 2 N Tile Filling\"","og_url":"https:\/\/atmokpo.com\/w\/33556\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:17:47+00:00","article_modified_time":"2024-11-01T11:47:38+00:00","author":"root","twitter_card":"summary_large_image","twitter_creator":"@bebubo4","twitter_site":"@bebubo4","twitter_misc":{"\uae00\uc4f4\uc774":"root","\uc608\uc0c1 \ub418\ub294 \ud310\ub3c5 \uc2dc\uac04":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33556\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33556\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Python Coding Test Course, 2 N Tile Filling","datePublished":"2024-11-01T09:17:47+00:00","dateModified":"2024-11-01T11:47:38+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33556\/"},"wordCount":537,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Python Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33556\/","url":"https:\/\/atmokpo.com\/w\/33556\/","name":"Python Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:17:47+00:00","dateModified":"2024-11-01T11:47:38+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33556\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33556\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33556\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Python Coding Test Course, 2 N Tile Filling"}]},{"@type":"WebSite","@id":"https:\/\/atmokpo.com\/w\/#website","url":"https:\/\/atmokpo.com\/w\/","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","description":"","publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/atmokpo.com\/w\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"ko-KR"},{"@type":"Organization","@id":"https:\/\/atmokpo.com\/w\/#organization","name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","url":"https:\/\/atmokpo.com\/w\/","logo":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/","url":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","contentUrl":"https:\/\/atmokpo.com\/w\/wp-content\/uploads\/2024\/11\/logo.png","width":400,"height":400,"caption":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8"},"image":{"@id":"https:\/\/atmokpo.com\/w\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/bebubo4"]},{"@type":"Person","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7","name":"root","image":{"@type":"ImageObject","inLanguage":"ko-KR","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/708197b41fc6435a7ce22d951b25d4a47e9e904270cb1f04682d4f025066f80c?s=96&d=mm&r=g","caption":"root"},"sameAs":["http:\/\/atmokpo.com\/w"],"url":"https:\/\/atmokpo.com\/w\/author\/root\/"}]}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33556","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/comments?post=33556"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33556\/revisions"}],"predecessor-version":[{"id":33557,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33556\/revisions\/33557"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33556"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33556"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33556"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}