{"id":27738,"date":"2024-10-27T14:43:29","date_gmt":"2024-10-27T14:43:29","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27738"},"modified":"2024-11-26T07:15:44","modified_gmt":"2024-11-26T07:15:44","slug":"c-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%b5%9c%eb%8c%80-%ea%b3%b5%ec%95%bd%ec%88%98-%ea%b5%ac%ed%95%98%ea%b8%b0-2","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27738\/","title":{"rendered":"C++ \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ucd5c\ub300 \uacf5\uc57d\uc218 \uad6c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

1. \uc11c\ub860<\/h2>\n

\n \ud504\ub85c\uadf8\ub798\ubc0d \ub300\ud68c\ub098 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c \uc911 \ud558\ub098\ub294 \ub450 \uc218\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218(GCD, Greatest Common Divisor)\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \ucd5c\ub300 \uacf5\uc57d\uc218\ub294 \ub450 \uac1c\uc758 \uc790\uc5f0\uc218\uc5d0\uc11c \uacf5\ud1b5\uc73c\ub85c \ub098\ub204\uc5b4 \ub5a8\uc5b4\uc9c0\ub294 \uac00\uc7a5 \ud070 \uc218\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.
\n \uc774 \uae00\uc5d0\uc11c\ub294 C++\uc744 \uc0ac\uc6a9\ud558\uc5ec \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc744 \uc124\uba85\ud558\uace0, \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uacfc\uc815\uc744 \uc790\uc138\ud788 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n

2. \ubb38\uc81c \uc815\uc758<\/h2>\n

\n \ub450 \uac1c\uc758 \uc790\uc5f0\uc218 a\uc640 b\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \uc774 \ub450 \uc218\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624.
\n \uc785\ub825\uc73c\ub85c \ub450 \uac1c\uc758 \uc790\uc5f0\uc218 a, b (1 <= a, b <= 1,000,000)\uac00 \uc8fc\uc5b4\uc9c0\uba70, \uacb0\uacfc\ub85c \ucd5c\ub300 \uacf5\uc57d\uc218 \uac12\uc744 \ucd9c\ub825\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n

\uc608\uc81c \uc785\ub825<\/h3>\n


\n 48 18
\n <\/code><\/p>\n

\uc608\uc81c \ucd9c\ub825<\/h3>\n


\n 6
\n <\/code><\/p>\n

3. \uc54c\uace0\ub9ac\uc998 \uc124\uba85<\/h2>\n

\n \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \uad6c\ud558\ub294 \ubc29\ubc95\uc5d0\ub294 \uc5ec\ub7ec \uac00\uc9c0\uac00 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc5ec\uae30\uc11c\ub294 \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95(Euclidean algorithm)\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \ucd5c\ub300 \uacf5\uc57d\uc218\ub97c \ucc3e\ub294 \ubc29\ubc95\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4.
\n \uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uc6d0\ub9ac\ub97c \uae30\ubc18\uc73c\ub85c \ud569\ub2c8\ub2e4.\n <\/p>\n

\n \ub450 \uc218 a\uc640 b\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218 GCD(a, b)\ub294 GCD(b, a mod b)\uc640 \uac19\uc2b5\ub2c8\ub2e4.\n <\/p><\/blockquote>\n

\n \uc774 \uacfc\uc815\uc744 \ubc18\ubcf5\ud558\uc5ec b\uac00 0\uc774 \ub420 \ub54c\uae4c\uc9c0 \uacc4\uc18d\ud558\uba74, a\uac00 \ub450 \uc218\uc758 \ucd5c\ub300 \uacf5\uc57d\uc218\uac00 \ub429\ub2c8\ub2e4.
\n \uc989, GCD(a, 0) = a\uc774\ubbc0\ub85c \ub9c8\uc9c0\ub9c9 \ub0a8\uc740 \uc22b\uc790\uac00 \ucd5c\ub300 \uacf5\uc57d\uc218\uc785\ub2c8\ub2e4.\n <\/p>\n

\uc720\ud074\ub9ac\ub4dc \ud638\uc81c\ubc95\uc758 \uc758\uc0ac\ucf54\ub4dc<\/h3>\n
\n    function GCD(a, b):\n        while b \u2260 0:\n            temp := b\n            b := a mod b\n            a := temp\n        return a\n    <\/pre>\n
4. C++ \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n        \uc704\uc5d0\uc11c \uc124\uba85\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \uae30\ubc18\uc73c\ub85c C++\ub85c \ucd5c\ub300 \uacf5\uc57d\uc218(GCD)\ub97c \uad6c\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.
\n        \ub2e4\uc74c\uc740 \ud574\ub2f9 \ud504\ub85c\uadf8\ub7a8\uc758 \uc18c\uc2a4 \ucf54\ub4dc\uc785\ub2c8\ub2e4.\n    <\/p>\n
\n    #include <iostream>\n\n    using namespace std;\n\n    int gcd(int a, int b) {\n        while (b != 0) {\n            int temp = b;\n            b = a % b;\n            a = temp;\n        }\n        return a;\n    }\n\n    int main() {\n        int a, b;\n        cout << \"\ub450 \uac1c\uc758 \uc790\uc5f0\uc218\ub97c \uc785\ub825\ud558\uc138\uc694: \";\n        cin >> a >> b;\n\n        cout << \"\ucd5c\ub300 \uacf5\uc57d\uc218 (GCD): \" << gcd(a, b) << endl;\n\n        return 0;\n    }\n    <\/pre>\n
5. \ucf54\ub4dc \uc124\uba85<\/h2>\n
\n        \uc704 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ubc29\uc2dd\uc73c\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4:\n    <\/p>\n