{"id":35134,"date":"2024-11-01T09:35:56","date_gmt":"2024-11-01T09:35:56","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35134"},"modified":"2024-11-01T12:41:12","modified_gmt":"2024-11-01T12:41:12","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%b5%9c%ec%86%8c-%ea%b3%b5%ed%86%b5-%ec%a1%b0%ec%83%81-%ea%b5%ac%ed%95%98%ea%b8%b0-2-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35134\/","title":{"rendered":"Kotlin coding test course, finding the lowest common ancestor"},"content":{"rendered":"<p>Hello! In this session, we will solve the problem of finding the Lowest Common Ancestor (LCA) using Kotlin through a series of algorithmic problems. This problem is one of the important concepts dealing with tree structures and appears in various coding tests. This course will detail the problem definition, solution process, and optimization methods along with explanations of the topic.<\/p>\n<h2>Problem Definition<\/h2>\n<p>The problem is to find the lowest common ancestor of node A and node B when a tree structure is given. The Lowest Common Ancestor is the deepest ancestor among the ancestors of nodes A and B. For example, consider the tree structure shown below.<\/p>\n<pre>\n            1\n           \/ \\\n          2   3\n         \/ \\   \\\n        4   5   6\n       \/\n      7\n<\/pre>\n<p>In this case, the lowest common ancestor of node 4 and node 5 is node 2. Additionally, the lowest common ancestor of node 4 and node 6 is node 1.<\/p>\n<h2>Input<\/h2>\n<ul>\n<li>First line: The number of nodes N in the tree (1 \u2264 N \u2264 20,000)<\/li>\n<li>From the second line to the N-1th line: Two integers a, b are given, indicating that a is the parent of b.<\/li>\n<li>Last line: Two integers X, Y (1 \u2264 X, Y \u2264 N) which are the nodes for which we need to find the LCA.<\/li>\n<\/ul>\n<h2>Output<\/h2>\n<p>Print the node number of the lowest common ancestor.<\/p>\n<h2>Example Input<\/h2>\n<pre>\n7\n1 2\n1 3\n2 4\n2 5\n4 7\n3 6\n4 6\n<\/pre>\n<h2>Example Output<\/h2>\n<pre>\n1\n<\/pre>\n<h2>Problem Solving Process<\/h2>\n<p>Now, I will explain the approach to solving the problem. In tree structures, it is common to use DFS (Depth-First Search) or BFS (Breadth-First Search) to store the depth of nodes and record parent nodes. This method allows us to compare the depth of each node and find the common ancestor.<\/p>\n<h3>1. Build the Tree<\/h3>\n<p>First, we need to build the tree based on the information given in the input. In Kotlin, this can be implemented using a list to store the children of each node.<\/p>\n<pre><code>\ndata class TreeNode(val id: Int) {\n    val children = mutableListOf<TreeNode>()\n}\n\nfun buildTree(n: Int, edges: List<Pair<Int, Int>>): Map<Int, TreeNode> {\n    val nodes = mutableMapOf<Int, TreeNode>()\n    edges.forEach { (parentId, childId) ->\n        val parentNode = nodes.getOrPut(parentId) { TreeNode(parentId) }\n        val childNode = nodes.getOrPut(childId) { TreeNode(childId) }\n        parentNode.children.add(childNode)\n    }\n    return nodes\n}\n<\/code><\/pre>\n<h3>2. Store Depth and Parent Nodes<\/h3>\n<p>We will write a function to store depth and parent nodes using DFS. This will be helpful for finding the LCA later on.<\/p>\n<pre><code>\nval depth = mutableMapOf<Int, Int>()\nval parent = mutableMapOf<Int, Int>()\n\nfun dfs(node: TreeNode, dep: Int) {\n    depth[node.id] = dep\n    for (child in node.children) {\n        parent[child.id] = node.id\n        dfs(child, dep + 1)\n    }\n}\n\n\/\/ Example usage\nval root = nodes[1] \/\/ Root node (ID: 1)\ndfs(root, 0)\n<\/code><\/pre>\n<h3>3. Find LCA<\/h3>\n<p>Now we will implement a function to find the LCA of the two nodes. We will compare the two given nodes to adjust their depths and find the ancestor.<\/p>\n<pre><code>\nfun findLCA(x: Int, y: Int): Int {\n    \/\/ Adjust depth\n    var a = x\n    var b = y\n    while (depth[a] > depth[b]) {\n        a = parent[a]!!\n    }\n    while (depth[b] > depth[a]) {\n        b = parent[b]!!\n    }\n    while (a != b) {\n        a = parent[a]!!\n        b = parent[b]!!\n    }\n    return a\n}\n\n\/\/ Example usage\nval lca = findLCA(4, 6)\nprintln(\"LCA: $lca\")\n<\/code><\/pre>\n<h3>4. Full Implementation<\/h3>\n<p>Now, we will consolidate all the steps to write the complete program.<\/p>\n<pre><code>\nfun main() {\n    val n = readLine()!!.toInt()\n    val edges = mutableListOf<Pair<Int, Int>>()\n    repeat(n - 1) {\n        val (a, b) = readLine()!!.split(\" \").map { it.toInt() }\n        edges.add(Pair(a, b))\n    }\n    val (x, y) = readLine()!!.split(\" \").map { it.toInt() }\n\n    val nodes = buildTree(n, edges)\n\n    val depth = mutableMapOf<Int, Int>()\n    val parent = mutableMapOf<Int, Int>()\n\n    fun dfs(node: TreeNode, dep: Int) {\n        depth[node.id] = dep\n        for (child in node.children) {\n            parent[child.id] = node.id\n            dfs(child, dep + 1)\n        }\n    }\n\n    val root = nodes[1]\n    dfs(root, 0)\n\n    fun findLCA(x: Int, y: Int): Int {\n        var a = x\n        var b = y\n        while (depth[a] > depth[b]) {\n            a = parent[a]!!\n        }\n        while (depth[b] > depth[a]) {\n            b = parent[b]!!\n        }\n        while (a != b) {\n            a = parent[a]!!\n            b = parent[b]!!\n        }\n        return a\n    }\n\n    val lca = findLCA(x, y)\n    println(\"LCA: $lca\")\n}\n<\/code><\/pre>\n<h2>Optimization<\/h2>\n<p>The current method calculates depth and parent nodes using DFS and then finds the LCA. This method operates in O(N) time, and finding the LCA takes O(log N) time complexity. However, for larger values of N, it is possible to utilize optimized algorithms such as &#8220;Sparse Table&#8221; or &#8220;Binary Lifting.&#8221; These methods can further reduce time complexity.<\/p>\n<h3>Conclusion<\/h3>\n<p>In this lecture, we learned about how to find the lowest common ancestor. The LCA problem in tree structures is a common topic in algorithm problems, so it is important to practice thoroughly until it becomes second nature. Try writing and understanding the code step by step. Next time, we will return with another topic. Thank you!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Hello! In this session, we will solve the problem of finding the Lowest Common Ancestor (LCA) using Kotlin through a series of algorithmic problems. This problem is one of the important concepts dealing with tree structures and appears in various coding tests. This course will detail the problem definition, solution process, and optimization methods along &hellip; <a href=\"https:\/\/atmokpo.com\/w\/35134\/\" class=\"more-link\">\ub354 \ubcf4\uae30<span class=\"screen-reader-text\"> &#8220;Kotlin coding test course, finding the lowest common ancestor&#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-35134","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 lowest common ancestor - \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\/35134\/\" \/>\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 lowest common ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello! In this session, we will solve the problem of finding the Lowest Common Ancestor (LCA) using Kotlin through a series of algorithmic problems. This problem is one of the important concepts dealing with tree structures and appears in various coding tests. This course will detail the problem definition, solution process, and optimization methods along &hellip; \ub354 \ubcf4\uae30 &quot;Kotlin coding test course, finding the lowest common ancestor&quot;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/35134\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:35:56+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T12:41:12+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=\"4\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/35134\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35134\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"Kotlin coding test course, finding the lowest common ancestor\",\"datePublished\":\"2024-11-01T09:35:56+00:00\",\"dateModified\":\"2024-11-01T12:41:12+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35134\/\"},\"wordCount\":489,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Kotlin coding test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/35134\/\",\"url\":\"https:\/\/atmokpo.com\/w\/35134\/\",\"name\":\"Kotlin coding test course, finding the lowest common ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:35:56+00:00\",\"dateModified\":\"2024-11-01T12:41:12+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/35134\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/35134\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/35134\/#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 lowest common ancestor\"}]},{\"@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 lowest common ancestor - \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\/35134\/","og_locale":"ko_KR","og_type":"article","og_title":"Kotlin coding test course, finding the lowest common ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello! In this session, we will solve the problem of finding the Lowest Common Ancestor (LCA) using Kotlin through a series of algorithmic problems. This problem is one of the important concepts dealing with tree structures and appears in various coding tests. This course will detail the problem definition, solution process, and optimization methods along &hellip; \ub354 \ubcf4\uae30 \"Kotlin coding test course, finding the lowest common ancestor\"","og_url":"https:\/\/atmokpo.com\/w\/35134\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:35:56+00:00","article_modified_time":"2024-11-01T12:41:12+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":"4\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/35134\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/35134\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"Kotlin coding test course, finding the lowest common ancestor","datePublished":"2024-11-01T09:35:56+00:00","dateModified":"2024-11-01T12:41:12+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/35134\/"},"wordCount":489,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Kotlin coding test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/35134\/","url":"https:\/\/atmokpo.com\/w\/35134\/","name":"Kotlin coding test course, finding the lowest common ancestor - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:35:56+00:00","dateModified":"2024-11-01T12:41:12+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/35134\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/35134\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/35134\/#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 lowest common ancestor"}]},{"@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\/35134","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=35134"}],"version-history":[{"count":2,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35134\/revisions"}],"predecessor-version":[{"id":38075,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/35134\/revisions\/38075"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=35134"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=35134"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=35134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}