메이쁘

https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다� www.acmicpc.net 안녕하세요. 이 문제도 KMP 문제로서, 문자열의 접두사와 접미사의 개수를 활용하는 문제입니다. 필자도 조금 어려워서 고민고민하다 해설을 참고했습니다...ㅠㅠ 결론은 그거입니다. len : 문자열의 전체 길이 pi 배열 : 0 ~ index까지의 부분 문자열의 접두사와 접미사가 같은 그 문자열의 최대 길이 가 있을 때, 제곱 n = len / (len - pi..

https://www.acmicpc.net/problem/1356 1356번: 유진수 첫째 줄에 수 N이 주어진다. 이 수는 2,147,483,647보다작거나 같은 자연수이다. www.acmicpc.net 안녕하세요. 이 문제는 문자열 + 수학 문제이다. int 최대치까지 가능한 자연수를 입력으로 받고, 이 수를 두 부분으로 나눴을 때, 앞 부분의 모든 자리의 곱 과 뒤 부분의 모든 자리의 곱 이 같은지 비교하는 문제이다. 따지면 여러 방법이 있는데 필자의 방법을 포스팅해보겠다. 매커니즘 1. int 배열 A와 B를 입력받은 문자열 크기(len)만큼 선언한다. (문자열은 input 이라고 하자.) 2. for문으로 (1 ~ len-2) 까지 탐색하며, index는 i라고 할 때 A[i] = A[i - 1..

https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 안녕하세요. 이 문제는 단순 문자열 문제가 아니라 정규표현식 문제이다. 자바의 정규표현식 기능을 사용해도 되긴 하지만, 자바 정규표현식 기능을 사용하는 것보다 오토마타 전이 그래프(DFA라고 하죠) 를 직접 그려보는 것 + 오토마타 상태 그래프를 바탕으로 알고리즘을 짜서 코딩하는 것 이 훨씬 빠르고 도움이 된다고 생각되서 이렇게 수행했다. 처음에는 단순히 하나씩 계산하려고 애먹었지만, ..

https://www.acmicpc.net/problem/11944 11944번: NN 첫 번째 줄에는 N, M이 주어진다. (1 ≤ N, M ≤ 2016) www.acmicpc.net 안녕하세요. 문자열 문제인데, 쉬운줄 알고 알고리즘 짠 후 테스트케이스 몇 개 돌려보니 생각보다 몇 개 고려할 것들이 있었다. 고려할 사항은 - N의 문자 개수 * N개 > M 인 경우, 앞에 M개까지만 출력해야 한다. 그렇기 때문에, N의 문자 개수 * M / N개 까지 문자열을 만든 후, 0~M까지 subString 한다. ex) 123 31 output : 1231231231231231231231231231231 (31개) - N의 문자 개수 * N개 만큼 개수 맞춰서 출력하기..? 음.. 별 거 없었구나.. 그렇기..

https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 쉽다. 팰린드롬 문제이지만 다른 팰린드롬 문제들과는 다르게 팰린드롬 알고리즘을 사용하지 않고 정공법(양 끝에서부터 탐색해서 같은지 비교) 만으로 해결했다. 더이상의 자세한 설명은 생략한다. 끗 소스코드

https://www.acmicpc.net/problem/1305 1305번: 광고 첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제도 문자열 탐색 알고리즘인 KMP 알고리즘을 사용한다. 포인트 몇 가지만 알아보자. 1) 광고 문자열은 무한히 반복한다. 2) 무한히 반복하는 문자열 중 일부분만 우리가 확인한다. 3) 그 중, 광고가 될 수 있는 문자열(무한히 반복하는 문자열)이 가능한 경우 중 가장 짧은 문자열의 길이를 구한다. 그럼, 이를 알기 위에선 어떻게하냐? 문자열에서 접두사 - 접미사가 같은 문자열의 최대 길이를 구하면 된다. 접두사와 접미사가 같으면 뭐가되었든 광고 문자열의 ..

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 안녕하세요. 이 문제는 문자열 검색 알고리즘인 KMP의 기본 문제로서 문제에도 노골적으로 O(전체 문자열 길이 + 찾으려는 문자열 길이) 의 시간복잡도로 문자열을 탐색하라고 나와있다. KMP 알고리즘에 대해 알고싶으면 백준 1701번 문제 포스팅을 보고 와도 좋다. https://maivve.tistory.com/203 (JAVA) 백준 1701번 : Cubeditor https://ww..

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 �� www.acmicpc.net 안녕하세요. 처음에 문자열 탐색 문제라고 생각해서 정석대로 문제를 해결하려 했으나 "메모리 초과" ... 이건 아니다.. 먼가 다른 알고리즘이 있을 것이다 해서 몇 번 서치해봤는데 역시나 존재했다. 공부각이다..! 찾아보니, 그것은 바로 KMP 알고리즘 이었다. 간단하게 설명하자면, 그나마 최근에 나온 문자열 탐색 알고리즘 으로, 1) 기본적인 문자열 탐..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 안녕하세요. 그리디 알고리즘 문제로, 난이도는 중 이다. 알아야 할 부분을 정리하자면, - N개의 도시, N-1개의 도로 - 1km -> 1L - 원 안의 숫자 : 리터당 가격. 즉, 1km 당 가격 - 왼쪽부터 순차적으로 이동해야 함 정도가 된다. 문제 해결 방법은 더욱 쉽다. 여기서 구하고자 하는 것은 시작 도시부터 도착 도시까지 이동하는데 드는 최소 비용 이다. 그럼 최소 비용..

https://www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 안녕하세요. 그리디 + 문자열 문제이다. 난이도는 쉬운 편이다. 거두절미하고, 핵심은 "문자열 안에 순서대로 UCPC 가 들어가있으면 I love UCPC, 들어가있지 않으면 I hate UCPC 이다." UCPC가 붙어있지 않아도 되지만, 반드시 앞에서부터 U - C - P - C 순서대로 들어있어야 한다. UCPC를 배열에 넣거나, 다른 자료구조를 사용해도 된다. ***..