[백준 12738: JAVA] 가장 긴 증가하는 부분 수열 3/ 이분 탐색
개요 이 문제는 2가지 정도의 풀이가 존재한다. 1. 동적 프로그래밍 2. 이분 탐색 하지만, 이 문제의 입력에서 n의 값이 1,000,000 이기 때문에 이분 탐색으로 풀이하여야 시간 초과를 피할 수 있다. 간단히 설명하자면 우리가 구하고자 하는 증가 수열을 List 자료구조에 저장하고 새로 들어온 값에 대해서 list 안에서의 위치를 찾아 list를 갱신해주는 것이다. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 풀이 개요에서 말했듯이 이분탐색을 이용해서 수열의 적당..
[백준 14002: JAVA] 가장 긴 증가하는 부분 수열 4/ 동적 프로그래밍 + 역추적
개요 이 문제는 dp와 이분 탐색으로 풀이할 수 있다. 하지만 문제의 입력의 최댓값이 1000이기 때문에 나는 dp로 풀이할 것이다. dp로 풀이할 때는 이전에 구한 값을 통해 풀이하게 된다. 또한 시간은 O(n^2)이 될 것이다. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 풀이 dp[i] = k → i번째 수열까지의 최대 증가수열의 길이 = k 라고 생각하고 접근하면 된다. 예를 들어 수열 {1, 2, 1, 3, 4, 3}이 주어지고 인덱스가 1부터 시작하여 6까지 ..
