\uc548\ub155\ud558\uc138\uc694! \uc624\ub298\uc740 \ucde8\uc5c5 \uc900\ube44\ud558\ub294 \uac1c\ubc1c\uc790 \uc5ec\ub7ec\ubd84\uc744 \uc704\ud574 \uc2a4\uc704\ud504\ud2b8\ub97c \ud65c\uc6a9\ud55c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c\ub97c \uc9c4\ud589\ud558\uaca0\uc2b5\ub2c8\ub2e4. \uc774\ubc88 \uc8fc\uc81c\ub294 \ubc14\ub85c \ucd5c\ub300 \uacf5\uc57d\uc218(Greatest Common Divisor, GCD)<\/strong>\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ucd5c\ub300 \uacf5\uc57d\uc218\ub294 \ub450 \uc22b\uc790\uac00 \uac00\uc9c0\uace0 \uc788\ub294 \uacf5\ud1b5\uc801\uc778 \uc57d\uc218 \uc911 \uac00\uc7a5 \ud070 \uc218\ub85c, \uc218\ud559\uc801 \uac1c\ub150 \uc678\uc5d0\ub3c4 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \ud65c\uc6a9\ub429\ub2c8\ub2e4.<\/p>\n \uc8fc\uc5b4\uc9c4 \ub450 \uc815\uc218 \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubc29\uc2dd\uc740 \uc5ec\ub7ec \uac00\uc9c0\uac00 \uc788\uc9c0\ub9cc, \uac00\uc7a5 \uc77c\ubc18\uc801\uc73c\ub85c \uc0ac\uc6a9\ud558\ub294 \ubc29\ubc95\uc740 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95(Euclidean Algorithm)\uc785\ub2c8\ub2e4. \uc774 \uc54c\uace0\ub9ac\uc998\uc740 \ub2e4\uc74c\uc758 \ub450 \uac00\uc9c0 \uac04\ub2e8\ud55c \uc0ac\uc2e4\uc5d0 \uae30\ubc18\ud569\ub2c8\ub2e4:<\/p>\n \uc704\uc758 \ub450 \uc6d0\ub9ac\ub97c \ubc14\ud0d5\uc73c\ub85c \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \uc801\uc6a9\ud558\uc5ec \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubc29\ubc95\uc744 \ub2e8\uacc4\ubcc4\ub85c \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n \uba3c\uc800, \ub450 \uc815\uc218\ub97c \uc785\ub825\ubc1b\uc544 \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \ubc18\ud658\ud558\ub294 \ud568\uc218\ub97c \uc815\uc758\ud569\ub2c8\ub2e4. \ud568\uc218\uc758 \uc2dc\uadf8\ub2c8\ucc98\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \ud568\uc218 \ub0b4\ubd80\uc5d0\uc11c \uc785\ub825\ubc1b\uc740 \ub450 \uac12\uc774 \ubaa8\ub450 0\uc778\uc9c0 \uccb4\ud06c\ud569\ub2c8\ub2e4. \uc774 \uacbd\uc6b0, \uc6b0\ub9ac\ub294 ‘\uc815\uc758\ub418\uc9c0 \uc54a\uc74c’ \uba54\uc2dc\uc9c0\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4:<\/p>\n \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \ubc18\ubcf5\uc801\uc73c\ub85c \uacc4\uc0b0\ud569\ub2c8\ub2e4. \uc774 \uacfc\uc815\uc5d0\uc11c\ub294 \ub450 \uc22b\uc790\ub97c \uc11c\ub85c \ubc14\uafb8\uba74\uc11c \ub098\uba38\uc9c0\ub97c \uc0ac\uc6a9\ud558\uc5ec \uac12\uc744 \uc5c5\ub370\uc774\ud2b8 \ud569\ub2c8\ub2e4:<\/p>\n \uc704\uc758 \ub2e8\uacc4\ub4e4\uc744 \ubaa8\ub450 \ud1b5\ud569\ud558\uba74 \ucd5c\uc885\uc801\uc778 \ucd5c\ub300 \uacf5\uc57d\uc218 \ud568\uc218\ub97c \uc644\uc131\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n \uc774\uc81c \uc6b0\ub9ac\uac00 \uc791\uc131\ud55c \ucd5c\ub300 \uacf5\uc57d\uc218 \ud568\uc218\ub97c \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub85c \uac80\uc99d\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc544\ub798\ub294 \uba87 \uac00\uc9c0 \uc608\uc2dc \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\uc785\ub2c8\ub2e4:<\/p>\n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc2a4\uc704\ud504\ud2b8\ub85c \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \ub2e4\ub918\uc2b5\ub2c8\ub2e4. \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc758 \uc6d0\ub9ac\uc5d0 \ub530\ub77c \uac04\uacb0\ud558\uace0 \ud6a8\uc728\uc801\uc778 \ucf54\ub4dc\ub97c \uc791\uc131\ud560 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4. \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub294 \uc218\ud559\uc801 \uc6d0\ub9ac\ub97c \uc774\ud574\ud558\uace0 \uc774\ub97c \ud504\ub85c\uadf8\ub798\ubc0d\uc73c\ub85c \uad6c\ud604\ud558\ub294 \uc5f0\uc2b5\uc744 \ud1b5\ud574 \ub354\uc6b1 \ubc1c\uc804\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc55e\uc73c\ub85c\ub3c4 \uc9c0\uc18d\uc801\uc73c\ub85c \ub2e4\uc591\ud55c \uc8fc\uc81c\ub85c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c\ub97c \uc9c4\ud589\ud560 \uc608\uc815\uc774\ub2c8 \ub9ce\uc740 \uad00\uc2ec \ubd80\ud0c1\ub4dc\ub9bd\ub2c8\ub2e4!<\/p>\n\ubb38\uc81c \uc124\uba85<\/h2>\n
a<\/code>\uc640 b<\/code>\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ud568\uc218\ub97c \uc2a4\uc704\ud504\ud2b8\ub85c \uc791\uc131\ud558\uc138\uc694. \ub610\ud55c, \ub450 \uc22b\uc790\uac00 \ubaa8\ub450 0\uc77c \uacbd\uc6b0\uc5d0\ub294 ‘\uc815\uc758\ub418\uc9c0 \uc54a\uc74c’\uc774\ub77c\ub294 \uba54\uc2dc\uc9c0\ub97c \ucd9c\ub825\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\nfunc gcd(_ a: Int, _ b: Int) -> String<\/code><\/pre>\n\ubb38\uc81c \ud574\uacb0 \uc811\uadfc \ubc29\uc2dd<\/h2>\n
\n
a<\/code>\uc640 b<\/code>\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\ub294 gcd(a, 0) = |a|<\/code>\uc785\ub2c8\ub2e4.<\/li>\na<\/code>\uc640 b<\/code>\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\ub294 gcd(a, b) = gcd(b, a % b)<\/code>\uc785\ub2c8\ub2e4.<\/li>\n<\/ul>\n\uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc758 \uad6c\ud604<\/h3>\n
1\ub2e8\uacc4: \ud568\uc218 \uc815\uc758<\/h4>\n
func gcd(_ a: Int, _ b: Int) -> String<\/code><\/pre>\n2\ub2e8\uacc4: \uc785\ub825 \uac80\uc99d<\/h4>\n
if a == 0 && b == 0 {\n return \"\uc815\uc758\ub418\uc9c0 \uc54a\uc74c\"\n }<\/code><\/pre>\n3\ub2e8\uacc4: \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h4>\n
var a = abs(a)\n var b = abs(b)\n\n while b != 0 {\n let temp = b\n b = a % b\n a = temp\n }\n return String(a)<\/code><\/pre>\n4\ub2e8\uacc4: \uc804\uccb4 \ucf54\ub4dc \uc644\uc131<\/h4>\n
func gcd(_ a: Int, _ b: Int) -> String {\n if a == 0 && b == 0 {\n return \"\uc815\uc758\ub418\uc9c0 \uc54a\uc74c\"\n }\n var a = abs(a)\n var b = abs(b)\n\n while b != 0 {\n let temp = b\n b = a % b\n a = temp\n }\n return String(a)\n }<\/code><\/pre>\n\ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4<\/h2>\n
print(gcd(48, 18)) \/\/ \ucd9c\ub825: 6\nprint(gcd(0, 0)) \/\/ \ucd9c\ub825: \uc815\uc758\ub418\uc9c0 \uc54a\uc74c\nprint(gcd(56, 98)) \/\/ \ucd9c\ub825: 14<\/code><\/pre>\n\uacb0\ub860<\/h2>\n