최장 증가 수열 2

[알고리즘] 백준 11054 자바 JAVA 동적프로그래밍 LIS 최장 증가 수열

이 문제는 11053문제 바로 뒤에 나오는 문제이다. 다만 가장 큰 값을 중심으로 왼쪽과 오른쪽으로 값이 작아지는 그 부분 수열의 길이를 알아야하는 문제이다. 처음에 접근 방식은 먼저 가장 긴 증가 부분 수열 방식으로 값을 셋팅해놓고, 큰 값과 그의 인덱스를 저장한 뒤, 그 인덱스부터 가장 긴 감소 부분 수열 방식으로 다시 검색하는 방식으로 진행했었는데, 될 법 한데 자꾸 예외에 부딪히고 코드가 읽기 힘들어졌다. 어찌어찌하면 될 것 같은데 동적프로그래밍의 특성을 제대로 활용하고 싶다고 가정한다면 좋은 접근 법은 아니다. 그렇다면 좋은 접근 법은 무엇이냐? 1. 가장 긴 증가하는 부분 수열을 통해 먼저 카운팅한다. 2. 가장 긴 감소하는 부분 수열을 통해 카운팅을 한다. 3. 합치고 -1한다. 코드를 보자..

알고리즘 2020.10.20

[알고리즘] 백준 11053 자바 JAVA 동적프로그래밍 LIS 최장 증가 수열

정말 알것 같다 싶으면 새로운 유형이 나와버리는 동적프로그래밍이다! 조금씩 익숙해지고는 있지만 자잘한 조건에 난감한 경우가 많다. 이 문제는 LIS문제이다. 이걸 처음 접하면 이게 왜 동적 프로그래밍 문제지? 하고 의문을 가지고 내 식대로 풀다가 망하는 경우가 100% 된다. 망하는 이유는 문제를 정확히 이해하지 못했기 때문이다. 아래는 문제에서 주어진 조건이다. 6 10 20 10 30 20 50 이렇게 보면 그냥 처음부터 max값을 찾아서 10 20 넣고 10은 건너뛰고 30넣고 20은 건너뛰고 50넣고.. 이렇게 하면 될것 같다. 그래서 아래는 그렇게 짠 코드이다. public class BaekJoon_16_11053_2 { public static void main(String[] args) t..

알고리즘 2020.10.20