Algorithm 01 - How to Solve Algorithm Problems on Your Own?

How to Solve Algorithm Problems Independently

To improve your ability to solve algorithm problems, encountering a wide variety of problems is beneficial. However, the skill to solve new problems on your own is equally important. I aim to develop the ability to understand problems and devise appropriate solutions even when faced with unfamiliar challenges.

In this article, I summarize the step-by-step process of solving algorithm problems independently and explore ways to practice effectively and consistently.

---

1. Starting with Problem Analysis

1.1 Understanding the Problem Properly

1. Read the Problem
   • Carefully read the problem statement and clearly identify the input and output conditions.
   • Try solving the given examples manually to better understand the problem’s intent.
2. Ask Key Questions
   • “What am I trying to find?”
   • “What constraints do I have?”
   • “What is the size of the input data?”

Example: “Find combinations of k elements from numbers 1 to n.”

• What to find: Combinations
• Constraints: Choose exactly k numbers
• Input size: Depending on the value of n, consider time complexity.

---

1.2 Breaking the Problem into Smaller Inputs

Use small input values to manually solve the problem and identify patterns. This approach helps you conceptualize the structural flow of the solution.

Example

• Input: n = 4, k = 2
• Manual Calculation: [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]
• Pattern Discovered: Select the current number, then recursively create combinations from the remaining numbers.

---

2. Devising a Solution Strategy

2.1 Analyzing Problem Types

Algorithm problems often fall into recurring patterns or types. When analyzing the problem, what would be the most suitable approach?

Common Problem Types and Strategies

1. Optimization Problems (Dynamic Programming, DP)
   • “When seeking the minimum or maximum value, divide the problem into smaller units and solve.”
2. Exhaustive Search Problems (Backtracking)
   • “Explore all possible choices and eliminate paths that do not meet the conditions.”
3. Search Problems (Graph Search, BFS/DFS)
   • “Search connected nodes in a graph while meeting specific conditions.”
4. Data Organization Problems (Sorting, Binary Search)
   • “Organize data or efficiently search for values in a sorted dataset.”

Example

• Combination generation → Use Backtracking.
• Array-specific sum problem → Use Two Pointers or Backtracking.

---

2.2 Breaking Problems into Smaller Units

Rather than solving the entire problem at once, divide it into smaller units and solve them step by step.

1. Determine Current Actions
   • “Decide whether to select a number or not.”
2. Pass the Problem to the Next Step
   • “After selecting a number, recursively generate combinations from the remaining numbers.”

Example

Problem: Find 2-element combinations from [1, 2, 3].

1. Select the first number: [1] → Generate combinations from [2, 3].
2. Exclude the first number: Empty path → Generate combinations from [2, 3].

---

3. Implementing the Solution in Code

Once you understand the problem and devise a strategy, implement it in code. Start by writing pseudo-code if needed.

Pseudo-Code Example: Combination Generation

1. Create a result list.
2. Recursively explore paths by choosing or not choosing the current number.
3. Add paths with length (k) to the result list.

---

3.1 Debugging and Validation

1. Test with Small Inputs
   • Verify the code’s correctness with simple input values.
2. Test Edge Cases
   • Examples: Empty input, cases where (n < k).

---

4. Training Your Problem-Solving Skills

4.1 Learning Patterns

Familiarize yourself with key patterns while solving problems. Here are common patterns:

1. Dynamic Programming (DP)
   • Solve small problems and use their solutions for larger problems.
   • Examples: Fibonacci sequence, Knapsack problem.
2. Backtracking
   • Explore all possible paths that meet conditions.
   • Examples: N-Queens, Subset generation.
3. Graph Search
   • BFS: Shortest path search.
   • DFS: Exhaustive path search.

---

4.2 Solving Problems by Hand

• Avoid jumping into coding right away. Manually solve simple inputs to identify rules and algorithms.
• This process helps conceptualize and structure the solution.

---

4.3 Review and Feedback

• Revisit solved problems and try alternative approaches.
• Analyze and learn from failed attempts.

---

5. Tips for Easy Memorization

1. Key Questions
   • “Can I break the problem into smaller units?”
   • “What are my current options at this step?”
   • “Can I prune invalid paths?”
2. Memorize Simple Keywords
   • Dynamic Programming: “Divide, Store, Combine!”
   • Backtracking: “Explore and Prune!”
   • Graph Search: “Breadth (BFS), Depth (DFS)!”

---

6. Conclusion

To solve algorithm problems independently, you need to train yourself to analyze problems and devise solution strategies. By learning common algorithm patterns and solving problems step by step, you can expand your problem-solving ability. Although it can be challenging to stay consistent, regular practice will naturally improve your ability to solve even the most difficult problems. Keep pushing forward!