City D – (7, 7)<\/li>\n<\/ul>\n\n In this case, the salesman needs to find the minimum distance of the route that visits cities A, B, C, and D and returns back to A.\n <\/p>\n
Approach to the Problem<\/h2>\n
\n There are several approaches to solving this problem, but the most commonly used method is Dynamic Programming. By using dynamic programming, we can optimize the exploration of all cities.\n <\/p>\n
1. Dynamic Programming using Bit Masking<\/h3>\n
\n By using bit masking, we can represent the visit status of each city in bits. For example, the bit representation for 4 cities can be expressed with values from 0000 (no city visited) to 1111 (all cities visited). Each bit of 1 indicates that the corresponding city has been visited.\n <\/p>\n
2. Defining Dynamic Programming State<\/h3>\n
\n Let’s define the DP table. dp[mask][i] represents the minimum cost to arrive at city i with a bitmask indicating the visited cities as mask. The initial state is dp[1<<i][i] (each=”” 0).=”” <=\"\" ==\"\" i corresponds to=\"\" the=\"\" cost=\"\" of=\"\" visiting=\"\" city=\"\" i=\"\" itself=\"\" 0.=\"\"><\/p>\n
3. Defining the Recurrence Relation<\/h3>\n
\n The recurrence relation is as follows:\n <\/p>\n
\n dp[mask][i] = min(dp[mask ^ (1 << i)][j] + dist[j][i]) for all j where j is in mask and j != i\n <\/p>\n
\n This recurrence relation calculates the optimal cost of coming to the current city i from previously visited city j while in the state with the bitmask as mask.\n <\/p>\n
Code Implementation<\/h2>\n
\n Let’s implement the algorithm in Kotlin.\n <\/p>\n
\n \n fun main() {\n val cities = arrayOf(\n Pair(0, 0),\n Pair(1, 2),\n Pair(4, 3),\n Pair(7, 7)\n )\n val n = cities.size\n val dist = Array(n) { IntArray(n) }\n \n \/\/ Distance calculation\n for (i in 0 until n) {\n for (j in 0 until n) {\n dist[i][j] = manhattanDistance(cities[i], cities[j])\n }\n }\n\n \/\/ DP array initialization\n val dp = Array(1 shl n) { IntArray(n) { Int.MAX_VALUE } }\n\n for (i in 0 until n) {\n dp[1 shl i][i] = 0\n }\n\n \/\/ DP processing\n for (mask in 1 until (1 shl n)) {\n for (i in 0 until n) {\n if (mask and (1 shl i) == 0) continue\n for (j in 0 until n) {\n if (mask and (1 shl j) == 0 || i == j) continue\n dp[mask][i] = minOf(dp[mask][i], dp[mask xor (1 shl i)][j] + dist[j][i])\n }\n }\n }\n\n \/\/ Minimum cost calculation\n var minCost = Int.MAX_VALUE\n \n for (i in 0 until n) {\n minCost = minOf(minCost, dp[(1 shl n) - 1][i] + dist[i][0])\n }\n println(\"Minimum cost: $minCost\")\n }\n\n fun manhattanDistance(city1: Pair, city2: Pair): Int {\n return Math.abs(city1.first - city2.first) + Math.abs(city1.second - city2.second)\n }\n <\/int,><\/int,><\/code>\n <\/pre>\nCode Explanation<\/h2>\n
\n The code above calculates the cost of the optimal path through dynamic programming in the following steps:\n <\/p>\n
\n- Distance Calculation:<\/strong> Calculate the Manhattan distance between two cities.<\/li>\n
- DP Initialization:<\/strong> Set the initial DP array in the state of not having visited any cities.<\/li>\n
- DP Processing:<\/strong> Calculate the optimal cost based on the bit mask and the current city.<\/li>\n
- Minimum Cost Calculation:<\/strong> Calculate the minimum cost of returning after visiting all cities.<\/li>\n<\/ol>\n
Complexity Analysis<\/h2>\n
\n The time complexity of this algorithm is O(n^2 * 2^n). This works effectively when n is small, but performance degrades sharply as n increases. Therefore, this problem may be inefficient for large inputs, requiring various optimization techniques.\n <\/p>\n
Conclusion<\/h2>\n
\n The “Salesman’s Dilemma” problem is one of the frequently encountered algorithmic problems in coding tests. Through this problem, one can understand the importance of dynamic programming and bit masking, as well as learn how to solve it using Kotlin. It is advisable to develop the ability to solve more complex problems by engaging in deeper learning of optimization and other techniques.\n <\/p>\n
<\/i][i]><\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
Problem Description A salesman needs to visit customers in various cities. The salesman can sell products in each city, and each city is located at different distances from one another. The goal of the salesman is to find the minimum cost of traveling to all cities and returning to the starting city. This problem is … \ub354 \ubcf4\uae30 “Kotlin coding test course, Salesman’s dilemma”<\/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-35040","post","type-post","status-publish","format-standard","hentry","category----en"],"yoast_head":"\nKotlin coding test course, Salesman's dilemma - \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\/35040\/\" \/>\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, Salesman's dilemma - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Problem Description A salesman needs to visit customers in various cities. The salesman can sell products in each city, and each city is located at different distances from one another. The goal of the salesman is to find the minimum cost of traveling to all cities and returning to the starting city. This problem is … \ub354 \ubcf4\uae30 "Kotlin coding test course, Salesman’s dilemma"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/35040\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:34:55+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T12:49: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\/35040\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35040\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Kotlin coding test course, Salesman’s dilemma\",\"datePublished\":\"2024-11-01T09:34:55+00:00\",\"dateModified\":\"2024-11-01T12:49:44+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35040\/\"},\"wordCount\":498,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/35040\/\",\"url\":\"https:\/\/atmokpo.com\/w\/35040\/\",\"name\":\"Kotlin coding test course, Salesman's dilemma - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:34:55+00:00\",\"dateModified\":\"2024-11-01T12:49:44+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35040\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/35040\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/35040\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Kotlin coding test course, Salesman’s dilemma\"}]},{\"@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, Salesman's dilemma - \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\/35040\/","og_locale":"ko_KR","og_type":"article","og_title":"Kotlin coding test course, Salesman's dilemma - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Problem Description A salesman needs to visit customers in various cities. The salesman can sell products in each city, and each city is located at different distances from one another. The goal of the salesman is to find the minimum cost of traveling to all cities and returning to the starting city. This problem is … \ub354 \ubcf4\uae30 \"Kotlin coding test course, Salesman’s dilemma\"","og_url":"https:\/\/atmokpo.com\/w\/35040\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:34:55+00:00","article_modified_time":"2024-11-01T12:49: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\/35040\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/35040\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Kotlin coding test course, Salesman’s dilemma","datePublished":"2024-11-01T09:34:55+00:00","dateModified":"2024-11-01T12:49:44+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/35040\/"},"wordCount":498,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/35040\/","url":"https:\/\/atmokpo.com\/w\/35040\/","name":"Kotlin coding test course, Salesman's dilemma - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:34:55+00:00","dateModified":"2024-11-01T12:49:44+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/35040\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/35040\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/35040\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"Kotlin coding test course, Salesman’s dilemma"}]},{"@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\/35040","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=35040"}],"version-history":[{"count":2,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35040\/revisions"}],"predecessor-version":[{"id":38101,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35040\/revisions\/38101"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=35040"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=35040"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=35040"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}