최장증가부분수열

🔺 문제 Softeer - 현대자동차그룹 SW인재확보플랫폼 남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지 softeer.ai 🧩 해결 아이디어 • DP (최장 증가 부분 수열) for문을 돌리며 다음 돌 arr[i]이 현재 돌 arr[j]보다 높을 때, 둘 중 더 큰 값을 찾아 dp[i]에 값을 넣는다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 import java.io.*; import java.util.*; public clas..

📍 정의 및 특징 주어진 수열에서 증가하는 순서로 연속되는 부분 수열 중 가장 긴 길이를 구하는 문제 📍 LIS 실행 방법 1) DP 활용 → 시간 복잡도 : O(N^2) 2) 이분 탐색 활용 → 시간 복잡도 : O(N log N) 📍 필요 변수 ✔ DP / LIS 배열 🧩 1) DP를 활용한 LIS 실행 과정 : O(n^2) DP 테이블을 생성하여 각 원소를 마지막으로 하는 LIS의 길이 저장 초기값으로 모든 원소의 LIS 길이를 1로 설정 각 원소 i에 대해, 이전 원소 j(0 nums[j]인지로 판단) 만약 nums[i] > nums[j]라면, dp[i] = max(dp[i], dp[j] + 1) 수행 ⇨ i번째 원소를 마지막으로 하는 LIS의 길이 갱신 모든 i에 대해 위 과정을 반복하면, dp ..

🔺 문제 11054번: 가장 긴 바이토닉 부분 수열첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)www.acmicpc.net  🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859import java.util.*;import java.io.*; public class Main {    static ..

🔺 문제 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Bu..