{"id":28360,"date":"2024-10-27T16:10:33","date_gmt":"2024-10-27T16:10:33","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=28360"},"modified":"2024-11-26T07:03:46","modified_gmt":"2024-11-26T07:03:46","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-2-n-%ed%83%80%ec%9d%bc-%ec%b1%84%ec%9a%b0%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/28360\/","title":{"rendered":"\ucf54\ud2c0\ub9b0 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, 2 N \ud0c0\uc77c \ucc44\uc6b0\uae30"},"content":{"rendered":"

<\/p>\n

\n

\uc774 \uac15\uc88c\uc5d0\uc11c\ub294 2*N \ud0c0\uc77c \ucc44\uc6b0\uae30 \ubb38\uc81c\ub97c \uae4a\uc774 \uc788\uac8c \ub2e4\ub8e8\uace0, \uc774\ub97c \ud480\uae30 \uc704\ud55c \uc54c\uace0\ub9ac\uc998\uacfc \ucf54\ud2c0\ub9b0 \uad6c\ud604 \ubc29\ubc95\uc744 \uc0c1\uc138\ud788 \uc124\uba85\ud569\ub2c8\ub2e4.<\/p>\n<\/header>\n

\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

2*N \ud06c\uae30\uc758 \uc9c1\uc0ac\uac01\ud615\uc744 1*2 \ud06c\uae30\uc758 \ud0c0\uc77c\ub85c \ucc44\uc6b0\ub294 \ubc29\ubc95\uc758 \uc218\ub97c \uacc4\uc0b0\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \ud0c0\uc77c\uc740 \uac00\ub85c \ub610\ub294 \uc138\ub85c\ub85c \ubc30\uce58\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc8fc\uc5b4\uc9c4 N \uac12\uc5d0 \ub300\ud574 \uac00\ub2a5\ud55c \ubaa8\ub4e0 \ud0c0\uc77c \ubc30\uce58 \ubc29\ubc95\uc758 \uc218\ub97c \uad6c\ud558\ub294 \uac83\uc774 \ubaa9\ud45c\uc785\ub2c8\ub2e4.<\/p>\n

\uc608\uc2dc:<\/strong>
\n – N=1: 1\uac00\uc9c0 (1\ud0c0\uc77c \uc138\ub85c\ub85c \ubc30\uce58)
\n – N=2: 2\uac00\uc9c0 (1\ud0c0\uc77c \uac00\ub85c\/\uc138\ub85c\ub85c \uac01\uac01 \ubc30\uce58)
\n – N=3: 3\uac00\uc9c0
\n – N=4: 5\uac00\uc9c0
\n – N=5: 8\uac00\uc9c0<\/p>\n

\uc704\uc640 \uac19\uc740 \ubc29\uc2dd\uc73c\ub85c \ud0c0\uc77c\uc744 \ubc30\uce58\ud560 \ub54c, N\uc774 \ucee4\uc9c8\uc218\ub85d \uac00\ub2a5\ud55c \ubc30\uce58 \ubc29\ubc95\uc758 \uac1c\uc218\uac00 \uc99d\uac00\ud569\ub2c8\ub2e4. \uc774\ub7ec\ud55c \ubb38\uc81c\ub294 \ud53c\ubcf4\ub098\uce58 \uc218\uc5f4\uacfc \uad00\ub828\uc774 \uae4a\uc2b5\ub2c8\ub2e4.<\/p>\n<\/section>\n

\n

\uc811\uadfc \ubc29\ubc95<\/h2>\n

\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc2dc\uc791\ud558\ub294 \ubc29\ubc95\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n

    \n
  1. \uc7ac\uadc0\uc801 \uc811\uadfc:<\/strong> \ud0c0\uc77c\uc744 \ubc30\uce58\ud558\ub294 \ubc29\uc2dd\uc758 \ud0d0\uc0c9\uc744 \ud1b5\ud574 \uac00\ub2a5\ud55c \uc870\ud569\uc744 \ucc3e\ub294 \uac83\uc785\ub2c8\ub2e4. N\uc774 0\uc77c \ub54c\ub294 1\uac00\uc9c0, 1\uc77c \ub54c\ub294 1\uac00\uc9c0\ub85c \uc2dc\uc791\ud574\uc11c \ubaa8\ub4e0 \uacbd\uc6b0\ub97c \ud0d0\uc0c9\ud569\ub2c8\ub2e4.<\/li>\n
  2. \ub3d9\uc801 \uacc4\ud68d\ubc95:<\/strong> \ud53c\ubcf4\ub098\uce58 \uc218\uc5f4\uc744 \uc774\uc6a9\ud558\uc5ec \uc774\uc804 \uacb0\uacfc\ub97c \uc800\uc7a5\ud558\uace0, \uc774\ub97c \ubc14\ud0d5\uc73c\ub85c \ub354 \ud070 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\uc2dd\uc785\ub2c8\ub2e4.<\/li>\n<\/ol>\n<\/section>\n
    \n

    \ub3d9\uc801 \uacc4\ud68d\ubc95\uc744 \ud65c\uc6a9\ud55c \ud480\uc774<\/h2>\n

    \uac00\uc7a5 \ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc740 \ub3d9\uc801 \uacc4\ud68d\ubc95(Dynamic Programming)\uc744 \ud65c\uc6a9\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud558\uba74 \uc911\ubcf5\ub418\ub294 \uacc4\uc0b0\uc744 \ud53c\ud558\uace0 O(N)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n

    \uc54c\uace0\ub9ac\uc998 \uc124\uba85<\/h3>\n

    DP \ubc30\uc5f4\uc744 \uc815\uc758\ud558\uc5ec \uacc4\uc0b0\ud569\ub2c8\ub2e4:<\/p>\n

    \n        dp[i] = i \ud06c\uae30\uc758 \uc9c1\uc0ac\uac01\ud615\uc744 \ucc44\uc6b0\ub294 \ubc29\ubc95\uc758 \uc218\n        - dp[0] = 1 (\uc544\ubb34\uac83\ub3c4 \ucc44\uc6b0\uc9c0 \uc54a\uc74c)\n        - dp[1] = 1 (1*2 \ud0c0\uc77c \uc138\ub85c \ubc30\uce58)\n        - dp[2] = 2 (1*2 \ud0c0\uc77c \ub450 \uac1c \uac00\ub85c \ub610\ub294 \uc138\ub85c \ubc30\uce58)\n        - dp[n] = dp[n-1] + dp[n-2]\n        <\/pre>\n
    \uc774\uc81c N\uc758 \ubc94\uc704\uc5d0 \ub530\ub77c dp \ubc30\uc5f4\uc744 \ucc28\ub840\ub300\ub85c \ucc44\uc6cc\ub098\uac00\uba74 \ub429\ub2c8\ub2e4. dp[n-1]\uc740 \ub9c8\uc9c0\ub9c9 \ud0c0\uc77c\uc744 \uc138\ub85c\ub85c \ubc30\uce58\ud588\uc744 \ub54c\uc758 \uacbd\uc6b0\uc774\uace0, dp[n-2]\ub294 \ub9c8\uc9c0\ub9c9 \ub450 \uac1c\uc758 \ud0c0\uc77c\uc744 \uac00\ub85c\ub85c \ubc30\uce58\ud588\uc744 \ub54c\uc758 \uacbd\uc6b0\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n
    \n
    \ucf54\ud2c0\ub9b0 \uad6c\ud604<\/h2>\n
    \ucf54\ub4dc \uc608\uc81c<\/h3>\n
    \n        fun tileCount(n: Int): Int {\n            if (n == 0) return 1\n            if (n == 1) return 1\n\n            val dp = IntArray(n + 1)\n            dp[0] = 1\n            dp[1] = 1\n\n            for (i in 2..n) {\n                dp[i] = dp[i - 1] + dp[i - 2]\n            }\n\n            return dp[n]\n        }\n\n        fun main() {\n            val n = 5 \/\/ \uc608\uc2dc\ub85c N=5\n            println(\"2*$n \ud0c0\uc77c\uc744 \ucc44\uc6b0\ub294 \ubc29\ubc95\uc758 \uc218: ${tileCount(n)}\")\n        }\n        <\/pre>\n
    \uc704 \ucf54\ub4dc\ub97c \uc2e4\ud589\ud558\uba74, 2*5 \ud06c\uae30\uc758 \uc9c1\uc0ac\uac01\ud615\uc744 \ucc44\uc6b0\ub294 \ubc29\ubc95\uc758 \uc218\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n<\/section>\n
    \n
    \uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
    \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N)\uc774\uba70, \uacf5\uac04 \ubcf5\uc7a1\ub3c4 \ub610\ud55c O(N)\uc785\ub2c8\ub2e4. N\uc774 \uc99d\uac00\ud560\uc218\ub85d \uacc4\uc0b0 \uc2dc\uac04\uacfc \uba54\ubaa8\ub9ac \uc0ac\uc6a9\ub7c9\uc774 \uc120\ud615\uc801\uc73c\ub85c \uc99d\uac00\ud569\ub2c8\ub2e4. \uc774 \uc815\ub3c4\uc758 \ubcf5\uc7a1\ub3c4\ub294 \ub300\ubd80\ubd84\uc758 \uc2e4\uc804 \ubb38\uc81c\uc5d0\uc11c \ud6a8\uc728\uc801\uc778 \uc218\uc900\uc785\ub2c8\ub2e4.<\/p>\n<\/section>\n
    \n
    \uacb0\ub860<\/h2>\n
    2*N \ud0c0\uc77c \ucc44\uc6b0\uae30 \ubb38\uc81c\ub294 \uc7ac\uadc0\uc801 \uc811\uadfc\uacfc \ub3d9\uc801 \uacc4\ud68d\ubc95\uc744 \ud1b5\ud574 \uc27d\uace0 \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ucf54\ud2c0\ub9b0 \ud480\uc774\ub97c \ud1b5\ud574 \ubb38\uc81c\ub97c \uad6c\uc870\uc801\uc73c\ub85c \uc774\ud574\ud558\uace0, \uc2e4\uc81c \uc0c1\ud669\uc5d0\uc11c\ub3c4 \uc751\uc6a9\ud560 \uc218 \uc788\ub294 \uc88b\uc740 \uacbd\ud5d8\uc774 \ub418\uae38 \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n
    \uc5ec\uae30\uae4c\uc9c0\uac00 2*N \ud0c0\uc77c \ucc44\uc6b0\uae30 \ubb38\uc81c\uc758 \ud574\uacb0 \uacfc\uc815\uc785\ub2c8\ub2e4. \ucd94\uac00\uc801\uc73c\ub85c \ub2e4\ub978 \ubb38\uc81c\ub4e4\ub3c4 \uc5f0\uc2b5\ud558\uba70 \ub2e4\uc591\ud55c \ubc29\uc2dd\uc73c\ub85c \uc54c\uace0\ub9ac\uc998\uc744 \ub2e4\ub8e8\ub294 \uc5f0\uc2b5\uc744 \ud558\uc2dc\uae38 \uad8c\uc7a5\ud569\ub2c8\ub2e4!<\/p>\n<\/section>\n