LIS

📖 문제 https://www.acmicpc.net/problem/14002   💡  풀이 방식• LIS (DP) LIS 배열을 만든다.이 때 String 배열을 숫자의 수만큼 만들고, 최장 길이 수열이 만들어졌을 때 수열 정보를 업데이트한다.   🔺 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950import java.util.*;import java.io.*; public class Main {    static int N;    static int[] A, dp;    static String[] str;        public static void main(String[] ..

🔺 문제 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..

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 코드 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 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); i..

🔺 문제 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 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 33 34 35 import java.util.*; import java.io.*; public class Main { static int N; static int[] arr, dp; public static void ..

🔺 문제 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 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 33 34 35 36 37 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException..

📍 정의 및 특징 주어진 수열에서 증가하는 순서로 연속되는 부분 수열 중 가장 긴 길이를 구하는 문제 📍 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 ..

🔺 문제 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 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 33 34 35 36 37 38 39 40 41 42 43 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader b..

🔺 문제 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..