오늘의 KMP 그 두번째 문제 https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 반복되는 가장 작은 문자열의 길이를 https://blog.koderpark.dev/263 1305번 풀이와 동일하게 구해준 다음, ( 문자열의 길이 / 반복되는 가장 작은 문자열의 길이 ) 로 구해줄 수 있다. 이때, 코너케이스가 있는데, 나눈 나머지를 보는 방법도 있다고 하지만 나는 그냥 입력받은 문자열을 두배로 이어붙여서 나온..

@이화월백 이 골라준 태그 문제풀이 오늘의 태그는 KMP되시겠다 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net KMP 알고리즘의 실패함수 개념에 대한 이해를 필요로 한다. KMP 알고리즘에서 전처리로 사용되는 실패함수의 값 Fail[K] 는 처음부터 시작하는 길이 K+1짜리 부분 문자열에서 접두사와 접미사가 같아지는 최대 길이 라는 의미를 지닌다. for(int i=0,j=1; j0 && s[i] != s[j]) i = fail[i-1]; if(s[i] == ..

플래는 될줄 알았는데 웰노운이라서 골드1이란다 ㅠㅠ 세상 말세다 정말 엉엉엉 다익스트라 문제인데 그래프 가중치를 시간으로 생각해주면 된다. 저장된 최단거리가 최단시간에 도착하였을 경우의 시간이 되는 셈. 횡단보도 불이 들어올때까지 기다릴 수 있기 때문에, 당장은 가지 못하는 도로이더라도 처리를 해줘야 한다. while(dist >= ndist) ndist += M; if(dist > ndist)ndist += (ll)ceil((double)(dist-ndist)/M)*M; 아이디어는 대략 위와 같은데, 처음 K초에 지날수 있게 되는 다리는 K+M초, K+2M초, K+3M초 등등.... 에 다시 지날수 있게 되므로 첫번째 줄에서 M을 하나씩 더해가며 계산했지만 시간초과를 받았다. 그렇기때문에 둘 사이의 시..

다익스트라 알고리즘의 활용 문제 처음에는 각 면접장마다 다익스트라를 K번 돌리려고 생각했었는데, 이 경우에는 면접장의 개수가 많기 때문에 TLE를 받게 된다. 다익스트라를 한번만 돌리되 처음에 넣는 노드를 K개 넣어주어야 한다. 모든 면접장과 거리 0으로 연결되는 가상의 도시를 하나 만든다고 생각해도 무난하다. 다익스트라를 돌리고 난 뒤의 거리는 각 도시에서 가장 가까운 면접장으로 가는 거리값과 같으므로 이 거리 배열을 순회하면서 최대값을 구해주면 AC를 받을 수 있다. 이때 주의해야 할 점은 탐색방향이 반대가 되므로 방향그래프의 방향도 모두 뒤집어줘야한다는점? 이거때문에 좀 고생좀했습니다. 그리고 범위가 int범위를 넘어갈수있으니 long long 형을 사용해주도록 하자. #include #define..

재활 3일차 시뻘건 문제를 잡아보았다. https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 트라이 자료구조형을 활용해야 하는데 단순히 포함여부만을 물어보는 문제가 아니라서 티어가 좀 높게 책정된 것 같다. 사용자의 입력이 필요한 경우가 1. 트라이 자료구조 내부의 트리에서 자식노드가 두개 이상 있을때 2. 자식노드가 한개 있는데 해당 노드가 문자열의 끝인 경우 2번 경우가 좀 비 직관적일수도 있을것 같은데 음 원하는 문자열의 끝까지 온 경우 / 다른 문..

트라이 자료구조를 사용하는 문제. https://www.acmicpc.net/problem/7432 7432번: 디스크 트리 갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파 www.acmicpc.net \ 기호를 기준으로 문자열을 토큰화 해서, 이 토큰화된 문자열들이 들어가는 trie 자료구조를 만들어 준다음 얘를 dfs로 순회하면서 출력해주면 정답을 받을 수 있다. trie 자료구조에 저장할때 std::map을 사용했는데 자동으로 정렬되면서 각 서브 디렉토리는 사전순으로 출력해야 하며, 를 충족시킬 수 있다. 더보기 #include using namespace ..