Will the Guru

Category: Backtracking

  • Palindrome Partitioning

    Problem https://leetcode.com/problems/palindrome-partitioning/description/ Solution

  • (KOR) 스타트와 링크

    Problem https://www.acmicpc.net/problem/14889 Solution Note

  • Generate Parentheses

    Problem https://leetcode.com/problems/generate-parentheses/ Solution

  • (KOR) 블랙잭

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2798 Solution Key Points Iteration, Recursion 둘 다 연습해 볼 수 있는 좋은 문제. 주어진 배열을 우선 sort 한 후 sum을 계산하는 것이 더 시간효율적이다. 작은 수 더했을 때 M보다 크면 큰 수 더하는 작업은 해보나 마나 이기 때문. Recursion 의 경우 백트래킹의 수도코드처럼 isValid 할 경우만…

  • (KOR) 로또

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/6603 Solution Key Points To avoid using the numbers that’s already used, the iteration under backtracking method should start from idx , not 0. ex) for(int i=idx;i<numList.size();i++){ StringBuilder is much faster than System.out.println

  • (KOR)연산자 끼워넣기

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/14888 Solution Key Points For backtracking method, we need to pass the changed value like the res or numIdx to recursive method as an argument. For full search problems, it’s likely to use DFS

  • (KOR) 스도쿠

    Problem – ⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2580 Solution Key Points Using an array list (zeroList) which stores all empty nodes. Using this, we only need to iterate through this list, NOT the whole grid(9×9). This helps avoid Timeout error. Using a flag(isEnded) to escape when we found the solution. This is required because…

  • (KOR) N-Queen

    Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/9663 Solution Key Points The solve method did not require nested for loops like for(int i=0;..){ for(int j=0..){.Instead, we could just pass ‘row’ as an argument and check that row only, because each row can only have 1 Queen at maximum.

  • (KOR) N과 M(4)

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/15652 Solution Key Points Use StringBuilder to print all outputs instead of System.out.println Backtracking removes the case that we already checked

  • (KOR) N과 M(3)

    Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/15651 Solution Key Points Use StringBuilder to print all outputs instead of System.out.println Backtracking removes the case that we already checked