문제https://www.acmicpc.net/problem/12015시간 제한메모리 제한solved.ac 티어1초512MB골드 2풀이https://codejin.tistory.com/314 백준 11053번 C++ 풀이문제https://www.acmicpc.net/problem/11053시간 제한메모리 제한solved.ac 티어1초256MB실버 2풀이 밀린 문제 정리하기. 이번엔 LIS 알고리즘이다. 뭐 사실 dp의 특수형태라고도 할 수 있는데, LIS는 Longest Increasicodejin.tistory.com
문제https://www.acmicpc.net/problem/14003시간 제한메모리 제한solved.ac 티어3초512MB플래티넘 5풀이 밀린 문제는 아니고 오늘 푼 문제이다. 문제 이름이 LIS니까 이 문제도 LIS이다. 다만, LIS를 역추적하는 문제이다. 2568번 문제를 설명하는 이전 글에서 간략하게 설명했고, 알만한 사람들은 알겠지만, LIS알고리즘은 LIS 자체를 구하는 것이 아닌 LIS의 길이를 구하는 알고리즘이다. 그렇기 때문에 dp 배열을 하나 더 선언하여, 해당 dp 테이블을 역순회하면서 LIS를 다시 찾아가는 방식을 사용한다.코드#include #define ALL(X) X.begin(), X.end()using namespace std;int n;vector arr;void in..
문제https://www.acmicpc.net/problem/2568시간 제한메모리 제한solved.ac 티어1초128MB플래티넘 5풀이 밀린 문제 정리하기... 라고 하기엔 너무 최근에 푼 문제라서 밀렸다고 해야하나 싶다. 여행가기전에 풀었던 마지막 문제이자, 알고리즘에 대한 이해도를 높여야겠다고 절실하게 느낀 문제이다. 문제 자체는 이전에 풀었던 전깃줄 - 1(2565번, https://codejin.tistory.com/316)과 다를게 없는 문제이다. 다만 포트의 개수와 번호가 천배 늘어났으며, 출력해야할 답이 늘어났다 정도이다. 없애야할 전깃줄의 개수를 구하는건 전깃줄 - 1과 다를게 없지만, 잘라야 하는 전깃줄의 데이터도 출력해야한다. 결국 우리는 실제 LIS를 구해야한다는 것인데, 문제는..
문제https://www.acmicpc.net/problem/2565시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이 밀린 문제 정리하기. LIS이다. 저번 반도체 설계(2352번, https://codejin.tistory.com/315)에서 한번 더 문제를 꼬아버렸다. 이번에는 LIS를 적용하기 위한 수열도 만들어야 한다. 말은 거창하지만 별거 없으니 한번 출발해보자. 해당 문제 여기 전깃줄이 꼬이지 않도록(교차하지 않도록) 하는 최대 개수를 구하는 문제이다. 그와 동시에 A에서 B로 연결해야하는 전선의 포트 정보를 같이 준다. 2352번을 해당문제에 적용시켜보면 A -> B로 연결되는 정보가 단순했다. A의 정보는 1부터 n까지 오름차순이고, B로 연결될 때 뒤죽박죽이었기 때문이..
문제https://www.acmicpc.net/problem/2352시간 제한메모리 제한solved.ac 티어2초128MB골드 2풀이 밀린 문제 정리하기. 이번에도 LIS이다. 해당 문제를 요약하면 왼쪽 포트에서 오른쪽 포트로 연결되있는 연결선이 꼬이지 않도록 최대한 많이 연결할 때, 연결선의 개수를 구하는 문제다. 문제 설명이 이래서 그렇지 결국 연결되어야 하는 포트에서 LIS를 찾으면 그것이 최대 길이이자 답일 것이다. LIS이기 때문에 중간에 연결선이 교차될리가 없고, 최대 개수를 구하기 때문이다.코드#include #define ALL(X) X.begin(), X.end()using namespace std;int n;vector arr;void input() { cin >> n; arr.res..
문제https://www.acmicpc.net/problem/11053시간 제한메모리 제한solved.ac 티어1초256MB실버 2풀이 밀린 문제 정리하기. 이번엔 LIS 알고리즘이다. 뭐 사실 dp의 특수형태라고도 할 수 있는데, LIS는 Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열의 약자이다. 말 그대로 전체 수열 S가 주어졌을 때, 이중에서 원소가 증가하는 순서대로 부분 수열들을 구했을 때, 이중에서 가장 긴 부분 수열을 구하는 문제이다. LIS알고리즘도 언젠간 정리할 예정이다. 말만 하고 안하고 있는 이유는 알고리즘 정리는 내가 그 알고리즘들에 대해 이해도가 높아졌다고 생각이 들 때 정리할 예정이다. 지금의 나는 여러 알고리즘을 사용할줄은 알지만, 제대로..
