문제https://www.acmicpc.net/problem/2758시간 제한메모리 제한solved.ac 티어1초128MB골드 4풀이 맨 처음엔 백트래킹으로 접근했지만, 점점 개선하다보니 dp였던 문제. 각 자릿수는 이전 자릿수의 2배여야 하기에, 각 자리에 올 수 있는 숫자의 최댓값은 정해져있다. n=4, m=17이라고 하면 각 자리에 올 수 있는 최댓값은 각각 2,4,8,17이다. 이 최댓값들까지 각 숫자들을 재귀를 이용해 순회하면서 개수를 찾아준다. 같은 예제를 기준으로 설명하면, 맨 처음 숫자는 1부터 2까지 순회하며, 재귀를 통해 각 숫자의 2배만큼의 숫자와, 남은 결정해야하는 숫자를 넘겨준다. f(2, 3)과 같은 식으로 말이다. 하지만 여기서 TLE에 대한 문제가 발생한다. 1 4 8 1..
문제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/3830시간 제한메모리 제한solved.ac 티어2초256MB플래티넘 3 풀이 이 문제는 풀고 기분이 아주 좋았다. 2일 반동안 풀이에 대해 고민했고, 구현을 구체화하며, 그 과정에서 알고리즘에 대한 이해가 조금 오른, 정말 성장했다는 기분을 느끼게 해주는 AC였다. 오랜만에 느끼는 희열이다. 원래 골드 이하 문제를 많이 풀고 있던 나였기에, 이 문제를 보고 처음에는 그래프 최단거리 문제로 접근하고자 했다. 그리고 나름의 최적화를 위해 각 샘플들을 유니온 파인드에 저장하여, 같은 집합이 아니라면 최단거리 탐색을 하지 않도록, 개선하고자 했다. 그래프 최단거리 알고리즘 세가지를 모두 따져보자.플로이드-워셜 : 시간복잡도 O(N^3)에 공간복잡도..
문제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알고리즘도 언젠간 정리할 예정이다. 말만 하고 안하고 있는 이유는 알고리즘 정리는 내가 그 알고리즘들에 대해 이해도가 높아졌다고 생각이 들 때 정리할 예정이다. 지금의 나는 여러 알고리즘을 사용할줄은 알지만, 제대로..
