{"id":34646,"date":"2024-11-01T09:30:26","date_gmt":"2024-11-01T09:30:26","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34646"},"modified":"2024-11-01T11:40:22","modified_gmt":"2024-11-01T11:40:22","slug":"javascript-coding-test-course-extended-euclidean-algorithm","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34646\/","title":{"rendered":"JavaScript Coding Test Course, Extended Euclidean Algorithm"},"content":{"rendered":"

Hello, everyone! Today, we will learn about one of the important algorithms in coding tests using JavaScript, the Extended Euclidean Algorithm. In this course, we will provide the concept of the Extended Euclidean Algorithm, the problem-solving process using it, and practical code examples.<\/p>\n

1. Problem Description<\/h2>\n

We will define the problem as follows. Given two integers A and B, the task is to find integers X and Y that satisfy AX + BY = GCD(A, B). Here, GCD refers to the greatest common divisor.<\/p>\n

Example<\/h3>\n

Input: A = 30, B = 21<\/p>\n

Output: X = 1, Y = -1, GCD = 3<\/p>\n

Solution: 30 * 1 + 21 * (-1) = 3<\/p>\n

2. Concept Explanation<\/h2>\n

The Extended Euclidean Algorithm not only calculates the greatest common divisor (GCD) of two integers but also finds specific coefficients from it. This is primarily used in the following formula:<\/p>\n

AX + BY = GCD(A, B)<\/p>\n

Here, A and B are the given two integers, and X and Y are the integers we want to find. If the GCD is 1, A and B are coprime, and X and Y can also be used to find modular inverses.<\/p>\n

3. Approach<\/h2>\n

We will implement the Extended Euclidean Algorithm based on the general Euclidean algorithm for finding GCD. The main idea of the algorithm is as follows:<\/p>\n

    \n
  1. Receive two integers A and B as input.<\/li>\n
  2. If B is 0, then the GCD is A, and X is 1, Y is 0.<\/li>\n
  3. Otherwise, recursively call with B and A % B using the Euclidean algorithm.<\/li>\n
  4. Use the results of the recursive call to calculate the values of X and Y.<\/li>\n<\/ol>\n

    4. Algorithm Implementation<\/h2>\n

    Below is an example of implementing the Extended Euclidean Algorithm in JavaScript:<\/p>\n

    \nfunction extendedGCD(a, b) {\n    if (b === 0) { \/\/ Base case\n        return { gcd: a, x: 1, y: 0 };\n    }\n    \/\/ Recur with the new parameters b and a % b\n    const { gcd, x: x1, y: y1 } = extendedGCD(b, a % b);\n    const x = y1;\n    const y = x1 - Math.floor(a \/ b) * y1;\n    return { gcd, x, y };\n}\n\n\/\/ Test the function with example values\nconst a = 30;\nconst b = 21;\nconst { gcd, x, y } = extendedGCD(a, b);\nconsole.log(`GCD: ${gcd}, X: ${x}, Y: ${y}`);\n<\/code><\/pre>\n
    5. Code Explanation<\/h3>\n
    In the above code, we are recursively calculating the GCD. In the base case, when B is 0, the GCD is A, and at that point, X is 1, Y is 0. After that, we calculate new values for X and Y using the returned X and Y values to ultimately get the result we desire.<\/p>\n
    6. Test Cases<\/h2>\n
    Now let’s test the function with various test cases.<\/p>\n
    \n\/\/ Test cases\nconst testCases = [\n    { a: 30, b: 21 },\n    { a: 48, b: 18 },\n    { a: 56, b: 15 },\n    { a: 101, b: 10 },\n];\n\ntestCases.forEach(({ a, b }) => {\n    const { gcd, x, y } = extendedGCD(a, b);\n    console.log(`A: ${a}, B: ${b} => GCD: ${gcd}, X: ${x}, Y: ${y}`);\n});\n<\/code><\/pre>\n
    7. Conclusion<\/h2>\n
    Today, we learned about the Extended Euclidean Algorithm. This algorithm is very useful for finding the greatest common divisor of two integers and for finding specific coefficients related to it. It is especially used in modular arithmetic and complex algorithm problems, so it is important to understand and practice it thoroughly.<\/p>\n
    I hope the algorithm used in this article will help you in your coding exam preparations. If you have any additional questions, please leave them in the comments!<\/p>\n","protected":false},"excerpt":{"rendered":"
    Hello, everyone! Today, we will learn about one of the important algorithms in coding tests using JavaScript, the Extended Euclidean Algorithm. In this course, we will provide the concept of the Extended Euclidean Algorithm, the problem-solving process using it, and practical code examples. 1. Problem Description We will define the problem as follows. Given two … \ub354 \ubcf4\uae30 “JavaScript Coding Test Course, Extended Euclidean Algorithm”<\/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-34646","post","type-post","status-publish","format-standard","hentry","category-javascript-coding-test"],"yoast_head":"\nJavaScript Coding Test Course, Extended Euclidean Algorithm - \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\/34646\/\" \/>\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, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"og:description\" content=\"Hello, everyone! Today, we will learn about one of the important algorithms in coding tests using JavaScript, the Extended Euclidean Algorithm. In this course, we will provide the concept of the Extended Euclidean Algorithm, the problem-solving process using it, and practical code examples. 1. Problem Description We will define the problem as follows. Given two … \ub354 \ubcf4\uae30 "JavaScript Coding Test Course, Extended Euclidean Algorithm"\" \/>\n<meta property=\"og:url\" content=\"https:\/\/atmokpo.com\/w\/34646\/\" \/>\n<meta property=\"og:site_name\" content=\"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\" \/>\n<meta property=\"article:published_time\" content=\"2024-11-01T09:30:26+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-11-01T11:40: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=\"3\ubd84\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/atmokpo.com\/w\/34646\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34646\/\"},\"author\":{\"name\":\"root\",\"@id\":\"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7\"},\"headline\":\"JavaScript Coding Test Course, Extended Euclidean Algorithm\",\"datePublished\":\"2024-11-01T09:30:26+00:00\",\"dateModified\":\"2024-11-01T11:40:22+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34646\/\"},\"wordCount\":413,\"publisher\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#organization\"},\"articleSection\":[\"Javascript Coding Test\"],\"inLanguage\":\"ko-KR\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/atmokpo.com\/w\/34646\/\",\"url\":\"https:\/\/atmokpo.com\/w\/34646\/\",\"name\":\"JavaScript Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8\",\"isPartOf\":{\"@id\":\"https:\/\/atmokpo.com\/w\/#website\"},\"datePublished\":\"2024-11-01T09:30:26+00:00\",\"dateModified\":\"2024-11-01T11:40:22+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/atmokpo.com\/w\/34646\/#breadcrumb\"},\"inLanguage\":\"ko-KR\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/atmokpo.com\/w\/34646\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/atmokpo.com\/w\/34646\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\ud648\",\"item\":\"https:\/\/atmokpo.com\/w\/en\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"JavaScript Coding Test Course, Extended Euclidean Algorithm\"}]},{\"@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, Extended Euclidean Algorithm - \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\/34646\/","og_locale":"ko_KR","og_type":"article","og_title":"JavaScript Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","og_description":"Hello, everyone! Today, we will learn about one of the important algorithms in coding tests using JavaScript, the Extended Euclidean Algorithm. In this course, we will provide the concept of the Extended Euclidean Algorithm, the problem-solving process using it, and practical code examples. 1. Problem Description We will define the problem as follows. Given two … \ub354 \ubcf4\uae30 \"JavaScript Coding Test Course, Extended Euclidean Algorithm\"","og_url":"https:\/\/atmokpo.com\/w\/34646\/","og_site_name":"\ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","article_published_time":"2024-11-01T09:30:26+00:00","article_modified_time":"2024-11-01T11:40: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":"3\ubd84"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/atmokpo.com\/w\/34646\/#article","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/34646\/"},"author":{"name":"root","@id":"https:\/\/atmokpo.com\/w\/#\/schema\/person\/91b6b3b138fbba0efb4ae64b1abd81d7"},"headline":"JavaScript Coding Test Course, Extended Euclidean Algorithm","datePublished":"2024-11-01T09:30:26+00:00","dateModified":"2024-11-01T11:40:22+00:00","mainEntityOfPage":{"@id":"https:\/\/atmokpo.com\/w\/34646\/"},"wordCount":413,"publisher":{"@id":"https:\/\/atmokpo.com\/w\/#organization"},"articleSection":["Javascript Coding Test"],"inLanguage":"ko-KR"},{"@type":"WebPage","@id":"https:\/\/atmokpo.com\/w\/34646\/","url":"https:\/\/atmokpo.com\/w\/34646\/","name":"JavaScript Coding Test Course, Extended Euclidean Algorithm - \ub77c\uc774\ube0c\uc2a4\ub9c8\ud2b8","isPartOf":{"@id":"https:\/\/atmokpo.com\/w\/#website"},"datePublished":"2024-11-01T09:30:26+00:00","dateModified":"2024-11-01T11:40:22+00:00","breadcrumb":{"@id":"https:\/\/atmokpo.com\/w\/34646\/#breadcrumb"},"inLanguage":"ko-KR","potentialAction":[{"@type":"ReadAction","target":["https:\/\/atmokpo.com\/w\/34646\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/atmokpo.com\/w\/34646\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\ud648","item":"https:\/\/atmokpo.com\/w\/en\/"},{"@type":"ListItem","position":2,"name":"JavaScript Coding Test Course, Extended Euclidean Algorithm"}]},{"@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\/34646","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=34646"}],"version-history":[{"count":1,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34646\/revisions"}],"predecessor-version":[{"id":34647,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/posts\/34646\/revisions\/34647"}],"wp:attachment":[{"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/media?parent=34646"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/categories?post=34646"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/atmokpo.com\/w\/wp-json\/wp\/v2\/tags?post=34646"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}