\uc5bc\ub9c8 \uc804 \ud55c \uc0dd\ubb3c\ud559\uc790\uac00 DNA \uc2dc\ud000\uc2a4\ub97c \ud1b5\ud574 \ud2b9\uc815 \ube44\ubc00\ubc88\ud638\ub97c \ub9cc\ub4e4\uc5b4\uc57c \ud558\ub294 \uc0c1\ud669\uc5d0 \ucc98\ud588\uc2b5\ub2c8\ub2e4. \uc774 DNA \uc2dc\ud000\uc2a4\ub294 A, C, G, T\uc758 4\uc885\ub958\uc758 \ub274\ud074\ub808\uc624\ud0c0\uc774\ub4dc\ub85c \uad6c\uc131\ub429\ub2c8\ub2e4. \uc774 \ube44\ubc00\ubc88\ud638\ub294 \uc8fc\uc5b4\uc9c4 DNA \uc2dc\ud000\uc2a4 \ub0b4\uc5d0\uc11c \uc120\ud0dd\ub41c A, C, G, T\uc758 \uc870\ud569\uc73c\ub85c \ub9cc\ub4e4\uc5b4\uc9d1\ub2c8\ub2e4.<\/p>\n
\uc8fc\uc5b4\uc9c4 \ubb38\uc790\uc5f4 S\uc5d0\uc11c \uae38\uc774\uac00 K\uc778 \ubaa8\ub4e0 \ubd80\ubd84 \ubb38\uc790\uc5f4 \uc911\uc5d0\uc11c \uac01 \ub274\ud074\ub808\uc624\ud0c0\uc774\ub4dc\uc758 \ube48\ub3c4\uac00 \ucd5c\uc18c\uc778 \ubd80\ubd84 \ubb38\uc790\uc5f4\uc744 \ucc3e\uace0, \uadf8 \uc911\uc5d0\uc11c \ube44\ubc00\ubc88\ud638\uc758 \uac1c\uc218\ub97c \uc54c\uc544\ub0b4\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624. \ub9cc\uc57d \ubaa8\ub4e0 \ube48\ub3c4\uac00 \uac19\ub2e4\uba74 \uadf8 \ube48\ub3c4\uac00 \ucd5c\uc18c\uc778 \ubd80\ubd84 \ubb38\uc790\uc5f4 \uc911 \uac00\uc7a5 \uc791\uc740 \uc0ac\uc804 \uc21c\uc11c\uc758 \ubb38\uc790\uc5f4\uc744 \uc120\ud0dd\ud569\ub2c8\ub2e4. \ubb38\uc790\uc5f4\uc758 \uae38\uc774\ub294 \uc8fc\uc5b4\uc9c4 \ubb38\uc790\uc5f4\ubcf4\ub2e4 \uc791\uac70\ub098 \uac19\uc544\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\uc720\ud6a8\ud55c \ube44\ubc00\ubc88\ud638\uc758 \uac1c\uc218\uc640 \uadf8 \uc911 \uac00\uc7a5 \uc791\uc740 \uc0ac\uc804 \uc21c\uc11c\uc758 \ube44\ubc00\ubc88\ud638\ub97c \ucd9c\ub825\ud558\uc2dc\uc624.<\/p>\n
\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc6b0\ub9ac\ub294 \uc2ac\ub77c\uc774\ub529 \uc708\ub3c4\uc6b0(Sliding Window) \uae30\ubc95\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. \uc774 \uae30\ubc95\uc740 \ud2b9\uc815 \uae38\uc774 K\uc758 \ubd80\ubd84 \ubb38\uc790\uc5f4\uc744 \uc774\ub3d9\ud558\uba74\uc11c \uac01 \ubb38\uc790(A, C, G, T)\uc758 \ube48\ub3c4\ub97c \uce74\uc6b4\ud2b8\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uac8c \ud574\uc90d\ub2c8\ub2e4.<\/p>\n
\uc544\ub798\ub294 \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c C++ \ucf54\ub4dc \uc608\uc81c\uc785\ub2c8\ub2e4:<\/p>\n
\n #include <iostream>\n #include <string>\n #include <unordered_map>\n #include <vector>\n #include <algorithm>\n\n using namespace std;\n\n int main() {\n int N, K;\n string S;\n cin >> N >> K;\n cin >> S;\n\n unordered_map freq;\n for (int i = 0; i < K; i++) {\n freq[S[i]]++;\n }\n\n \/\/ \ucd08\uae30 \uacb0\uacfc \uc124\uc815\n int min_freq = INT_MAX;\n vector passwords;\n\n \/\/ \uc2ac\ub77c\uc774\ub529 \uc708\ub3c4\uc6b0 \ud558\uc5ec \ubaa8\ub4e0 K \uae38\uc774 \ubd80\ubd84 \ubb38\uc790\uc5f4 \uac80\uc0ac\n for (int i = 0; i <= N - K; i++) {\n if (i > 0) {\n freq[S[i - 1]]--;\n freq[S[i + K - 1]]++;\n }\n\n \/\/ \uac00\uc7a5 \uc791\uc740 \ube48\ub3c4 \ucc3e\uae30\n int cur_min = INT_MAX;\n for (const auto &entry : freq) {\n cur_min = min(cur_min, entry.second);\n }\n\n \/\/ \uc720\ud6a8\ud55c \ube44\ubc00\ubc88\ud638 \ucd94\uac00\n if (cur_min <= (K \/ 4)) { \/\/ \ubaa8\ub4e0 \ub274\ud074\ub808\uc624\ud0c0\uc774\ub4dc\uc758 \ube48\ub3c4\uac00 K\/4 \uc774\ud558\n passwords.push_back(S.substr(i, K));\n }\n }\n\n \/\/ \uac00\uc7a5 \uc791\uc740 \uc0ac\uc804 \uc21c\uc758 \ube44\ubc00\ubc88\ud638 \ucc3e\uae30\n sort(passwords.begin(), passwords.end());\n string smallest_password = (passwords.empty() ? \"\" : passwords[0]);\n \n \/\/ \uacb0\uacfc \ucd9c\ub825\n cout << passwords.size() << \" \" << smallest_password << endl;\n\n return 0;\n }\n <\/string><\/char,><\/pre>\n4. \ucf54\ub4dc \ud574\uc124<\/h2>\n
\uc704\uc758 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \uc791\ub3d9\ud569\ub2c8\ub2e4:<\/p>\n
\n- \uc6b0\uc120 DNA \ubb38\uc790\uc5f4\uacfc \uadf8 \uae38\uc774, \ubd80\ubd84 \ubb38\uc790\uc5f4\uc758 \uae38\uc774 K\ub97c \uc785\ub825\ubc1b\uc2b5\ub2c8\ub2e4.<\/li>\n
- \uccab K\uac1c\uc758 \ubb38\uc790\uc758 \ube48\ub3c4\ub97c \uce74\uc6b4\ud2b8\ud558\uae30 \uc704\ud574
unordered_map<\/code>\uc744 \uc0ac\uc6a9\ud569\ub2c8\ub2e4.<\/li>\n- \uc2ac\ub77c\uc774\ub529 \uc708\ub3c4\uc6b0 \uae30\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec \uac01 K \uae38\uc774\uc758 \ubd80\ubd84 \ubb38\uc790\uc5f4\uc744 \uc774\ub3d9\ud558\uba74\uc11c \ube48\ub3c4\ub97c \uc218\uc815\ud569\ub2c8\ub2e4.<\/li>\n
- \uac01 \ubd80\ubd84 \ubb38\uc790\uc5f4\uc5d0 \ub300\ud574 \ube48\ub3c4\uc758 \ucd5c\uc18c\uac12\uc744 \uacc4\uc0b0\ud558\uace0, \uc870\uac74\uc5d0 \ub9de\ub294 \uacbd\uc6b0\uc5d0\ub9cc \uc720\ud6a8\ud55c \ube44\ubc00\ubc88\ud638 \ub9ac\uc2a4\ud2b8\uc5d0 \ucd94\uac00\ud569\ub2c8\ub2e4.<\/li>\n
- \ub9c8\uc9c0\ub9c9\uc5d0 \uc720\ud6a8\ud55c \ube44\ubc00\ubc88\ud638 \ub9ac\uc2a4\ud2b8\ub97c \uc815\ub82c\ud558\uc5ec \uac00\uc7a5 \uc791\uc740 \uc0ac\uc804 \uc21c\uc758 \ube44\ubc00\ubc88\ud638\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.<\/li>\n<\/ul>\n
5. \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4<\/h2>\n
\uc774\uc81c \ubcf8 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud55c \uba87 \uac00\uc9c0 \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub97c \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n
\ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4 1<\/h3>\n\n \uc785\ub825:\n 8 4\n ACGTTGCA\n\n \ucd9c\ub825:\n 1 ACGT\n <\/pre>\n\ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4 2<\/h3>\n\n \uc785\ub825:\n 12 5\n ACGTTACGATC\n\n \ucd9c\ub825:\n 3 ACCTA ACTAC TCGAT\n <\/pre>\n\ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4 3<\/h3>\n\n \uc785\ub825:\n 6 3\n ACGTAC\n\n \ucd9c\ub825:\n 2 ACG ACT\n <\/pre>\n6. \uacb0\ub860<\/h2>\n
\uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 DNA \ube44\ubc00\ubc88\ud638 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc2ac\ub77c\uc774\ub529 \uc708\ub3c4\uc6b0 \uae30\ubc95\uc744 \ud65c\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \ubc30\uc6e0\uc2b5\ub2c8\ub2e4. \uc774 \uae30\ubc95\uc740 \ubb38\uc790\uc5f4 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \ub9e4\uc6b0 \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ub420 \uc218 \uc788\uc73c\uba70, \ub2e4\uc591\ud55c \ubcc0\ud615 \ubb38\uc81c\uc5d0 \uc801\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub3c4 \ucc44\uc6a9\ub420 \uc218 \uc788\ub294 \uc88b\uc740 \uae30\ucd08 \uc9c0\uc2dd\uc774 \ub420 \uac83\uc785\ub2c8\ub2e4.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"