\uc548\ub155\ud558\uc138\uc694! \uc624\ub298\uc740 \ucf54\ub529\ud14c\uc2a4\ud2b8\ub97c \uc900\ube44\ud558\ub294 \uc5ec\ub7ec\ubd84\uc744 \uc704\ud574 “\ucd5c\ub300 \uacf5\uc57d\uc218”\ub97c \uad6c\ud558\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ub2e4\ub904\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uc801\uc808\ud558\uac8c \uacc4\uc0b0\ud558\ub294 \uac83\uc740 \uc5ec\ub7ec \ubb38\uc81c\uc5d0\uc11c \ud544\uc218\uc801\uc73c\ub85c \ud544\uc694\ud558\uba70, \ud2b9\ud788 \uc218\ud559\uc801 \uc0ac\uace0\uc640 \uc54c\uace0\ub9ac\uc998\uc801 \uc0ac\uace0\ub97c \ub3d9\uc2dc\uc5d0 \uc694\uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc774\ubc88 \uc2dc\uac04\uc5d0\ub294 \ud568\uc218\ud615 \ud504\ub85c\uadf8\ub798\ubc0d \uae30\ubc95\uc744 \uc0ac\uc6a9\ud560 \uac83\uc774\uba70, Python \uc5b8\uc5b4\ub97c \uc774\uc6a9\ud574 \uc2e4\uc2b5\ud560 \uac83\uc785\ub2c8\ub2e4.<\/p>\n
\ub450 \uac1c\uc758 \uc815\uc218 \ub2e4\uc74c\uc740 \uba87 \uac00\uc9c0 \uc608\uc81c\uc785\ub2c8\ub2e4:<\/p>\n \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubc29\ubc95 \uc911 \uac00\uc7a5 \uc720\uba85\ud55c \ubc29\ubc95\uc740 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc785\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uc6d0\ub9ac\uc5d0 \uae30\ubc18\ud569\ub2c8\ub2e4:<\/p>\n \uc774\uc81c \uc774\uc81c \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \ud30c\uc774\uc36c \ucf54\ub4dc\ub85c \uad6c\ud604\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc544\ub798 \ucf54\ub4dc\ub294 \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uacc4\uc0b0\ud558\ub294 \ud568\uc218\ub97c \uc815\uc758\ud55c \uc608\uc2dc\uc785\ub2c8\ub2e4:<\/p>\n \uc774 \ud568\uc218\ub294 \ubc18\ubcf5\ubb38\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc785\ub825\uc744 \ubc1b\uc544 \uc2e4\ud589\ud558\ub294 \uba54\uc778 \ucf54\ub4dc\ub97c \uc791\uc131\ud558\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n \uc774\ubc88 \uae00\uc5d0\uc11c\ub294 \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc758 \uc6d0\ub9ac\ub97c \ubc30\uc6b0\uace0, \uc2e4\uc81c\ub85c \ud30c\uc774\uc36c\uc73c\ub85c \uad6c\ud604\ud574\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \ub2e4\uc591\ud55c \uc751\uc6a9\uc774 \uac00\ub2a5\ud558\uba70, \ub2e4\ub978 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud480 \ub54c\ub3c4 \uac19\uc740 \uc6d0\ub9ac\ub97c \uc801\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc5d0\uc11c \uc218\ud559\uacfc \ud504\ub85c\uadf8\ub798\ubc0d\uc758 \uc870\ud654\ub97c \uacbd\ud5d8\ud574 \ubcf4\uc2dc\uae38 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n \uaf2d \ub9c8\ubb34\ub9ac\ub85c \ub9d0\uc500\ub4dc\ub9ac\uace0 \uc2f6\uc740 \uc810\uc740!<\/strong><\/p>\n \ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44\uc758 \uae30\ubcf8\uc740 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ub9ce\uc774 \ud480\uc5b4\ubcf4\ub294 \uac83\uc785\ub2c8\ub2e4. \ub9ce\uc740 \ubb38\uc81c\ub4e4\uc744 \ud480\uc5b4\ubcf4\uc2dc\uace0, \ubcf5\uc2b5\ud558\uc2dc\ub294 \uacfc\uc815\uc744 \ud1b5\ud574 \ucf54\ub529 \uc2e4\ub825\uc744 \ud55c\uce35 \ub354 \ubc1c\uc804\uc2dc\ud0ac \uc218 \uc788\uc744 \uac83\uc785\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"a<\/code>, b<\/code>\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \uc774 \ub450 \uc218\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud574 \uc8fc\uc138\uc694. \ucd5c\ub300 \uacf5\uc57d\uc218(Greatest Common Divisor, GCD)\ub294 \ub450 \uc815\uc218\uc758 \uacf5\ud1b5\ub41c \uc57d\uc218 \uc911\uc5d0\uc11c \uac00\uc7a5 \ud070 \uc218\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.<\/p>\n\uc785\ub825<\/h3>\n
\n
a<\/code>, b<\/code> (1 \u2264 a<\/code>, b<\/code> \u2264 109<\/sup>)\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
\n
GCD(a, b)<\/code>\ub97c \ucd9c\ub825\ud55c\ub2e4.<\/li>\n<\/ul>\n\uc608\uc81c<\/h2>\n
\n\uc608\uc81c 1:\n\uc785\ub825: 60 48\n\ucd9c\ub825: 12\n\n\uc608\uc81c 2:\n\uc785\ub825: 101 10\n\ucd9c\ub825: 1\n\n\uc608\uc81c 3:\n\uc785\ub825: 17 17\n\ucd9c\ub825: 17\n<\/pre>\n
\ubb38\uc81c \ud574\uacb0 \ubc29\ubc95<\/h2>\n
\n
a<\/code>\uc640 b<\/code>\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\ub294 b<\/code>\uc640 a<\/code>\ub97c b<\/code>\ub85c \ub098\ub208 \ub098\uba38\uc9c0 r<\/code>\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\uc640 \uac19\ub2e4. \uc989, GCD(a, b) = GCD(b, r)<\/code>\uc774\ub2e4.<\/li>\nr<\/code>\uac00 0\uc774 \ub420 \ub54c\uae4c\uc9c0 \uc9c4\ud589\ud558\uba74, \ub9c8\uc9c0\ub9c9\uc5d0 \ub0a8\uc740 b<\/code>\uac00 \ucd5c\ub300 \uacf5\uc57d\uc218\uc774\ub2e4.<\/li>\n<\/ul>\n\uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95 \uad6c\ud604<\/h2>\n
def gcd(a, b):\n while b != 0:\n a, b = b, a % b\n return a\n<\/code><\/pre>\nb<\/code>\uac00 0\uc774 \ub420 \ub54c\uae4c\uc9c0 \uacc4\uc18d\ud574\uc11c \ub450 \uc218\uc758 \uac12\uc744 \uad50\uccb4\ud558\uba70 \ub098\uba38\uc9c0\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4. \ucd5c\uc885\uc801\uc73c\ub85c \ub0a8\ub294 a<\/code>\uac00 \ucd5c\ub300 \uacf5\uc57d\uc218\uac00 \ub429\ub2c8\ub2e4.<\/p>\n\ucf54\ub4dc \uc2e4\ud589 \uc608<\/h2>\n
if __name__ == \"__main__\":\n a, b = map(int, input(\"\ub450 \uc218\ub97c \uc785\ub825\ud558\uc138\uc694: \").split())\n result = gcd(a, b)\n print(f\"\ucd5c\ub300 \uacf5\uc57d\uc218: {result}\")\n<\/code><\/pre>\n\uacb0\ub860<\/h2>\n