\uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\uc5d0\uc11c \uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \ucc3e\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc740 \ubc30\uc5f4\uc5d0\uc11c \uc11c\ub85c \ub2e4\ub978 \uc778\ub371\uc2a4\ub97c \uac00\uc9c0\ub294 \uc694\uc18c\ub4e4 \uc911\uc5d0\uc11c, \ud574\ub2f9 \uc694\uc18c\ub4e4\uc774 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ub41c \ubd80\ubd84 \ubc30\uc5f4\uc785\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \ubc30\uc5f4 \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4 \uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n \uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc744 \ucc3e\ub294 \uc5ec\ub7ec \uc54c\uace0\ub9ac\uc998 \uc911 \uac00\uc7a5 \ub9ce\uc774 \uc0ac\uc6a9\ub418\ub294 \ubc29\ubc95\uc740 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming)\uc785\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \ubb38\uc81c\ub97c \uc791\uc740 \ubd80\ubd84 \ubb38\uc81c\ub85c \ub098\ub204\uc5b4 \ud574\uacb0\ud558\uace0, \uc774 \uacb0\uacfc\ub97c \ubc14\ud0d5\uc73c\ub85c \uc804\uccb4 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \uc811\uadfc\ubc95\uc785\ub2c8\ub2e4.<\/p>\n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc744 \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc744 C#\uc73c\ub85c \uad6c\ud604\ud574 \ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\uba70, \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc758 \uae30\ucd08\ub97c \ubc30\uc6b0\uace0 \uc775\ud788\ub294 \ub370 \ub9e4\uc6b0 \uc720\uc6a9\ud569\ub2c8\ub2e4. \uafb8\uc900\ud55c \uc5f0\uc2b5\uc744 \ud1b5\ud574 \ub2e4\uc591\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ub370 \ud544\uc694\ud55c \uc0ac\uace0\ub825\uacfc \uc811\uadfc \ubc29\uc2dd\uc744 \uae30\ub97c \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"[10, 22, 9, 33, 21, 50, 41, 60, 80]<\/code>\uc5d0 \ub300\ud574 \uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc740 [10, 22, 33, 50, 60, 80]<\/code>\ub85c \uae38\uc774\ub294 6\uc785\ub2c8\ub2e4.<\/p>\n\ubb38\uc81c \uc815\uc758<\/h2>\n
arr<\/code>\uc774 \uc788\uc744 \ub54c, \uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \ubc18\ud658\ud558\ub294 \uba54\uc11c\ub4dc\ub97c \uc791\uc131\ud558\uc2dc\uc624.<\/p>\n\uc785\ub825<\/h3>\n
\n
n<\/code>\uc774 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. (1 \u2264 n \u2264 1000)<\/li>\nn<\/code>\uac1c\uc758 \uc815\uc218\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4. \uac01 \uc815\uc218\ub294 -10^6 \u2264 arr[i] \u2264 10^6<\/code>\uc785\ub2c8\ub2e4.<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
\uc608\uc81c<\/h2>\n
\uc785\ub825<\/h4>\n
9\n10 22 9 33 21 50 41 60 80<\/code><\/pre>\n\ucd9c\ub825<\/h4>\n
6<\/code><\/pre>\n\ubb38\uc81c \ud480\uc774 \ubc29\ubc95<\/h2>\n
\ub2e8\uacc4\ubcc4 \uc124\uba85<\/h3>\n
\n
arr<\/code>\uc758 \uae38\uc774\ub97c n<\/code>\uc774\ub77c \uac00\uc815\ud569\ub2c8\ub2e4. \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ubc30\uc5f4 dp<\/code>\ub97c \ucd08\uae30\ud654\ud558\uc5ec \uac01 \uc778\ub371\uc2a4 i<\/code>\uc5d0 \ub300\ud574, \uadf8 \uc778\ub371\uc2a4\uae4c\uc9c0\uc758 \uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \uc800\uc7a5\ud560 \uac83\uc785\ub2c8\ub2e4. \uc6b0\uc120 \uac01 \uc694\uc18c\uac00 \uc790\uae30 \uc790\uc2e0\ub9cc\uc73c\ub85c\ub3c4 \uc218\uc5f4\uc774 \ub420 \uc218 \uc788\uc73c\ubbc0\ub85c \ucd08\uae30\uac12\uc744 1\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/li>\ni<\/code>\uc640 j<\/code>\ub97c \ube44\uad50\ud569\ub2c8\ub2e4. \uc774\ub54c i<\/code>\ub294 j<\/code> \ubcf4\ub2e4 \ud06c\uace0, arr[i]<\/code>\uac00 arr[j]<\/code>\ubcf4\ub2e4 \ud074 \uacbd\uc6b0 (\uc989, \uc99d\uac00\ud558\ub294 \uc870\uac74\uc744 \ub9cc\uc871\ud558\ub294 \uacbd\uc6b0), dp[i]<\/code> \uac12\uc744 \uc5c5\ub370\uc774\ud2b8\ud569\ub2c8\ub2e4. \uad6c\uccb4\uc801\uc73c\ub85c, dp[i] = max(dp[i], dp[j] + 1)<\/code>\ub85c \uc124\uc815\ud569\ub2c8\ub2e4. \uc774\uac83\uc740 j<\/code>\ub97c \ud3ec\ud568\ud55c \uc218\uc5f4\uc758 \uae38\uc774\uc5d0 1\uc744 \ucd94\uac00\ud558\ub294 \uac83\uc785\ub2c8\ub2e4.<\/li>\ndp<\/code> \ubc30\uc5f4\uc5d0\uc11c \ucd5c\ub300\uac12\uc744 \ucc3e\uc544 \ubc18\ud658\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\nC# \uad6c\ud604<\/h2>\n
using System;\n\nclass Program\n{\n static void Main()\n {\n int n = int.Parse(Console.ReadLine());\n int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);\n\n int[] dp = new int[n];\n for (int i = 0; i < n; i++)\n {\n dp[i] = 1; \/\/ \uac01 \uc694\uc18c\ub294 \ucd5c\uc18c 1\uac1c\uc758 \uc218\uc5f4\uc744 \ud615\uc131\ud560 \uc218 \uc788\uc74c\n }\n\n for (int i = 1; i < n; i++)\n {\n for (int j = 0; j < i; j++)\n {\n if (arr[i] > arr[j] && dp[i] < dp[j] + 1)\n {\n dp[i] = dp[j] + 1;\n }\n }\n }\n\n int maxLength = dp[0];\n for (int i = 1; i < n; i++)\n {\n if (dp[i] > maxLength)\n {\n maxLength = dp[i];\n }\n }\n\n Console.WriteLine(maxLength);\n }\n}\n<\/code><\/pre>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h2>\n
O(n^2)<\/code>\uc785\ub2c8\ub2e4. \uc774\ub294 \ub450 \uac1c\uc758 \uc911\ucca9 \ubc18\ubcf5\ubb38\uc744 \uc0ac\uc6a9\ud558\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. \uc678\ubd80 \ubc18\ubcf5\ubb38\uacfc \ub0b4\ubd80 \ubc18\ubcf5\ubb38 \ubaa8\ub450 \uac01\uac01 \ubc30\uc5f4\uc758 \uae38\uc774\ub9cc\ud07c \uc2e4\ud589\ub418\ubbc0\ub85c \ucd5c\uc545\uc758 \uacbd\uc6b0 \ucd1d n * n<\/code>\uc758 \uc5f0\uc0b0\uc774 \ud544\uc694\ud569\ub2c8\ub2e4. \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n)<\/code>\uc774\uba70, \uc774\ub294 dp<\/code> \ubc30\uc5f4\uc744 \uc800\uc7a5\ud558\uae30 \uc704\ud574 \ud544\uc694\ud55c \uacf5\uac04\uc785\ub2c8\ub2e4.<\/p>\n\uacb0\ub860<\/h2>\n