Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처상자넣기 실버 2 📖 문제 LIS 문제DP, 이분탐색 둘다 풀 수 있다. 최장 증가 부분수열 풀이로 풀면된다. 하다가 찾은 반례 42 4 2 2정답 : 2오답 : 1 🔅 문제 풀이 [DP]import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(S..

🧫 문제 분석 ✔️ 출처가장 긴 증가하는 부분 수열 2 골드 2 📖 문제 가장 긴 증가하는 부분 수열 1에 이어 2문제는 DP로는 불가능하고이분탐색을 통한 대치, 추가를 하여 부분 수열을 만들어 가야한다.  많은 블로그들이 원리를 설명하고 있으므로 생략하고 내가 헷갈렸던 것만 정리한다.  범위 탐색에서 front 무분별하게 front  이문제는 이렇게 풀면 좋지 않다.  근데 이렇게 해서 풀긴했다... ㅋㅋ front 이유는 front == back일때도 탐색함으로써 정확한 탐색이 가능하기 때문이다.  front front = mid + 1;back = mid; 이런식으로 범위를 줄이는데 현재 mid 위치의 값 front는 mid + 1을 하는 이유가 뭘까 라는 의문점이 생겼다. LIS는 증가하는 부..