LIS12 [백준] 7570번 - 줄 세우기 [Java] https://www.acmicpc.net/problem/7570 1. 아이디어 가장 긴 연속하며 증가하는 번호로 이루어진 부분 수열을 구하고 수열에 해당하지 않는 번호를 적절하게 앞 뒤로 이동시키는 그리디 알고리즘과 다이나믹 프로그래밍으로 해결할 수 있다.2. 문제풀이 dp 배열을 먼저 선언했고 dp 배열은 인덱스에 해당하는 숫자로 끝나는 가장 긴 연속하며 증가하는 부분 수열의 길이를 저장한다.점화식은 dp[idx] = dp[idx-1] + 1 로 연속해야하므로 해당 숫자보다 1 작은 숫자로 끝나는 가장 긴 연속하며 증가하는 부분 수열의 길이 + 1을 해주면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public stati.. 2025. 3. 4. [백준] 2631번 - 줄세우기 [Java] https://www.acmicpc.net/problem/2631 1. 아이디어 옮겨야하는 아이들의 수의 최솟값은 순서대로 있는 아이들의 번호에서 오름차순에 해당하지 않는 아이들만 옮기면 된다. 이때 오름차순은 가장 긴 오름차순에 해당하며 이는 LIS 알고리즘으로 구할 수 있다.2. 문제풀이 N이 최대 200이어서 다이나믹 프로그래밍을 활용한 LIS 알고리즘으로 구현했다. LIS의 길이를 구한 후 처음 아이들의 수에서 빼주면 옮겨야 하는 아이들의 수를 구할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Bu.. 2025. 1. 17. [백준] 13711번 - LCS 4 [Java] https://www.acmicpc.net/problem/13711 1. 아이디어 이분 탐색을 활용한 LIS 알고리즘으로 해결할 수 있다.2. 문제풀이 문제 제목이나 설명과 달리 다이나믹 프로그래밍을 활용하는 일반적인 LCS 알고리즘으로 해결하기에는 수열의 크기가 너무 크다.문제 조건이 특이하게 1부터 N까지의 중복되지 않은 수로 이루어진 두 수열의 LCS를 구하라고 나왔는데 이를 LIS 알고리즘으로 치환해서 생각할 수 있다. 두 수열을 한 줄씩 나열한 후 같은 숫자끼리 선을 이으면 마치 전깃줄처럼 연결되어있는데 이때 이 선들이 교차하지 않게 몇 개를 지웠을 때 만들 수 있는 선의 최대 개수와 동일함을 알 수 있다. 선들은 두 수열의 같은 숫자로 이루어져 있으므로 한 수열을 기준으로 숫자를 앞에서부터 .. 2025. 1. 13. [백준] 2568번 - 전깃줄 - 2 [Java] https://www.acmicpc.net/problem/2568 1. 아이디어 이전 전깃줄 문제에서 전깃줄의 개수와 위치 번호가 늘어난 문제로 O(N^2) 시간복잡도의 다이나믹 프로그래밍으로는 해결할 수 없다. 이를 위해 이분 탐색을 활용한 LIS로 구현했고 해당 전깃줄을 포함하는 LIS의 길이를 저장하는 before 배열을 활용했다.([코딩테스트 준비/백준] - [백준] 2565번 - 전깃줄 [Java])2. 문제풀이 이전 전깃줄 문제에서 LIS 로직만 이분 탐색을 활용하도록 바꿨다. dp 배열에는 Lower Bound 이분 탐색으로 수열의 해당 수가 들어갈 수 있는 위치를 반환하게 해서 dp 배열을 해당 수로 갱신시켰다. dp 배열은 인덱스 숫자와 같은 길이의 LIS의 마지막 원소가 저장된다. 추.. 2025. 1. 13. [백준] 14003번 - 가장 긴 증가하는 부분 수열 5 [Java] https://www.acmicpc.net/problem/14003 1. 아이디어 이전 가장 긴 증가하는 부분 수열 3 문제에서 수열 출력이 추가된 문제로 수열의 해당 수가 dp 배열의 어떤 위치에 저장됐는지 before 배열을 통해 저장 후 이를 역순으로 탐색하는 방식으로 해결할 수 있다.([코딩테스트 준비/백준] - [백준] 12738번 - 가장 긴 증가하는 부분 수열 3 [Java])2. 문제풀이 Lower Bound 이분 탐색으로 LIS 구하는 과정에서 before 배열만 추가가 됐는데 수열의 수가 dp 배열에 저장된 인덱스를 저장했다. 그러면 before 배열에는 수열에서 해당 수를 포함하는 LIS의 길이가 저장되게 되고 이 before 배열을 역순으로 돌며 len과 일치하는 위치를 찾으면 해.. 2025. 1. 13. [백준] 14002번 - 가징 긴 증가하는 부분 수열 4 [Java] https://www.acmicpc.net/problem/14002 1. 아이디어 LIS의 길이와 수열을 구하는 문제로 LIS 출력은 LIS가 갱신될 때 이전 수열의 위치를 저장한 뒤 복원하는 방식으로 구현할 수 있다.2. 문제풀이 이전 가장 긴 증가하는 부분 수열 문제에서 수열 출력이 추가된 문제로 다이나믹 프로그래밍에서 dp 배열의 LIS가 갱신되는 순간 갱신되게 해줬던 수의 인덱스를 before 라는 배열에 저장을 해줬다.([코딩테스트 준비/백준] - [백준] 11053번 - 가장 긴 증가하는 부분 수열 [Java]) 추가로 LIS의 마지막 원소의 위치로 maxIdx라는 변수에 저장해줬다. 수열을 arr 라는 배열에 담았을 때 arr[maxIdx]는 LIS의 마지막 원소가 되고 before[max.. 2025. 1. 13. [백준] 12738번 - 가장 긴 증가하는 부분 수열 3 [Java] https://www.acmicpc.net/problem/12738 1. 아이디어 수열의 길이가 최대 100만 문제로 O(N^2)의 시간복잡도가 소요되는 기존의 다이나믹 프로그래밍 방식으로는 해결할 수 없는데 이분 탐색을 활용하면 O(N log N)으로 해결할 수 있다.2. 문제풀이 이전 가장 긴 증가하는 부분 수열 2 문제에서 수열에 음수도 올 수 있는 조건이 추가된 문제로 수열을 저장하는 dp 배열이 양수만 있는 수열은 0으로 초기화하면 이분 탐색에서 1번 인덱스부터 활용할 수 있었지만 이번 문제는 음수도 존재하므로 dp 배열의 1번 인덱스를 문제 조건의 최소 음수보다 작게 초기화하는 방식으로 구현했다.([코딩테스트 준비/백준] - [백준] 12015번 - 가장 긴 증가하는 부분 수열 2 [Java.. 2025. 1. 13. [백준] 12015번 - 가장 긴 증가하는 부분 수열 2 [Java] https://www.acmicpc.net/problem/12015 1. 아이디어 수열의 길이가 최대 100만 문제로 O(N^2)의 시간복잡도가 소요되는 기존의 다이나믹 프로그래밍 방식으로는 해결할 수 없는데 이분 탐색을 활용하면 O(N log N)으로 해결할 수 있다.2. 문제풀이 Lower Bound 이분 탐색으로 수열을 돌며 해당 수가 dp 배열에 어디에 들어갈 수 있는지 찾는다. dp 배열은 인덱스가 LIS의 길이고 값에 해당 길이의 LIS의 마지막 원소가 들어간다. len은 현재까지 구한 LIS의 길이이다. 이분 탐색으로 얻은 인덱스로 dp 배열을 갱신해주고 만약 인덱스가 len 보다 크면 LIS의 길이가 1 늘어난 것이므로 len을 갱신해준다. 이분 탐색 과정에서 dp 배열의 패딩으로 lef.. 2025. 1. 13. [백준] 11054번 - 가장 긴 바이토닉 부분 수열 [Java] https://www.acmicpc.net/problem/11054 1. 아이디어 앞에서 뒤로 LIS를 구하고 뒤에서 앞으로 LIS를 구하면 간단하게 해결할 수 있다.2. 문제풀이 아이디어처럼 서로 다른 방향으로 LIS를 구한 후 같은 인덱스를 비교해보면 두 LIS의 길이의 합 - 1 이(자기 자신 제외) 바이토닉 부분 수열의 길이가 되는 점을 활용해서 구현했다. 이때 뒤에서 앞으로 LIS를 구해야하고 앞에서 뒤로 LDS를 구하는 것이 아님에 주의해야했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffered.. 2025. 1. 13. [백준] 11722번 - 가장 긴 감소하는 부분 수열 [Java] https://www.acmicpc.net/problem/11722 1. 아이디어 대표적인 LIS 알고리즘 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 이전 가장 긴 증가하는 부분 수열 문제에서 증가만 감소로 바뀐 문제로 안쪽 for문의 비교 부분만 바꾸면 간단하게 구현할 수 있다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeniz.. 2025. 1. 13. [백준] 11053번 - 가장 긴 증가하는 부분 수열 [Java] https://www.acmicpc.net/problem/11053 1. 아이디어 대표적인 LIS 알고리즘 문제로 다이나믹 프로그래밍을 활용해서 해결할 수 있다.2. 문제풀이 dp 배열은 수열과 같은 위치의 인덱스에 해당 수를 포함하는 가장 큰 증가하는 부분 수열의 길이를 저장한다.구현은 2중 for문을 활용하면 간단하게 해결할 수 있는데 첫 for문으로 dp 배열을 쭉 돌고 안쪽 for문은 이전 원소들에 대해 현재 수열의 수보다 작은 수를 발견하면 현재 수의 LIS와 해당 수의 LIS를 비교 갱신하는 방식으로 구현했다.3. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args.. 2025. 1. 13. [백준] 2565번 - 전깃줄 [Java] https://www.acmicpc.net/problem/2565 1. 아이디어 다이나믹 프로그래밍 중 LIS 알고리즘으로 해결할 수 있다.2. 문제풀이 전깃줄을 A 전봇대를 기준으로 위에서부터 번호를 매겼을 때 전깃줄이 교차하지 않는 상태는 전깃줄의 순서가 커질수록 B 전봇대에서의 위치가 같이 커져야 한다. 이를 활용해 A 전봇대 위치를 기준으로 정렬한 후 B 전봇대에서의 위치에 대한 LIS를 구하면 이 값이 서로 교차되지 않고 연결될 수 있는 최대 전깃줄의 수이다.문제는 없애야할 전깃줄의 최소 개수를 구해야하므로 처음 주어진 전깃줄의 수에서 LIS의 크기를 뻬주면 된다.3. 코드 import java.io.*;import java.util.*;public class Main { public s.. 2025. 1. 5. 이전 1 다음
