\uc548\ub155\ud558\uc138\uc694! \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \ucf54\ud2c0\ub9b0\uc744 \uc774\uc6a9\ud574 \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \uc811\ud560 \uc218 \uc788\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\ub97c \uae4a\uc774 \uc788\uac8c \ub2e4\ub904\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc8fc\uc81c\ub294 ‘\uc81c\uacf1\uc774 \uc544\ub2cc \uc218 \ucc3e\uae30’\uc785\ub2c8\ub2e4. \ubcf8 \ubb38\uc81c\uc758 \uae30\ubcf8 \uc544\uc774\ub514\uc5b4\ub294 \uc8fc\uc5b4\uc9c4 \uc218 \ub0b4\uc5d0\uc11c \uc81c\uacf1\uc218(1, 4, 9, 16 \ub4f1)\ub4e4\uc774 \uc544\ub2cc \ubaa8\ub4e0 \uc218\ub97c \ucc3e\uc544\ub0b4\ub294 \uac83\uc785\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub97c \uc774\ud574\ud558\uace0 \ud574\uacb0\ud558\uae30 \uc704\ud574 \ud544\uc694\ud55c \uc54c\uace0\ub9ac\uc998\uc801 \uc0ac\uace0\uc640 \ucf54\ud2c0\ub9b0 \ubb38\ubc95\uc744 \ud568\uaed8 \uc0b4\ud3b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.<\/p>\n<\/div>\n
\ubb38\uc81c\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
\n\uc81c\uacf1\uc774 \uc544\ub2cc \uc218 \ucc3e\uae30<\/strong>
\n 1\ubd80\ud130 N\uae4c\uc9c0\uc758 \uc790\uc5f0\uc218 \uc911\uc5d0\uc11c \uc81c\uacf1\uc218\uac00 \uc544\ub2cc \uc218\ub4e4\uc744 \ubaa8\ub450 \ucc3e\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uc2dc\uc624. <\/p>\n\uc785\ub825<\/strong>: \uc815\uc218 N (1 \u2264 N \u2264 1000)
\n\ucd9c\ub825<\/strong>: \uc81c\uacf1\uc218\uac00 \uc544\ub2cc \uc218\ub4e4\uc758 \ub9ac\uc2a4\ud2b8\n <\/p><\/blockquote>\n<\/div>\n\n\ubb38\uc81c \ubd84\uc11d<\/h2>\n
\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uacfc\uc815\uc774 \ud544\uc694\ud569\ub2c8\ub2e4:<\/p>\n
\n
- 1\ubd80\ud130 N\uae4c\uc9c0\uc758 \ubaa8\ub4e0 \uc790\uc5f0\uc218\ub97c \ubc18\ubcf5\ubb38\uc744 \ud1b5\ud574 \ud0d0\uc0c9<\/li>\n
- \uac01 \uc218\uac00 \uc81c\uacf1\uc218\uc778\uc9c0 \ud655\uc778\ud558\ub294 \ubc29\ubc95 \uad6c\uc0c1<\/li>\n
- \uc81c\uacf1\uc218\uac00 \uc544\ub2cc \uc218\ub4e4\uc744 \ub9ac\uc2a4\ud2b8\uc5d0 \uc800\uc7a5<\/li>\n<\/ul>\n
\uc81c\uacf1\uc218\ub294 1, 4, 9, 16, 25, … \uc758 \ud615\ud0dc\ub85c \ub098\ud0c0\ub098\uba70, \uc774\ub7ec\ud55c \uc218\ub4e4\uc740 i\uc758 \uc81c\uacf1\uc73c\ub85c \ud45c\uc2dc\ub429\ub2c8\ub2e4. \uadf8\ub7ec\ubbc0\ub85c i\uac00 1\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \u221aN\uae4c\uc9c0 \uc99d\uac00\ud558\uba74\uc11c \uadf8 \uac12\uc744 \uc81c\uacf1\ud55c \uacb0\uacfc\ub97c \ub9ac\uc2a4\ud2b8\uc5d0 \uc800\uc7a5\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uadf8 \ud6c4, \uc774 \uc81c\uacf1\uc218\ub4e4\uc744 \uc81c\uc678\ud55c \ub098\uba38\uc9c0 \uc218\ub4e4\uc744 \uacb0\uacfc \ub9ac\uc2a4\ud2b8\uc5d0 \ud3ec\ud568\uc2dc\ud0a4\uba74 \ub429\ub2c8\ub2e4.<\/p>\n<\/div>\n
\n\uc54c\uace0\ub9ac\uc998 \uc124\uacc4<\/h2>\n
\uc704\uc758 \uacfc\uc815\uc744 \ud1a0\ub300\ub85c \uc544\ub798\uc640 \uac19\uc740 \uc54c\uace0\ub9ac\uc998\uc744 \uc124\uacc4\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n
\n
- \ube48 \ub9ac\uc2a4\ud2b8\ub97c \uc0dd\uc131\ud55c\ub2e4.<\/li>\n
- 1\ubd80\ud130 N\uae4c\uc9c0 \ubc18\ubcf5\ubb38\uc744 \ub3cc\ub9b0\ub2e4.<\/li>\n
- \uac01 \uc218\uac00 \uc81c\uacf1\uc218\uc778\uc9c0 \ud310\ubcc4\ud55c\ub2e4.<\/li>\n
- \uc81c\uacf1\uc218\uac00 \uc544\ub2d0 \uacbd\uc6b0 \ub9ac\uc2a4\ud2b8\uc5d0 \ucd94\uac00\ud55c\ub2e4.<\/li>\n
- \uacb0\uacfc \ub9ac\uc2a4\ud2b8\ub97c \ucd9c\ub825\ud55c\ub2e4.<\/li>\n<\/ol>\n<\/div>\n
\n\ucf54\ud2c0\ub9b0 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
\uc790 \uc774\uc81c \uc774 \uc54c\uace0\ub9ac\uc998\uc744 \ucf54\ud2c0\ub9b0\uc73c\ub85c \uad6c\ud604\ud574\ubd05\uc2dc\ub2e4:<\/p>\n
fun findNonPerfectSquares(n: Int): List{\n val nonPerfectSquares = mutableListOf ()\n \n \/\/ \uc81c\uacf1\uc218\ub97c \uc800\uc7a5\ud558\uae30 \uc704\ud55c \uc138\ud2b8\n val perfectSquares = mutableSetOf ()\n \n \/\/ 1\ubd80\ud130 n\uc758 \uc81c\uacf1\uc218 \uacc4\uc0b0\n for (i in 1..Math.sqrt(n.toDouble()).toInt()) {\n perfectSquares.add(i * i)\n }\n \n \/\/ 1\ubd80\ud130 N\uae4c\uc9c0 \ud0d0\uc0c9\n for (i in 1..n) {\n \/\/ \uc81c\uacf1\uc218\uac00 \uc544\ub2cc \uacbd\uc6b0 \ub9ac\uc2a4\ud2b8\uc5d0 \ucd94\uac00\n if (i !in perfectSquares) {\n nonPerfectSquares.add(i)\n }\n }\n \n return nonPerfectSquares\n}<\/int><\/int><\/int><\/code><\/pre>\n \uc704 \ucf54\ub4dc\uc5d0\uc11c
findNonPerfectSquares<\/code> \ud568\uc218\ub294 \uc785\ub825\uc73c\ub85c \uc8fc\uc5b4\uc9c4 N\uae4c\uc9c0\uc758 \uc790\uc5f0\uc218 \uc911 \uc81c\uacf1\uc218\uac00 \uc544\ub2cc \uc218\ub4e4\uc744 \ub9ac\uc2a4\ud2b8\ub85c \ubc18\ud658\ud569\ub2c8\ub2e4.mutableSetOf<\/code>\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc81c\uacf1\uc218\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uad00\ub9ac\ud558\uace0, \ud0d0\uc0c9\uc758 \ubcf5\uc7a1\uc131\uc744 \uc904\uc600\uc2b5\ub2c8\ub2e4.<\/p>\n<\/div>\n\n\ucf54\ub4dc \uc2e4\ud589 \ubc0f \uacb0\uacfc<\/h2>\n
\uc774\uc81c \uc791\uc131\ud55c \ucf54\ub4dc\ub97c \ud14c\uc2a4\ud2b8\ud574\ubcf4\uace0 \uacb0\uacfc\ub97c \ud655\uc778\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, N\uc744 20\uc73c\ub85c \uc124\uc815\ud558\uace0 \ud568\uc218\ub97c \ud638\ucd9c\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc740 \uacb0\uacfc\ub97c \uc5bb\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n
fun main() {\n val n = 20\n val result = findNonPerfectSquares(n)\n println(\"1\ubd80\ud130 $n\uae4c\uc9c0\uc758 \uc81c\uacf1\uc774 \uc544\ub2cc \uc218\ub4e4: $result\")\n}<\/code><\/pre>\n\uc704\uc758
main<\/code> \ud568\uc218\ub97c \ud1b5\ud574 \uacb0\uacfc\ub97c \ucd9c\ub825\ud558\uba74 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n1\ubd80\ud130 20\uae4c\uc9c0\uc758 \uc81c\uacf1\uc774 \uc544\ub2cc \uc218\ub4e4: [2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20]<\/code><\/pre>\n<\/div>\n\n\ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\uc774\ubc88 \ubb38\uc81c\uc758 \uc2dc\uac04\ubcf5\uc7a1\ub3c4\ub97c \uc0b4\ud3b4\ubcf4\uba74:<\/p>\n
\n
- \uc81c\uacf1\uc218\ub97c \uacc4\uc0b0\ud558\ub294 for\ubb38: O(\u221aN)<\/li>\n
- N\uae4c\uc9c0\uc758 \ubc18\ubcf5\ubb38\uc5d0\uc11c \uc81c\uacf1\uc218 \uccb4\ud06c: O(N)<\/li>\n<\/ul>\n
\ub530\ub77c\uc11c \uc804\uccb4 \uc2dc\uac04\ubcf5\uc7a1\ub3c4\ub294 O(\u221aN + N) = O(N)\uc785\ub2c8\ub2e4.<\/p>\n<\/div>\n