문제https://www.acmicpc.net/problem/10942시간 제한메모리 제한solved.ac 티어0.5초256MB골드 4풀이 문제를 보고 고민하다가 dp임을 깨달은 문제였다. 어떤 문자열이 회문이라면, 양 옆의 문자를 하나씩 떼어내도 회문이다. 예를 들어 12321라는 회문의 양 끝을 떼어보면 232로 회문임을 알 수 있다. 이를 통해 dp점화식을 세울 수 있다. 이 문제에서는 수열이기 때문에, 수열로 바꿔보면, 수열 seq에 대해dp[s][e] = seq[s] == seq[e] && dp[s+1][e-1] 이다. dp[s+1][e-1]은 재귀적으로 구할 수 있다. 또한, 길이 1의 부분수열은 항상 회문이기 때문에, dp[i][i]는 무조건 true이다. 이를 적용하여, [s, e] 구간을..
문제https://www.acmicpc.net/problem/9177시간 제한메모리 제한solved.ac 티어1초256MB골드 4풀이 dfs + dp로 풀었다. 첫번째 단어를 a, 두번째를 b, 세번째를 c라고 하자. c의 첫번째 글자은 a의 첫번째 글자이거나, b의 첫번째 글자일 것이다. 둘다일수도 있다. 현재 사용된 이 알파벳이 a일때와 b일때를 구분해서 계속 dfs로 들어가면서, 최종적으로 c를 만들 수 있는지를 판단한다. dfs를 하면서 지금 사용해야하는 a와 b, c의 인덱스를 인자로 넘겨준다. 이때, 재귀를 하면서 a, b의 같은 인덱스를 여러번 탐색할 수도 있다. 예를 들어, 다른 탐색에서 a와 b의 인덱스가 각각 1, 2일때 불가능함을 알았을때, 다른 경로로 1, 2에 다시 왔다면, 볼 이..
문제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/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알고리즘도 언젠간 정리할 예정이다. 말만 하고 안하고 있는 이유는 알고리즘 정리는 내가 그 알고리즘들에 대해 이해도가 높아졌다고 생각이 들 때 정리할 예정이다. 지금의 나는 여러 알고리즘을 사용할줄은 알지만, 제대로..
