LIS4 [Problem Solving] BOJ 2361: 줄세우기 문제 링크: https://www.acmicpc.net/problem/2631 LIS를 제외한 나머지 수들의 순서를 맞추면 된다. 라면여기서 LIS는 이다.그러면 나머지는 인데LIS 순서는 유지하고 나머지 숫자 4(7 - 3)개만 움직이면 되므로, 4를 출력하면 된다. #include #include #include #include #include #include #define endl '\n'using namespace std;int N;vector v;vector lis;void input(){ cin >> N; v.resize(N); for (int i = 0; i > v[i]; }}void solution(){ for (int i = 0; i 2025. 3. 4. [Problem Solving] BOJ 3745 : 오름세 문제 링크 : https://www.acmicpc.net/problem/3745 각 테스트케이스마다 LIS의 길이를 구하는 문제이다.LIS 알고리즘 : https://junstory314.tistory.com/entry/Computer-Algorithms-LIS-Longest-Increasing-Sequence-%EC%B5%9C%EC%9E%A5-%EC%A6%9D%EA%B0%80-%EC%88%98%EC%97%B4 #include #include #include #include #include #include #include #include #include #include #define endl '\n'using namespace std;int N;vector p;vector lis;void input(){.. 2025. 2. 17. [Problem Solving] BOJ 2352 : 반도체 설계 문제 링크 : https://www.acmicpc.net/problem/2352#include #include #include #include #include #include #define endl '\n'using namespace std;int N;vector A, LIS;void input(){ cin >> N; A.resize(N); for (int i = 0; i > A[i]; }}void solution(){ for (int i = 0; i 왼쪽 n개의 포트에서 오른쪽 n개의 포트로 연결할 때 교차하지 않는 최대 연결 개수를 구하는 문제이다. 생각해보면 교차한다는 것은 오른쪽에서 연결되는 포트의 번호가 내림차일 때다. 그렇다면 교차 하지 않는 최대 연결 개수는 .. 2024. 8. 4. [Computer Algorithms] LIS (Longest Increasing Subsequence, 최장 증가 부분 수열) LIS (Longest Increasing Subsequence)말 그대로 가장 긴 증가하는 부분 수열이다. 수열에서 LIS를 구하는 방법은 두 가지가 있다.1. DP를 이용한 방법 -> 시간 복잡도 O(N^2)2. 이분 탐색을 이용한 방법 -> 시간 복잡도 O(N * logN) Finding LIS using DP- LIS의 길이 구하기 (DP)문제 링크 : https://www.acmicpc.net/problem/11053#include #include #include #include #include #include #define endl '\n'using namespace std;int N;vector A, DP;int maxVal = 0;void input(){ cin >> N; A.r.. 2024. 8. 3. 이전 1 다음