{"id":34638,"date":"2024-11-01T09:30:22","date_gmt":"2024-11-01T09:30:22","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34638"},"modified":"2024-11-01T11:40:24","modified_gmt":"2024-11-01T11:40:24","slug":"javascript-coding-test-course-calculating-number-of-stairs","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34638\/","title":{"rendered":"JavaScript Coding Test Course, Calculating Number of Stairs"},"content":{"rendered":"<div class=\"blog-post\">\n<p>Hello, today we will solve one of the algorithm problems useful for JavaScript coding test preparation, called &#8220;Counting Stair Numbers&#8221;. This problem can be approached interestingly using Dynamic Programming and combinatorial methods. In this article, I will provide a detailed explanation including the problem description, the solution process, and optimization strategies.<\/p>\n<h2>Problem Description<\/h2>\n<p>A stair number refers to a number of n digits where the difference between two adjacent digits is 1. For example, numbers like 123 and 321 are stair numbers since the difference between adjacent digits is 1. Write a program to find the n-digit stair numbers for the given n.<\/p>\n<h3>Input<\/h3>\n<p>An integer n (1 \u2264 n \u2264 1000)<\/p>\n<h3>Output<\/h3>\n<p>Output the number of n-digit stair numbers modulo 1,000,000,000.<\/p>\n<h2>Problem Solving Strategy<\/h2>\n<p>To solve this problem, we can use a dynamic programming approach. Stair numbers can be defined by the following state:<\/p>\n<ul>\n<li>dp[i][j]: the number of i-digit stair numbers that end with j<\/li>\n<\/ul>\n<p>The rules for forming stair numbers can be established as follows:<\/p>\n<ul>\n<li>When j is 0 (no number can start with 0): dp[i][0] = dp[i-1][1]<\/li>\n<li>When j is 9: dp[i][9] = dp[i-1][8]<\/li>\n<li>In other cases: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]<\/li>\n<\/ul>\n<h2>Initialization of the Dynamic Programming Table<\/h2>\n<p>Now let&#8217;s initialize the dp table. For 1-digit numbers, since digits can range from 0 to 9, we initialize dp[1][0] to dp[1][9] to 1 respectively.<\/p>\n<h2>Solution Code<\/h2>\n<pre><code>\nfunction countStairNumbers(n) {\n    const MOD = 1000000000;\n    const dp = Array.from({ length: n + 1 }, () =&gt; Array(10).fill(0));\n\n    \/\/ Initialize 1-digit numbers\n    for (let j = 0; j &lt; 10; j++) {\n        dp[1][j] = 1;\n    }\n\n    \/\/ Fill the dp table\n    for (let i = 2; i &lt;= n; i++) {\n        for (let j = 0; j &lt; 10; j++) {\n            if (j &gt; 0) dp[i][j] += dp[i - 1][j - 1]; \/\/ Move from j-1\n            if (j &lt; 9) dp[i][j] += dp[i - 1][j + 1]; \/\/ Move from j+1\n            dp[i][j] %= MOD; \/\/ modulo operation\n        }\n    }\n\n    \/\/ Sum of all n-digit stair numbers\n    let result = 0;\n    for (let j = 0; j &lt; 10; j++) {\n        result += dp[n][j];\n    }\n\n    return result % MOD;\n}\n\n\/\/ Example of function call\nconsole.log(countStairNumbers(3)); \/\/ 24\n<\/code><\/pre>\n<h2>Time Complexity<\/h2>\n<p>The time complexity of the above code is O(n), and the space complexity is O(n). Since the result is derived through combinations of each digit, it efficiently uses time and space as n increases.<\/p>\n<h2>Optimization Strategies<\/h2>\n<p>To reduce memory usage in the currently implemented code, we can change the dp array from two-dimensional to one-dimensional. Since only the previous dp state is needed for each i, this can be utilized for optimization.<\/p>\n<pre><code>\nfunction countStairNumbersOptimized(n) {\n    const MOD = 1000000000;\n    const dp = Array(10).fill(0);\n    const temp = Array(10).fill(0);\n\n    \/\/ Initialize 1-digit numbers\n    for (let j = 0; j &lt; 10; j++) {\n        dp[j] = 1;\n    }\n\n    for (let i = 2; i &lt;= n; i++) {\n        for (let j = 0; j &lt; 10; j++) {\n            temp[j] = 0;\n            if (j &gt; 0) temp[j] += dp[j - 1]; \/\/ Move from j-1\n            if (j &lt; 9) temp[j] += dp[j + 1]; \/\/ Move from j+1\n            temp[j] %= MOD; \/\/ modulo operation\n        }\n        for (let j = 0; j &lt; 10; j++) {\n            dp[j] = temp[j]; \/\/ Update for the next step\n        }\n    }\n\n    \/\/ Sum of all n-digit stair numbers\n    let result = 0;\n    for (let j = 0; j &lt; 10; j++) {\n        result += dp[j];\n    }\n\n    return result % MOD;\n}\n<\/code><\/pre>\n<h2>Conclusion<\/h2>\n<p>In this article, we learned how to solve the &#8220;Counting Stair Numbers&#8221; problem using dynamic programming in JavaScript. I provided a detailed explanation of initialization, constructing the dp table, and the optimization process, as well as methods to enhance the efficiency of the algorithm through various techniques. When solving algorithm problems, always consider multiple approaches and explore ways to optimize them. Thank you!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Hello, today we will solve one of the algorithm problems useful for JavaScript coding test preparation, called &#8220;Counting Stair Numbers&#8221;. This problem can be approached interestingly using Dynamic Programming and combinatorial methods. In this article, I will provide a detailed explanation including the problem description, the solution process, and optimization strategies. Problem Description A stair &hellip; <a href=\"https:\/\/atmokpo.com\/w\/34638\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;JavaScript Coding Test Course, Calculating Number of Stairs&#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":[141],"tags":[],"class_list":["post-34638","post","type-post","status-publish","format-standard","hentry","category-javascript-coding-test"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>JavaScript Coding Test Course, Calculating Number of Stairs - \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\/34638\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"JavaScript Coding Test Course, Calculating Number of Stairs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello, today we will solve one of the algorithm problems useful for JavaScript coding test preparation, called &#8220;Counting Stair Numbers&#8221;. This problem can be approached interestingly using Dynamic Programming and combinatorial methods. In this article, I will provide a detailed explanation including the problem description, the solution process, and optimization strategies. Problem Description A stair &hellip; \ub354 \ubcf4\uae30 &quot;JavaScript Coding Test Course, Calculating Number of Stairs&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34638\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:30:22+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:40:24+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\/34638\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34638\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"JavaScript Coding Test Course, Calculating Number of Stairs\",\"datePublished\":\"2024-11-01T09:30:22+00:00\",\"dateModified\":\"2024-11-01T11:40:24+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34638\/\"},\"wordCount\":370,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Javascript Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34638\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34638\/\",\"name\":\"JavaScript Coding Test Course, Calculating Number of Stairs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:30:22+00:00\",\"dateModified\":\"2024-11-01T11:40:24+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34638\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34638\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34638\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"JavaScript Coding Test Course, Calculating Number of Stairs\"}]},{\"@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":"JavaScript Coding Test Course, Calculating Number of Stairs - \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\/34638\/","og_locale":"ko_KR","og_type":"article","og_title":"JavaScript Coding Test Course, Calculating Number of Stairs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello, today we will solve one of the algorithm problems useful for JavaScript coding test preparation, called &#8220;Counting Stair Numbers&#8221;. This problem can be approached interestingly using Dynamic Programming and combinatorial methods. In this article, I will provide a detailed explanation including the problem description, the solution process, and optimization strategies. Problem Description A stair &hellip; \ub354 \ubcf4\uae30 \"JavaScript Coding Test Course, Calculating Number of Stairs\"","og_url":"https:\/\/atmokpo.com\/w\/34638\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:30:22+00:00","article_modified_time":"2024-11-01T11:40:24+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\/34638\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34638\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"JavaScript Coding Test Course, Calculating Number of Stairs","datePublished":"2024-11-01T09:30:22+00:00","dateModified":"2024-11-01T11:40:24+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34638\/"},"wordCount":370,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Javascript Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34638\/","url":"https:\/\/atmokpo.com\/w\/34638\/","name":"JavaScript Coding Test Course, Calculating Number of Stairs - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:30:22+00:00","dateModified":"2024-11-01T11:40:24+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34638\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34638\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34638\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"JavaScript Coding Test Course, Calculating Number of Stairs"}]},{"@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\/34638","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=34638"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34638\/revisions"}],"predecessor-version":[{"id":34639,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34638\/revisions\/34639"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34638"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34638"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34638"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}