\uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4 (Longest Increasing Subsequence, LIS)\uc744 \ucc3e\ub294 \ubb38\uc81c\ub294 \uc8fc\uc5b4\uc9c4 \uc218\uc5f4 \ub0b4\uc5d0\uc11c \uc99d\uac00\ud558\ub294 \uc21c\uc11c\ub97c \uc720\uc9c0\ud558\uba70 \uac00\ub2a5\ud55c \uae34 \ubd80\ubd84 \uc218\uc5f4\uc744 \ucc3e\ub294 \uac83\uc774\ub2e4. \ubd80\ubd84 \uc218\uc5f4\uc740 \uc5f0\uc18d\uc801\uc774\uc9c0 \uc54a\uc544\ub3c4 \ub418\uc9c0\ub9cc, \uc120\ud0dd\ud55c \uc22b\uc790\ub4e4\uc740 \ubc18\ub4dc\uc2dc \uc99d\uac00\ud558\ub294 \uc21c\uc11c\ub97c \ub530\ub77c\uc57c \ud55c\ub2e4.<\/p>\n
\uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \ucd9c\ub825\ud558\ub77c.<\/p>\n
6\n10 20 10 30 20 50<\/code><\/pre>\n\ucd9c\ub825 \uc608\uc2dc<\/h3>\n4<\/code><\/pre>\n\ubb38\uc81c \ud480\uc774 \uacfc\uc815<\/h2>\n1\ub2e8\uacc4: \ubb38\uc81c \uc774\ud574\ud558\uae30<\/h3>\n
\ubb38\uc81c\ub97c \uc774\ud574\ud558\uae30 \uc704\ud574 \uc218\uc5f4\uc744 \uc0b4\ud3b4\ubcf4\uc790. \uc8fc\uc5b4\uc9c4 \uc218\uc5f4 [10, 20, 10, 30, 20, 50]<\/code>\uc758 \uacbd\uc6b0, \uac00\ub2a5\ud55c \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc740 \uc5ec\ub7ec \uac00\uc9c0\uac00 \uc788\ub2e4. \uc774 \uc218\uc5f4\uc758 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4 \uc911 \uac00\uc7a5 \uae34 \uac83\uc740 [10, 20, 30, 50]<\/code>\ub85c, \uae38\uc774\ub294 4\uc774\ub2e4. \ub530\ub77c\uc11c \uc815\ub2f5\uc740 4\uac00 \ub41c\ub2e4.<\/p>\n2\ub2e8\uacc4: \uc54c\uace0\ub9ac\uc998 \uc120\ud0dd\ud558\uae30<\/h3>\n
\uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc744 \ucc3e\ub294 \uc54c\uace0\ub9ac\uc998\uc740 \uc5ec\ub7ec \uac00\uc9c0\uac00 \uc788\uc9c0\ub9cc \uac00\uc7a5 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc740 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\uc774\ub2e4. \uc774 \ubc29\ubc95\uc740 O(N^2)<\/code>\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c4\ub2e4. \uc774 \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud574\ubcf4\uaca0\ub2e4.<\/p>\n3\ub2e8\uacc4: \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ud480\uc774<\/h3>\nfunction LIS(array) {\n const N = array.length;\n const dp = new Array(N).fill(1); \/\/ \ubd80\ubd84 \uc218\uc5f4 \uae38\uc774\ub97c 1\ub85c \ucd08\uae30\ud654\n\n for (let i = 1; i < N; i++) {\n for (let j = 0; j < i; j++) {\n if (array[i] > array[j]) {\n dp[i] = Math.max(dp[i], dp[j] + 1);\n }\n }\n }\n\n return Math.max(...dp);\n }\n\n const sequence = [10, 20, 10, 30, 20, 50];\n console.log(LIS(sequence)); \/\/ \ucd9c\ub825: 4\n <\/code><\/pre>\n\uc124\uba85<\/h4>\n
1. dp<\/code> \ubc30\uc5f4\uc744 \uc120\uc5b8\ud558\uc5ec \uac01 \uc778\ub371\uc2a4\uc758 \uac00\uc7a5 \uae34 \uc99d\uac00\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc758 \uae38\uc774\ub97c \uc800\uc7a5\ud55c\ub2e4. \ucd08\uae30\uac12\uc740 1\ub85c \uc124\uc815\ud55c\ub2e4, \uac01 \uc694\uc18c \uc790\uc2e0\ub9cc\uc73c\ub85c\ub3c4 \ubd80\ubd84 \uc218\uc5f4\uc744 \uc774\ub8f0 \uc218 \uc788\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n2. \ub450 \uac1c\uc758 \ubc18\ubcf5\ubb38\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc778\ub371\uc2a4 i<\/code>\uc640 j<\/code>\ub97c \ube44\uad50\ud55c\ub2e4. \ub9cc\uc57d array[i]<\/code>\uac00 array[j]<\/code>\ubcf4\ub2e4 \ud070 \uacbd\uc6b0, dp[i]<\/code>\uc758 \uac12\uc740 dp[j] + 1<\/code>\uacfc \ud604\uc7ac dp[i]<\/code>\uc758 \uac12 \uc911 \ud070 \uac12\uc73c\ub85c \uc5c5\ub370\uc774\ud2b8\ub41c\ub2e4. \uc774\ub294 array[j]<\/code>\ub97c \ud3ec\ud568\ud558\uc5ec array[i]<\/code>\ub97c \ud3ec\ud568\ud55c \ubd80\ubd84 \uc218\uc5f4\uc744 \uace0\ub824\ud558\ub294 \uac83\uc774\ub2e4.<\/p>\n