{"id":35184,"date":"2024-11-01T09:36:30","date_gmt":"2024-11-01T09:36:30","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35184"},"modified":"2024-11-01T11:44:44","modified_gmt":"2024-11-01T11:44:44","slug":"kotlin-coding-test-course-finding-the-minimum-number-of-matrix-multiplication-operations","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35184\/","title":{"rendered":"kotlin coding test course, finding the minimum number of matrix multiplication operations"},"content":{"rendered":"<div class=\"blog-post\">\n<p>Matrix-related problems frequently appear in coding tests, and among them, matrix multiplication problems are a topic many candidates struggle with. In this article, we will examine the problem of &#8216;Finding the Minimum Number of Matrix Multiplication Operations&#8217; and explain the algorithm and code to solve it in detail.<\/p>\n<h2>Problem Description<\/h2>\n<p>When the size of matrix A is <code>A_rows x A_cols<\/code> and the size of matrix B is <code>B_rows x B_cols<\/code>, to perform the multiplication of the two matrices, the number of columns in A <code>A_cols<\/code> must match the number of rows in B <code>B_rows<\/code>. The complexity of this operation is calculated as <code>A_rows x A_cols x B_cols<\/code>.<\/p>\n<p>When multiplying multiple matrices, it is important to suitably select the &#8216;order of matrix multiplication&#8217; to enhance operational efficiency. For a given list of matrices, we need to compute the number of operations for all possible multiplication orders and find the minimum.<\/p>\n<h2>Input Format<\/h2>\n<p>The first line contains a natural number N (1 \u2264 N \u2264 30). The next N lines provide two integers R and C representing the size of each matrix. Here, R refers to the number of rows and C refers to the number of columns. It is assumed that the multiplication of each matrix is given in the form R\u00d7C.<\/p>\n<h2>Output Format<\/h2>\n<p>Print the minimum number of matrix multiplication operations on one line.<\/p>\n<h2>Example Input<\/h2>\n<pre>\n    3\n    10 20\n    20 30\n    30 40\n    <\/pre>\n<h2>Example Output<\/h2>\n<pre>\n    3000\n    <\/pre>\n<h2>Solution Process<\/h2>\n<p>The algorithm used to solve this problem is the &#8216;Dynamic Programming Method for Deciding the Order of Matrix Multiplication&#8217;. By using this method, we can efficiently compute the multiplication operation cost for each matrix combination.<\/p>\n<h3>Dynamic Programming Approach<\/h3>\n<p>To determine the order of matrix multiplication for the given problem, we proceed with the following steps:<\/p>\n<ol>\n<li>Create a DP table based on the entered matrix sizes.<\/li>\n<li>Recursively calculate the multiplication ratio and update to the minimum value.<\/li>\n<li>Finally, print the final value from the DP table.<\/li>\n<\/ol>\n<h3>DP Array and Initialization<\/h3>\n<p>First, we declare a two-dimensional array <code>dp<\/code> and initialize all values to 0. This array will store the minimum multiplication cost from matrix i to j in <code>dp[i][j]<\/code>.<\/p>\n<h3>Operation Count Calculation Logic<\/h3>\n<p>To calculate the number of multiplication operations for the matrix, we proceed with the DP as follows:<\/p>\n<ol>\n<li>Iterate through all possible intervals from i to j.<\/li>\n<li>Select a midpoint k for the current interval (i \u2264 k &lt; j).<\/li>\n<li>Calculate the costs of the two parts based on the current DP value and the midpoint, and sum them up.<\/li>\n<li>Update the minimum value.<\/li>\n<\/ol>\n<h3>Code Implementation<\/h3>\n<p>Below is the code implemented in Kotlin for the above process:<\/p>\n<pre>\n    fun matrixChainOrder(dims: IntArray): Int {\n        val n = dims.size - 1\n        val dp = Array(n) { IntArray(n) }\n\n        for (chainLength in 2..n) {\n            for (i in 0..n - chainLength) {\n                val j = i + chainLength - 1\n                dp[i][j] = Int.MAX_VALUE\n                for (k in i until j) {\n                    val cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]\n                    dp[i][j] = minOf(dp[i][j], cost)\n                }\n            }\n        }\n        return dp[0][n - 1]\n    }\n\n    fun main() {\n        val n = readLine()!!.toInt()\n        val dims = IntArray(n + 1)\n        for (i in 0 until n) {\n            val (r, c) = readLine()!!.split(\" \").map { it.toInt() }\n            dims[i] = r\n            if (i == n - 1) {\n                dims[i + 1] = c\n            } else {\n                dims[i + 1] = c\n            }\n        }\n        println(matrixChainOrder(dims))\n    }\n    <\/pre>\n<h2>Conclusion<\/h2>\n<p>Through this problem, we learned the optimization process of matrix multiplication, namely how to determine the optimal multiplication order. It is important to calculat the trivial parts step by step using dynamic programming to reduce the overall number of operations. Prepare adequately for these types of problems in coding tests, and practice repeatedly to gain an advantage. Next time, we will tackle even more in-depth problems!<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Matrix-related problems frequently appear in coding tests, and among them, matrix multiplication problems are a topic many candidates struggle with. In this article, we will examine the problem of &#8216;Finding the Minimum Number of Matrix Multiplication Operations&#8217; and explain the algorithm and code to solve it in detail. Problem Description When the size of matrix &hellip; <a href=\"https:\/\/atmokpo.com\/w\/35184\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;kotlin coding test course, finding the minimum number of matrix multiplication operations&#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":[106],"tags":[],"class_list":["post-35184","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v26.2 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>kotlin coding test course, finding the minimum number of matrix multiplication operations - \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\/35184\/\" \/>\n<meta property=\"og:locale\" content=\"ko_KR\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"kotlin coding test course, finding the minimum number of matrix multiplication operations - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Matrix-related problems frequently appear in coding tests, and among them, matrix multiplication problems are a topic many candidates struggle with. In this article, we will examine the problem of &#8216;Finding the Minimum Number of Matrix Multiplication Operations&#8217; and explain the algorithm and code to solve it in detail. Problem Description When the size of matrix &hellip; \ub354 \ubcf4\uae30 &quot;kotlin coding test course, finding the minimum number of matrix multiplication operations&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/35184\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:36:30+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:44:44+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\/35184\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35184\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"kotlin coding test course, finding the minimum number of matrix multiplication operations\",\"datePublished\":\"2024-11-01T09:36:30+00:00\",\"dateModified\":\"2024-11-01T11:44:44+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35184\/\"},\"wordCount\":486,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/35184\/\",\"url\":\"https:\/\/atmokpo.com\/w\/35184\/\",\"name\":\"kotlin coding test course, finding the minimum number of matrix multiplication operations - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:36:30+00:00\",\"dateModified\":\"2024-11-01T11:44:44+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35184\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/35184\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/35184\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"kotlin coding test course, finding the minimum number of matrix multiplication operations\"}]},{\"@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":"kotlin coding test course, finding the minimum number of matrix multiplication operations - \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\/35184\/","og_locale":"ko_KR","og_type":"article","og_title":"kotlin coding test course, finding the minimum number of matrix multiplication operations - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Matrix-related problems frequently appear in coding tests, and among them, matrix multiplication problems are a topic many candidates struggle with. In this article, we will examine the problem of &#8216;Finding the Minimum Number of Matrix Multiplication Operations&#8217; and explain the algorithm and code to solve it in detail. Problem Description When the size of matrix &hellip; \ub354 \ubcf4\uae30 \"kotlin coding test course, finding the minimum number of matrix multiplication operations\"","og_url":"https:\/\/atmokpo.com\/w\/35184\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:36:30+00:00","article_modified_time":"2024-11-01T11:44:44+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\/35184\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/35184\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"kotlin coding test course, finding the minimum number of matrix multiplication operations","datePublished":"2024-11-01T09:36:30+00:00","dateModified":"2024-11-01T11:44:44+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/35184\/"},"wordCount":486,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/35184\/","url":"https:\/\/atmokpo.com\/w\/35184\/","name":"kotlin coding test course, finding the minimum number of matrix multiplication operations - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:36:30+00:00","dateModified":"2024-11-01T11:44:44+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/35184\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/35184\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/35184\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"kotlin coding test course, finding the minimum number of matrix multiplication operations"}]},{"@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\/35184","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=35184"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35184\/revisions"}],"predecessor-version":[{"id":35185,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35184\/revisions\/35185"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=35184"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=35184"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=35184"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}