가장 긴 증가하는 부분 수열1 백준 14003 JAVA - 가장 긴 증가하는 부분 수열 5 (BOJ 14003 JAVA) 문제 : boj14003 8달전에 못풀고 키핑해뒀던 문제인데, 이번에도 못풀 뻔 했다가 겨우 풀었다. 확실히 플래는 아직 많이 까다롭다. 일단 가장 긴 증가하는 부분 수열의 길이 자체는 이분탐색을 활용한 LIS 알고리즘을 쓰면 얻을 수 있다. 하지만 LIS 알고리즘은 가장 긴 증가하는 부분 수열의 '길이'를 파악할 뿐이고, 이 문제에서는 가능한 수열 중 하나를 출력하는 방법도 찾아야 한다. LIS 알고리즘은 나름대로 잘 알려진 알고리즘이므로 제외하고, 수열 자체를 찾는 방법에 대해 써보겠다. 1. LIS 알고리즘에서 입력이 10 20 30 5 15 가 들어오면 어떻게 될까? 최종적으로 LIS의 길이인 '3'은 구해낼 수 있으나, 배열에는 다음과 같이 '5 15 30' 이라는 값이 들어가 있게 된다. 실제.. 2021. 12. 8. 이전 1 다음
