[백준 java] 11054 - 가장 긴 바이토닉 부분 수열
11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 내가 푼 방법 가장 긴 증가하는 부분수열과 감소하는 부분수열을 합친 문제이다. 나는 기준점 (idx) 을 잡아 그 기준점보다 낮은 인덱스는 LIS 알고리즘을 그리고 높은 인덱스는 LIS를 뒤집어 사용하여 감소하는 부분 수열을 구현하였다. 10 1 5 2 1 4 3 4 5 2 1 만약 위 예제에서 idx = 3을 조사한다 하면 arr[3]을 기준으로 { 1, 5, 2 } 를 오름차순 긴 부분수열을 구하고, { 2, 1, 4, 3, 5, 2, 1 } 을 내림차순 긴 부분수열을 구한다 이..
[백준 java] 11722 - 가장 긴 감소하는 부분 수열
11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net [백준 java] 11053 - 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부 dwc04112.tistory.com 위 문제와 매우 유사한 문제이다. 이번에도 dp에 해당 숫자로 ..
[백준 java] 11053 - 가장 긴 증가하는 부분 수열
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 최장 증가 부분 수열(Longest Increasing Subsequence) 알고리즘으로 풀 수 있는 문제이다. 어떤 수열이 주어지면 그 수열 내에서 (변형x) 오름차순으로 구성된 가장 긴 수열을 LIS 라고 한다. 이 알고리즘을 사용하기 전에는최소값 index를 구하여 해당 index부터 최장거리를 구하려고 했는데중복되는 최소값이 있으면 길이를 구하지 못해서 바로 틀렸다... [BO..
