https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 www.acmicpc.net 바로 전에 풀었던 10266 - 시계 사진들과 상당히 유사한 문제 환형으로 이어지는 문자열에서 다른 문자열이 몇번 포함되는지 체크하는 문제이다. 환형을 일일히 구현하기는 상당히 복잡하기 때문에 그냥 문자열 A와 B가 있을때 A를 두번 이어붙인 A' 속에 B가 몇번이나 포함되는지 세면 된다. 몇번이나 포함되는지 세는것은 kmp 알고리즘의 구현에 해당한다. 조심해야할 부분으로써 1 A A 와 같이..

KMP 알고리즘을 장기기억에 남기기위해서 텀을 두고 풀고있다 아직까지는 기억해내는듯 https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시계 바 www.acmicpc.net 시곗바늘의 위치가 36만 등분된 각도값으로 주어질 때, 시계 1번을 적절히 회전하여 시계 2번을 만들 수 있는지 묻는 문제이다. 시곗바늘의 위치를 36만칸 짜리 배열에다 저장해서, 시곗바늘이 있는 곳의 배열 값을 1이라고 했을때 배열을 주우우욱 나열해놓고 보면 0과 1로 만들어진 36만자 짜리 문자열이 된다. 그러면..

오늘의 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을 하나씩 더해가며 계산했지만 시간초과를 받았다. 그렇기때문에 둘 사이의 시..

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