x = 8<\/code>\uc774\ub77c\uba74 \ub2e4\uc74c\uacfc \uac19\uc740 \uacfc\uc815\uc744 \ud1b5\ud574 1\ub85c \ub9cc\ub4e4 \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n\n8 \u2192 4 \u2192 2 \u2192 1\n <\/pre>\n\uc704\uc640 \uac19\uc740 \uacbd\uc6b0 \ucd5c\uc18c \uc791\uc5c5 \ud69f\uc218\ub294 3\uc785\ub2c8\ub2e4.<\/p>\n
\uc811\uadfc \ubc29\ubc95<\/h2>\n
\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc0c1\ud0dc \uae30\ubc18 \uc811\uadfc \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc8fc\uc5b4\uc9c4 \uc815\uc218 x<\/code>\ub97c 1\ub85c \ub9cc\ub4e4\uae30 \uc704\ud55c \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ucc3e\uae30 \uc704\ud574 BFS(\ub108\ube44 \uc6b0\uc120 \ud0d0\uc0c9) \ub610\ub294 DFS(\uae4a\uc774 \uc6b0\uc120 \ud0d0\uc0c9)\ub97c \ud65c\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \uc774 \ubb38\uc81c\uc758 \uacbd\uc6b0 BFS\uac00 \ub354 \uc801\ud569\ud569\ub2c8\ub2e4.<\/p>\nBFS\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud558\ub294 \uc774\uc720\ub294 \uac01 \uc0c1\ud0dc\uc5d0 \ub3c4\ub2ec\ud558\uae30 \uc704\ud574 \uace0\ub824\ud574\uc57c \ud560 \uacbd\ub85c\uac00 \uc5ec\ub7ec \uac1c\uc778 \uacbd\uc6b0\uac00 \ub9ce\uae30 \ub54c\ubb38\uc785\ub2c8\ub2e4. BFS\ub294 \uac01 \ub2e8\uacc4\uc5d0\uc11c \uac00\ub2a5\ud55c \ubaa8\ub4e0 \uacbd\ub85c\ub97c \ud0d0\uc0c9\ud558\ubbc0\ub85c \ucd5c\uc801\uc758 \uacbd\ub85c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ucc3e\uc744 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
BFS \uc54c\uace0\ub9ac\uc998 \uad6c\ud604<\/h2>\n
\uc774\uc81c BFS \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub4dc\ub97c \uc791\uc131\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
\nfunction minStepsToOne(x) {\n const queue = [];\n const visited = new Set();\n \n queue.push(x);\n visited.add(x);\n let steps = 0;\n \n while (queue.length > 0) {\n const size = queue.length; \/\/ \ud604\uc7ac \ub808\ubca8\uc758 \ub178\ub4dc \uac1c\uc218\n \n for (let i = 0; i < size; i++) {\n const current = queue.shift();\n \/\/ \ud604\uc7ac \uc22b\uc790\uac00 1\uc774\uba74 steps \ubc18\ud658\n if (current === 1) {\n return steps;\n }\n \n \/\/ \uc9dd\uc218\uc77c \uacbd\uc6b0\n if (current % 2 === 0 && !visited.has(current \/ 2)) {\n queue.push(current \/ 2);\n visited.add(current \/ 2);\n }\n \/\/ \ud640\uc218\uc77c \uacbd\uc6b0\n if (current > 1 && !visited.has(current - 1)) {\n queue.push(current - 1);\n visited.add(current - 1);\n }\n }\n steps++; \/\/ \ud55c \ub808\ubca8 \ub05d\ub0a8\n }\n \n return steps;\n}\n\n\/\/ \uc608\uc2dc \ud638\ucd9c\nconsole.log(minStepsToOne(8)); \/\/ \ucd9c\ub825: 3\n <\/code><\/pre>\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
\uc704 \ucf54\ub4dc\uc5d0\uc11c \uc0ac\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc758 \uc8fc\uc694 \ub0b4\uc6a9\uc744 \uc124\uba85\ud558\uaca0\uc2b5\ub2c8\ub2e4:<\/p>\n
\n- \ud050(Queue) \uc0ac\uc6a9:<\/strong> BFS\ub294 \ud050 \uc790\ub8cc\uad6c\uc870\ub97c \uc0ac\uc6a9\ud558\uc5ec \uad6c\ud604\ub429\ub2c8\ub2e4. \ud050\uc5d0 \uac01 \uc0c1\ud0dc\ub97c \ucd94\uac00\ud558\uace0, \ud558\ub098\uc529 \uaebc\ub0b4\uc5b4 \ucc98\ub9ac\ud569\ub2c8\ub2e4.<\/li>\n
- \ubc29\ubb38 \uae30\ub85d:<\/strong> \uc911\ubcf5 \ubc29\ubb38\uc744 \ubc29\uc9c0\ud558\uae30 \uc704\ud574 \ubc29\ubb38\ud55c \uc0c1\ud0dc\ub97c
Set<\/code> \uc790\ub8cc\uad6c\uc870\uc5d0 \uae30\ub85d\ud569\ub2c8\ub2e4.<\/li>\n- \ub2e8\uacc4 \uce74\uc6b4\ud305:<\/strong> \uac01 BFS \ub808\ubca8\uc744 \uc9c4\ud589\ud560 \ub54c\ub9c8\ub2e4 \ub2e8\uacc4\ub97c \uc99d\uac00\uc2dc\ucf1c \ucd1d \uc791\uc5c5 \ud69f\uc218\ub97c \uae30\ub85d\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4<\/h2>\n
\ubaa8\ub4e0 \ubb38\uc81c \ud574\uacb0 \uacfc\uc815\uc5d0\uc11c \ub2e4\uc591\ud55c \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\ub97c \uace0\ub824\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \ub2e4\uc74c\uc740 \uba87 \uac00\uc9c0 \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\uc785\ub2c8\ub2e4:<\/p>\n
\n\/\/ \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4\nconsole.log(minStepsToOne(1)); \/\/ \ucd9c\ub825: 0 (\uc774\ubbf8 1)\nconsole.log(minStepsToOne(2)); \/\/ \ucd9c\ub825: 1 (2 \u2192 1)\nconsole.log(minStepsToOne(3)); \/\/ \ucd9c\ub825: 2 (3 \u2192 2 \u2192 1)\nconsole.log(minStepsToOne(10)); \/\/ \ucd9c\ub825: 5 (10 \u2192 5 \u2192 4 \u2192 2 \u2192 1)\nconsole.log(minStepsToOne(25)); \/\/ \ucd9c\ub825: 6 (25 \u2192 24 \u2192 12 \u2192 6 \u2192 3 \u2192 2 \u2192 1)\nconsole.log(minStepsToOne(100)); \/\/ \ucd9c\ub825: 7 (100 \u2192 50 \u2192 25 \u2192 24 \u2192 12 \u2192 6 \u2192 3 \u2192 2 \u2192 1)\n <\/code><\/pre>\n\ucd5c\uc801\ud654 \ubc29\ubc95<\/h2>\n
\uc704\uc758 BFS \uc54c\uace0\ub9ac\uc998\uc73c\ub85c\ub3c4 \ud6a8\uc728\uc801\uc778 \uacb0\uacfc\ub97c \uc5bb\uc744 \uc218 \uc788\uc9c0\ub9cc, \ucd94\uac00\uc801\uc778 \ucd5c\uc801\ud654\ub3c4 \uac00\ub2a5\ud569\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \uc0c1\ud0dc\ub97c \uc800\uc7a5\ud560 \ub54c \uba54\ubaa8\uc774\uc81c\uc774\uc158(Memoization)\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc73c\ub85c \uc774\uc804\uc5d0 \uacc4\uc0b0\ud55c \uac12\uc744 \uc800\uc7a5\ud558\uc5ec \ubd88\ud544\uc694\ud55c \uc911\ubcf5 \uacc4\uc0b0\uc744 \uc904\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
\uacb0\ub860<\/h2>\n
\uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub97c \uc0ac\uc6a9\ud558\uc5ec “\uc815\uc218\ub97c 1\ub85c \ub9cc\ub4e4\uae30”\ub77c\ub294 \ubb38\uc81c\ub97c \ud574\uacb0\ud588\uc2b5\ub2c8\ub2e4. BFS\ub97c \ud65c\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc744 \uc124\uba85\ud558\uace0, \ucf54\ub4dc \uad6c\ud604, \ud14c\uc2a4\ud2b8 \ucf00\uc774\uc2a4, \uadf8\ub9ac\uace0 \ucd5c\uc801\ud654 \ubc29\ubc95\uae4c\uc9c0 \uc544\uc6b0\ub974\ub294 \uc790\uc138\ud55c \ub0b4\uc6a9\uc744 \ub2e4\ub8e8\uc5c8\uc2b5\ub2c8\ub2e4. \ub2e4\uc74c \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub3c4 \uc774\ub7ec\ud55c \ubb38\uc81c \ud574\uacb0 \ub2a5\ub825\uc744 \ubc1c\ud718\ud558\uc2e4 \uc218 \uc788\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4.<\/p>\n