[알고리즘] 가장 긴 증가하는 부분수열(LIS)
※ 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence)이란? 부분 수열 중에서 각 원소가 이전 원소보다 큰 부분 수열 중에서 가장 긴 것! 예를 들어서, { 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 때, 증가하는 부분 수열은 { 2, 5 }, { 1, 4, 3} 등이 있지만 LIS는 { 2, 5, 7, 8 } 이다! 알고리즘은 시간복잡도에 따라서 2가지가 있다. ( O(N^2)과 O(N log N) ) 첫 번째 방법은 다이나믹 프로그래밍을 통한 방법이다. 시간 복잡도는 O(N^2) code#1 1 2 3 4 5 6 7 for (int i = 0; i arr[i]; } dp[0] = arr[0]; int idx = 0; for (int i = 1; i
2021. 6. 23.
[C++] 백준 11054번 : 가장 긴 바이토닉 부분 수열
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 풀이 바이토닉 수열은 LIS의 변형으로 커지면서 작아지는 부분 수열이다. k번째를 기준으로 오르내림이 바뀌므로 정방향으로 LIS를 구하고 역방향으로 LIS를 구해서 DP 값을 따진다. 여기서 주의할 점은 각 DP를 더한 값 중 가장 큰 값을 -1을 해야 한다는 점인데, 이유는 중복돼서 그렇다. 예를 들면, 문제 속 수열 { 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 }에서 각 LIS는 정방향 : { 1..
2021. 6. 23.
[C++] 백준 14003번 : 가장 긴 증가하는 부분 수열5
https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 접근 LIS 4번 문제와 다른 점은 인풋의 갯수와 크기 뿐이다. 따라서 이전과 동일하다. 코드 #include using namespace std; int n; int arr[1000001], dp[1000001], p[1000001]; int binary(int left, int right, int key) { int mid; while (left = key)..
2021. 6. 22.
[C++] 백준 14002번 : 가장 긴 증가하는 부분 수열4
https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 LIS 1번 문제에서 다음 버전으로 LIS의 길이와 LIS 자체를 출력해야한다. 배열 L은 LIS의 길이를 구하기 위한 배열이고 배열 P는 arr의 원소들의 lower_bound를 저장하는 배열이다. 함수 Backtrace는 배열 P에 저장된 lower_bound로 LIS를 출력하는 재귀함수이다. P[i]..
2021. 6. 22.
[C++] 백준 12738번 : 가장 긴 증가하는 부분 수열3
https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 풀이 이전 문제와 다른 점은 입력 값이 음수 범위도 포함한다는 점이다. 하지만 코드 자체는 차이가 없다. 코드 #include using namespace std; int n; int arr[1000001], dp[1000001]; int binary(int left, int right, int key) { int mid; while (left = key) ri..
2021. 6. 22.