delpho

Think 1. LIS인 이 문제를 보고 고민해보았으나, 풀이 접근 방법이 떠오르지 않음 (이걸 dp로 어떻게 풀지..? 라는 생각) 2. https://st-lab.tistory.com/137 를 참고하여 풀이 방법을 공부함 3. 현재 수열 기준으로 이전 값들을 탐색하며 이전 값이 더 작다면 해당 인덱스의 dp 값 + 1과 현재 dp값을 비교하여 최대값을 저장해준다 4. 해당 풀이법은 시간복잡도가 N^2라고 하며, 이분탐색을 활용하면 NlogN까지 가능하다고 함 제출 코드 (Top-down) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public..

Think 1. 점화식을 잘못 찾아서 틀렸다. 2. https://yinq.tistory.com/68 를 참고하여 풀었다. 3. 예제를 활용하여 점화식을 검토하는 방법이 있다. 4. 문제를 여러 개 풀면서 여러 점화식을 접해보자. 제출 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int n; static Integer dp[]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringT..

Think 1. 점화식이 주어졌기때문에 그나마 간단하게 풀었음. 2. 0의 개수와 1의 개수를 세야하니 처음에는 객체로 풀었음 3. https://st-lab.tistory.com/124 를 보니, 2차원배열로도 풀 수 있다는걸 확인함 객체코드1 (2차원배열 사용) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class test { static int n, t; static Integer dp[][]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.i..

Think 1. DP 분류로 되어있는 문제로 고른거였지만, DP로 풀 방법이 떠오르지 않아 처음에는 단순 재귀로 풀었다. 2. https://lotuslee.tistory.com/43 를 참고해보니, 규칙성이 있다는 점을 확인할 수 있었고, 이를 통해 점화식을 도출하는 부분을 보았다. 3. https://goodmilktea.tistory.com/43 의 글처럼, DP는 (재귀를 적용시킬 점화식) + (종료조건)을 찾는게 관건인 것 같다. 4. 앞으로도 Top-Down과 Bottom-Up 방식을 모두 고려해보자 제출 코드1 (DP) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo..