It is very important to solve various algorithm problems in preparing for coding tests. In this course, we will develop basic problem-solving skills through the problem of ‘Making an Integer Equal to 1’ and look at the process of designing efficient algorithms. This problem asks for the minimum number of operations needed to turn a given integer into 1.<\/p>\n
Given an integer The goal is to find the minimum number of operations to make There are several approaches to solving this problem. Here we will introduce two methods: DFS (Depth-First Search) and DP (Dynamic Programming).<\/p>\n First, we can consider using DFS to explore all possible paths. However, this approach can lead to a very high time complexity. For example, the number of possible paths can be quite large for The above code explores all possible paths from the given Thus, a more efficient method is to use DP. By using DP, we can store previously computed results and reuse them when needed, reducing unnecessary calculations.<\/p>\n The above DP implementation code uses an array The DFS approach has a time complexity of In this course, we examined various approaches to making an integer equal to 1 and learned efficient problem-solving methods through DFS and DP. Understanding actual algorithms and developing the ability to solve problems based on them are important in preparing for coding tests. Practice learning various approaches to complex problems like this and choose optimized methods.<\/p>\n Try to solve the additional problems below for practice:<\/p>\nN<\/code>, you can transform the number by choosing one of the following three operations:<\/p>\n\n
N - 1<\/code><\/li>\nN \/ 2<\/code> (only possible if N is even)<\/li>\nN \/ 3<\/code> (only possible if N is divisible by 3)<\/li>\n<\/ul>\nN<\/code> equal to 1.<\/p>\nExample Input and Output<\/h2>\n
\n
N = 10<\/code><\/li>\n3<\/code> (10 \u2192 9 \u2192 3 \u2192 1)<\/li>\n<\/ul>\nApproach to Solve the Problem<\/h2>\n
1. DFS (Depth-First Search)<\/h3>\n
N=10<\/code>. Nevertheless, let\u2019s approach it with DFS.<\/p>\nDFS Implementation Code<\/h4>\n
\nimport java.util.HashMap;\n\npublic class Main {\n static int minSteps = Integer.MAX_VALUE;\n \n public static void main(String[] args) {\n int N = 10;\n findSteps(N, 0);\n System.out.println(\"Minimum steps to reach 1: \" + minSteps);\n }\n \n private static void findSteps(int N, int steps) {\n if (N == 1) {\n minSteps = Math.min(minSteps, steps);\n return;\n }\n \n findSteps(N - 1, steps + 1); \/\/ Decrement\n if (N % 2 == 0) {\n findSteps(N \/ 2, steps + 1); \/\/ Divide by 2\n }\n if (N % 3 == 0) {\n findSteps(N \/ 3, steps + 1); \/\/ Divide by 3\n }\n }\n}\n<\/pre>\n<\/div>\nN<\/code>. However, this method has a time complexity of O(3^N)<\/code> due to duplicate calls and inefficient path exploration.<\/p>\n2. DP (Dynamic Programming)<\/h3>\n
DP Implementation Code<\/h4>\n
\npublic class Main {\n public static void main(String[] args) {\n int N = 10;\n System.out.println(\"Minimum steps to reach 1: \" + minStepsDP(N));\n }\n\n private static int minStepsDP(int N) {\n int[] dp = new int[N + 1];\n dp[1] = 0; \/\/ Minimum operations to reach 1 is 0\n \n for (int i = 2; i <= N; i++) {\n dp[i] = dp[i - 1] + 1; \/\/ Decrement\n\n if (i % 2 == 0) {\n dp[i] = Math.min(dp[i], dp[i \/ 2] + 1); \/\/ Divide by 2\n }\n if (i % 3 == 0) {\n dp[i] = Math.min(dp[i], dp[i \/ 3] + 1); \/\/ Divide by 3\n }\n }\n \n return dp[N];\n }\n}\n<\/pre>\n<\/div>\ndp<\/code> to store the minimum steps needed to reach each number. The algorithm has a time complexity of O(N)<\/code>. It calculates the minimum steps by referencing the values of the previous numbers for each number.<\/p>\nTime Complexity Analysis<\/h2>\n
O(3^N)<\/code>, making it very inefficient. In contrast, the DP approach has a time complexity of O(N)<\/code>, which allows for deriving the minimum steps for all numbers with at most one calculation.<\/p>\nConclusion<\/h2>\n
Practice Problems<\/h2>\n