Category: Algorithm
-
(KOR) 포도주 시식
Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2156 Solution Key Points 계단오르기 문제와 비슷해보였으나, 마지막 잔을 반드시 선택할 필요가 없었던 점에서 차이가 있었다. 풀이방법 dp[n][k] = n번째 와인잔을 골랐을 때, 그것이 k번 연속되었을 경우 마실 수 있는 최대 포도주 양. dp[n][2] 가 아닌 dp[n+1][3]으로 설정한 이유는, dp[i][1]를 구할 때 i-2를 참조해야하므로 dummy 값을 추가해준…
-
(KOR) 쉬운 계단 수
Problem – ⭐️⭐️⭐️ https://www.acmicpc.net/problem/10844 Solution Key Points 2차원 배열을 이용한 다이나믹 프로그래밍이 핵심이였던 문제. 점화식이 바로 떠오르지 않을 경우, f(1), f(2), f(3), .. 하나씩 직접 해보면서 점화식을 도출해내는 것이 좋다. 풀이 방법 dp[n][k] = 끝자리가 k 인 n 자리 수 끝자리가 0, 9 인 경우는 예외적인 경우로 따로 핸들링해준다 int…
-
(KOR) 계단 오르기
Problem – ⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/2579 Solution Key Points 점화식을 떠올리는 과정이 핵심이였던 문제. f(0), f(1)에서 시작해서 f(n)까지 점차 규칙을 찾는 과정이 필요했다. 풀이방법 f(n, k) = n번째 계단에 오를 때 얻을 수 있는 최대 점수. 이 때, n번째 계단은 k번 연속된 계단을 오른 경우이다. g(n) = n번째 계단의 점수 f(n, 0)…
-
(KOR) 정수 삼각형
Problem – ⭐️⭐️⭐️⭐️⭐️ https://www.acmicpc.net/problem/1932 Solution Key Points Using brute-force to calculate all possible solutions resulted in duplicate calculations, causing timeout. To avoid timeout, have to use dynamic programming either Bottom-Up or Top-Down
-
Backtracking
Backtracking is a method that removes child nodes that will not satisfy the condition and go back to parent node to proceed to other child nodes. Usually backtracking is related with DFS, which searches through all the children nodes. Typically, problems that require “Print all” or “Get all” are the…
-
(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
Will the Guru 