https://www.acmicpc.net/problem/22963 22963번: 3초 정렬 원래 수열인 A = [6, 7, 10, 8, 20]의 4번째 원소인 8을 15로 바꾸면 A = [6, 7, 10, 15, 20]이 되어 오름차순으로 정렬된 배열이 된다. 3번째 원소인 10을 8로 바꾸어도 A = [6, 7, 8, 8, 20]이 되어 오름차순으로 정 www.acmicpc.net 처음 보고 든 생각은 lis였고, lis에 포함되지 못한 값들을 적당히 변경하면 오름차순으로 만들수 있지 않을까 생각. https://blog.koderpark.dev/191 백준 BOJ 14003 - 가장 긴 증가하는 부분 수열 5 https://www.acmicpc.net/problem/14003 14003번: 가장 긴..

nlogn lis의 경로추적 반전 문제. https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net lis잘 구해서 역추적 해준 다음에 역추적해서 나온 값들 정렬해주고 입력 배열과 비교해가며 없는애들을 따로 관리해주면 된다. #include #define INF 123456789 using namespace std; vector lis; vector v; vector back; int chk[567890] = {0}; int conv[567890] =..

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 nlogn구현과 함께 역추적이 가능한지를 묻는 문제였다 일단 처음으로 문제에 접근했던 방법은 각 자리 lis배열의 최솟값을 저장하는건데 이건 WA가 나왔었고, 반례를 접하고 나서의 접근은 일단 lis의 그 끝 값을 구성하는 수가 나온 뒤에 이보다 작은 값이 나올때 순서대로 채워나가는 것이었다. 즉 for문을 통해 역순회하면서 정답 배열또한 역순으로 채워주면 된..

LIS NlogN 연습의 전형적 형태 입력이 간단해서 쉬웠다. https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 풀이방법은 정말 lis 구현밖에 없다.... #include #define INF 123456789 using namespace std; vector v; vector in; int main(){ int n,tmp; scanf("%d", &n); for(int i=0; i

오버킬 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net lis의 nlogn이 주제였으므로 의도치않게 오버킬을 했다. 입력받은 값을 pair에 넣고 정렬 후 lis구하기. #include #define INF 123456789 using namespace std; vector v; vector input; int main(){ v.push_back(-INF); int n,a,b; scanf("%d", &n); for(int i=0; i

일단 나는 이 문제를 LIS nlogn 구현 문제 밀다가 발견한거기 때문에 알고리즘 접근에 있어서의 문제는 없었다. https://www.acmicpc.net/problem/13711 13711번: LCS 4 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] www.acmicpc.net https://jason9319.tistory.com/113 [최장 증가 수열] LIS(Longest Increasing Subsequence) 이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보..