{"id":33281,"date":"2024-11-01T09:15:07","date_gmt":"2024-11-01T09:15:07","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33281"},"modified":"2024-11-01T11:39:22","modified_gmt":"2024-11-01T11:39:22","slug":"java-coding-test-course-2-n-tile-filling","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33281\/","title":{"rendered":"Java Coding Test Course, 2 N Tile Filling"},"content":{"rendered":"<article>\n<section>\n<h2>Problem Description<\/h2>\n<p>\n            This is a problem of finding the number of ways to fill an N x 2 space with 2 x 1 sized tiles.<br \/>\n            When the size of the given space is N, the goal is to calculate the number of ways to completely fill the space by joining tiles in various forms.\n        <\/p>\n<p>\n            This problem can be solved using Dynamic Programming techniques.<br \/>\n            It approaches the current state based on previous states depending on how each tile is arranged.\n        <\/p>\n<\/section>\n<section>\n<h2>Problem Example<\/h2>\n<p>\n            For example, when N is 3, the following arrangements are possible:\n        <\/p>\n<ul>\n<li>Place 3 tiles vertically<\/li>\n<li>Place 2 tiles horizontally and 1 tile vertically<\/li>\n<li>Place 1 tile vertically, 2 tiles horizontally, and 1 tile vertically<\/li>\n<li>Place 1 tile horizontally, 2 tiles vertically, and 1 tile horizontally<\/li>\n<\/ul>\n<p>\n            The output result for the arrangements above will be 5.\n        <\/p>\n<\/section>\n<section>\n<h2>Problem Solving Process<\/h2>\n<h3>Step 1: State Definition<\/h3>\n<p>\n            To solve the problem, we first need to define the state.<br \/>\n            If we let the function f(N) represent the number of ways to fill an N x 2 space, we can establish the following recurrence relation:\n        <\/p>\n<p>\n            f(N) = f(N-1) + f(N-2)\n        <\/p>\n<p>\n            Here, f(N-1) refers to the case where a tile is placed vertically in an N-1 x 2 space,<br \/>\n            and f(N-2) refers to the case where two tiles are placed horizontally in an N-2 x 2 space.\n        <\/p>\n<h3>Step 2: Initial Condition Definition<\/h3>\n<p>\n            We need to define the initial conditions. When N is 1, we can place a tile vertically, so f(1) = 1.<br \/>\n            When N is 2, we can place two tiles vertically or horizontally, so f(2) = 2.\n        <\/p>\n<h3>Step 3: Solving Method Using Recurrence Relation<\/h3>\n<p>\n            We can compute step-by-step up to N using the recurrence relation.<br \/>\n            While an array can be used, it is sufficient to use only two variables.<br \/>\n            This is because knowing just the previous two values allows us to calculate the next value.\n        <\/p>\n<\/section>\n<section>\n<h2>Java Code Example<\/h2>\n<pre>\n            <code>\n                public class Tiling {\n                    public static void main(String[] args) {\n                        int N = 5; \/\/ For example, set N to 5\n                        System.out.println(\"Number of ways to fill a 2 x \" + N + \" space: \" + countWays(N));\n                    }\n\n                    static int countWays(int N) {\n                        if (N == 1) return 1; \/\/ Base condition 1\n                        if (N == 2) return 2; \/\/ Base condition 2\n\n                        int[] dp = new int[N + 1];\n                        dp[1] = 1;\n                        dp[2] = 2;\n\n                        for (int i = 3; i <= N; i++) {\n                            dp[i] = dp[i - 1] + dp[i - 2]; \/\/ Recurrence relation\n                        }\n\n                        return dp[N];\n                    }\n                }\n            <\/code>\n        <\/pre>\n<\/section>\n<section>\n<h2>Time and Space Complexity Analysis<\/h2>\n<p>\n            In the above example, the time complexity is O(N), increasing proportionally with N. This is because every state is calculated once.<br \/>\n            The space complexity is O(N) due to the need to use a dp array for storage.<br \/>\n            However, it can be optimized to O(1) by using just two variables.\n        <\/p>\n<\/section>\n<section>\n<h2>Conclusion<\/h2>\n<p>\n            The 2*N tiling problem is a representative example of dynamic programming,<br \/>\n            aiding in implementing efficient algorithms while optimizing memory usage.<br \/>\n            Through such problems, one can deepen their understanding of basic algorithms and data structures and practice with various variations. Give it a try!\n        <\/p>\n<\/section>\n<\/article>\n","protected":false},"excerpt":{"rendered":"<p>Problem Description This is a problem of finding the number of ways to fill an N x 2 space with 2 x 1 sized tiles. When the size of the given space is N, the goal is to calculate the number of ways to completely fill the space by joining tiles in various forms. This &hellip; <a href=\"https:\/\/atmokpo.com\/w\/33281\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Java 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":[139],"tags":[],"class_list":["post-33281","post","type-post","status-publish","format-standard","hentry","category-java-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Java 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\/33281\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Java Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Problem Description This is a problem of finding the number of ways to fill an N x 2 space with 2 x 1 sized tiles. When the size of the given space is N, the goal is to calculate the number of ways to completely fill the space by joining tiles in various forms. This &hellip; \ub354 \ubcf4\uae30 &quot;Java Coding Test Course, 2 N Tile Filling&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/33281\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:15:07+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:39:22+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=\"2\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/33281\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33281\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Java Coding Test Course, 2 N Tile Filling\",\"datePublished\":\"2024-11-01T09:15:07+00:00\",\"dateModified\":\"2024-11-01T11:39:22+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33281\/\"},\"wordCount\":398,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Java Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/33281\/\",\"url\":\"https:\/\/atmokpo.com\/w\/33281\/\",\"name\":\"Java Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:15:07+00:00\",\"dateModified\":\"2024-11-01T11:39:22+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/33281\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/33281\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/33281\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Java 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":"Java 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\/33281\/","og_locale":"ko_KR","og_type":"article","og_title":"Java Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Problem Description This is a problem of finding the number of ways to fill an N x 2 space with 2 x 1 sized tiles. When the size of the given space is N, the goal is to calculate the number of ways to completely fill the space by joining tiles in various forms. This &hellip; \ub354 \ubcf4\uae30 \"Java Coding Test Course, 2 N Tile Filling\"","og_url":"https:\/\/atmokpo.com\/w\/33281\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:15:07+00:00","article_modified_time":"2024-11-01T11:39:22+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":"2\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/33281\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/33281\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Java Coding Test Course, 2 N Tile Filling","datePublished":"2024-11-01T09:15:07+00:00","dateModified":"2024-11-01T11:39:22+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/33281\/"},"wordCount":398,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Java Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/33281\/","url":"https:\/\/atmokpo.com\/w\/33281\/","name":"Java Coding Test Course, 2 N Tile Filling - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:15:07+00:00","dateModified":"2024-11-01T11:39:22+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/33281\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/33281\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/33281\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Java 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\/33281","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=33281"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33281\/revisions"}],"predecessor-version":[{"id":33282,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/33281\/revisions\/33282"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=33281"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=33281"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=33281"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}