\uc548\ub155\ud558\uc138\uc694! \uc774 \uae00\uc5d0\uc11c\ub294 \ucf54\ud2c0\ub9b0\uc744 \uc0ac\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud574\uacb0 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4. \ud2b9\ud788 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc5d0 \ub300\ud574 \uc790\uc138\ud788 \uc124\uba85\ud558\uace0, \uc774\ub97c \uc774\uc6a9\ud55c \ud2b9\uc815 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4. \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc740 \ub450 \uc218\uc758 \ucd5c\ub300\uacf5\uc57d\uc218\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c, \ub9ce\uc740 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \ud65c\uc6a9\ub429\ub2c8\ub2e4.<\/p>\n
\uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc740 \uace0\ub300 \uadf8\ub9ac\uc2a4\uc758 \uc218\ud559\uc790 \uc720\ud074\ub9ac\ub4dc\uac00 \uc81c\uc548\ud55c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c, \ub450 \uc815\uc218\uc758 \ucd5c\ub300\uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubc29\ubc95\uc785\ub2c8\ub2e4. \ub450 \uc815\uc218 a\uc640 b\uc5d0 \ub300\ud574 \ucd5c\ub300\uacf5\uc57d\uc218 GCD\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc815\uc758\ub429\ub2c8\ub2e4:<\/p>\n
GCD(a, b) = GCD(b, a % b) \uc774\uace0, GCD(a, 0) = a\uc785\ub2c8\ub2e4.<\/p>\n
\uc989, a\ub97c b\ub85c \ub098\ub208 \ub098\uba38\uc9c0\uac00 0\uc774 \ub420 \ub54c\uae4c\uc9c0 \ub450 \uac1c\uc758 \uc815\uc218 A\uc640 B\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \uc774 \ub450 \uc218\uc758 \ucd5c\ub300\uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ucf54\ub4dc\ub97c \uc791\uc131\ud558\uc2dc\uc624.<\/p>\n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574, \ub450 \uc785\ub825 \uac12 A\uc640 B\uc758 \ucd5c\ub300\uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubc29\ubc95\uc744 \uc774\ud574\ud574\uc57c \ud569\ub2c8\ub2e4. \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec \uac04\ub2e8\ud558\uac8c GCD\ub97c \uad6c\ud560 \uc218 \uc788\uc73c\ubbc0\ub85c, \uc774 \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc774 \ubb38\uc81c\uc5d0\uc11c \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \ud65c\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uc808\ucc28\ub85c \uc9c4\ud589\ub429\ub2c8\ub2e4:<\/p>\n \uc785\ub825 \uc608\uc2dc: \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(log(min(A, B)))\ub85c \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4. \ub530\ub77c\uc11c \uc785\ub825 \uac12\uc774 \ucee4\uc838\ub3c4 \ucda9\ubd84\ud788 \ube60\ub978 \ucc98\ub9ac \uc18d\ub3c4\ub97c \uc720\uc9c0\ud569\ub2c8\ub2e4.<\/p>\n \uc774\ubc88 \ud3ec\uc2a4\ud305\uc5d0\uc11c\ub294 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \ud65c\uc6a9\ud55c \ucd5c\ub300\uacf5\uc57d\uc218 \uad6c\ud558\uae30 \ubb38\uc81c\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \ucf54\ud2c0\ub9b0\uc73c\ub85c \uac04\ub2e8\ud558\uac8c \uad6c\ud604\ud560 \uc218 \uc788\uc73c\uba70, \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc591\ud55c \ubb38\uc81c\uc5d0 \ud65c\uc6a9\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \ub54c \uc774\ub7ec\ud55c \uae30\ubc95\uc744 \uc774\ud574\ud558\uace0 \uc801\uc6a9\ud558\ub294 \uac83\uc740 \ub9e4\uc6b0 \uc911\uc694\ud569\ub2c8\ub2e4. \ub2e4\uc74c \ud3ec\uc2a4\ud305\uc5d0\uc11c\ub294 \ub354\uc6b1 \ubcf5\uc7a1\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0 \ub300\ud574 \ub2e4\ub8e8\uc5b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95 \uc774\uc678\uc5d0\ub3c4 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uc774 \uc874\uc7ac\ud558\uba70, \uc774\ub97c \ud1b5\ud574 \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \ud0a4\uc6cc\ub098\uac08 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ucf54\ub4dc \uc791\uc131\uacfc \ud568\uaed8 \uc54c\uace0\ub9ac\uc998 \uc0ac\uace0 \ubc29\uc2dd\uc744 \uac1c\ubc1c\ud558\ub294 \uac83\uc774 \uc911\uc694\ud558\uba70, \uc9c0\uc18d\uc801\uc778 \uc5f0\uc2b5\uacfc \uad6c\ud604\uc774 \ud544\uc694\ud569\ub2c8\ub2e4. \ud1b5\ud569\uc801\uc73c\ub85c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0 \ub300\ud55c \ud1b5\ucc30\ub825\uc744 \ub192\uc774\uace0, \ub098\ub9cc\uc758 \ucf54\ub529 \uc2a4\ud0c0\uc77c\uc744 \ubc1c\uc804\uc2dc\ucf1c \ub098\uac00\uae38 \ubc14\ub78d\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n<\/div>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n a<\/strong>\ub97c b<\/strong>\ub85c, b<\/strong>\ub97c a % b<\/strong>\ub85c \uad50\ud658\ud558\ub294 \uacfc\uc815\uc744 \ubc18\ubcf5\ud569\ub2c8\ub2e4. \uc774\ub807\uac8c \ud558\uba74 \ucd5c\uc885\uc801\uc73c\ub85c b\uc758 \uac12\uc774 GCD\uac00 \ub429\ub2c8\ub2e4.<\/p>\n2. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c<\/h2>\n
\ubb38\uc81c \uc124\uba85<\/h3>\n
\uc785\ub825<\/h4>\n
\n
\ucd9c\ub825<\/h4>\n
\n
3. \ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
3.1 \ubb38\uc81c \ubd84\uc11d<\/h3>\n
3.2 \uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h3>\n
\n
3.3 \ucf54\ud2c0\ub9b0 \ucf54\ub4dc<\/h3>\n
fun gcd(a: Int, b: Int): Int {\n var x = a\n var y = b\n while (y != 0) {\n val temp = y\n y = x % y\n x = temp\n }\n return x\n }\n\n fun main() {\n val input = readLine()!!\n val parts = input.split(\" \")\n val A = parts[0].toInt()\n val B = parts[1].toInt()\n println(gcd(A, B))\n }<\/code><\/pre>\n3.4 \ucf54\ub4dc \uc2e4\ud589<\/h3>\n
\n 48 18<\/code>
\n \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc740 \ucd9c\ub825\uc774 \ub098\ud0c0\ub0a9\ub2c8\ub2e4:<\/p>\n6<\/code><\/pre>\n4. \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
5. \uacb0\ub860<\/h2>\n
\ub9c8\uce58\uba70<\/h3>\n