반응형 LIS5 백준 3745번 오름세 - C++ 풀이 1. 가장 긴 증가하는 부분 수열의 길이를 O(nlogn)에 구한다. 1. 가장 긴 증가하는 부분 수열의 길이를 O(nlogn)에 구한다. 가장 긴 증가하는 부분 수열을 구하는 문제이다. n = 10^5이므로 O(n^2)이 아닌 O(nlogn)의 알고리즘을 사용해서 구해야 한다. #include #include #include using namespace std; int LIS(const vector& arr) { vector lis; lis.push_back(0); for (auto x: arr) { if (x > lis.back()) { lis.push_back(x); } else { int lb = lower_bound(lis.begin(), lis.end(), x) - lis.begin(); li.. 2022. 7. 30. 백준 1365번 꼬인 전깃줄 - C++(cpp) 풀이 1. 줄이 꼬이지 않으려면 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다. 2. 잘라내는 전깃줄을 최소로 하려면, 남아있는 전깃줄을 최대로 하면 된다. 3. 가장 긴 증가하는 부분 수열의 길이만큼 남기는 것이 최대이다. 1. 줄이 꼬이지 않으려면 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다. 왼쪽 i번 전봇대와 연결된 오른쪽 전봇대의 번호를 A[i]라고 하면, i A[j]이면 줄이 꼬이게 된다. 반대로 A[i] < A[j]이면 줄이 꼬이지 않는다. 따라서 줄이 꼬이지 않기 위해서는 연결된 오른쪽 전봇대들의 번호가 오름차순이어야 한다. 2. 잘라내는 전깃줄을 최소로 하려면, 남아있는 전깃줄을 최대로 하면 된다. 잘라내는 전깃줄을 최소로 하여 꼬인 부분이 없게 만들어야 .. 2022. 5. 9. 백준 2568번 전깃줄 - 2 - 스위프트(Swift) 풀이 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열을 구한다. 3. (N - LIS길이)가 없애야 하는 전깃줄의 최소 개수이며, LIS에 속하지 않는 전깃줄이 제거해야하는 전깃줄이다. 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2565번 문제에서 제거해야 하는 전깃줄 목록까지 추가로 구하는 문제이다. 기본 원리는 아래와 같다. 백준 2565번 전깃줄 - 스위프트(Swift) 풀이 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열의 길이를 구한다. 3. N - LIS가 없애야하는 전깃줄의 최소 개수이다. 1. 전깃줄 please-amend.tistory.c.. 2022. 2. 7. 백준 2565번 전깃줄 - 스위프트(Swift) 풀이 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열의 길이를 구한다. 3. N - LIS가 없애야하는 전깃줄의 최소 개수이다. 1. 전깃줄들을 A를 기준으로 오름차순 정렬한다. 먼저 (A-B) 쌍으로 이루어진 전깃줄을 A를 기준으로 오름차순 정렬해준다. 전깃줄이 교차하지 않으려면, A 오름차순으로 정렬했을 때 B도 오름차순이어야 한다. A는 증가하는데, B는 감소하면 전깃줄이 교차한다. 2. 1번 결과에서 B만 모아 만든 배열에서 가장 긴 증가하는 부분 수열의 길이를 구한다. 전깃줄을 최소 개수로 제거해서 교차가 없게 만들려면, 남는 전깃줄의 개수를 최대로 만들어야 한다. 즉, 가장 긴 증가하는 부분 수열을 구하면 된다. N이 작기 .. 2022. 2. 7. 백준 11054번 가장 긴 바이토닉 부분 수열 - 스위프트(Swift) 풀이 + 그림 설명 1. 모든 i에 대해 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 LIS[i]를 구한다. 2. 모든 i에 대해 i번째 원소를 첫 번째로 하는 가장 긴 감소하는 부분 수열의 길이 reverseLIS[i]를 구한다. 3. i번째 원소를 기준으로 좌측은 증가하고 우측은 감소하는 가장 긴 바이토닉 부분 수열의 길이는 LIS[i] + reverseLIS[i] - 1이다. 1. 모든 i에 대해 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 LIS[i]를 구한다. 일단 앞 부분에서는 증가를 해야 되기 때문에 LIS를 구해준다. DP를 사용해서 구하면 저절로 모든 i에 대해 i번째 원소를 마지막으로 하는 LIS 길이를 얻을 수 있다. 2. 모든 i에 대해 i번째 원소를 첫번째로.. 2022. 1. 25. 이전 1 다음 반응형
