[백준] 4354 문자열 제곱 - KMP(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net ​ 📕 문제 접근 📕 - 굉장히 난처했던 문제 였다. - 문제 이해가 어려웠는데 정말 간단하게 설명하자면 ababab에서 최대 접미사 접두사의 반복 길이는 abab로 4이다 - 그치만 해당 문제가 요구하는것은 반복되는 문자열이 몇개의 반복으로 이루어져 있냐는 것이였다. - 예를 들면 ABCD의 경우 반복되는 것 없기에 ABCD의 1제곱이다. - 다음..

• format_list_bulleted JAVA/Algo 풀이
• · 2023. 8. 6.
• textsms

[백준] 1305 광고 - KMP(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net ​ 📕 문제 접근 📕 - 해당 문제도 KMP 알고리즘을 사용한다(?). - 개인적인 생각으로는 KMP를 위한 table만 설계하면 끝난다고 생각하여 반쪽짜리 KMP 느낌이 든다. 포인트 1) 광고 문자열은 무한히 반복한다. 2) 무한히 반복하는 문자열 중 일부분만 확인하다. 3) 그광고가 될 수 있는 문자열(무한히 반복하는 문자열)이 가능한 경우 중 가장 짧은 문자열의 길이를 구한다. 문자열에서 접두사..

• format_list_bulleted JAVA/Algo 풀이
• · 2023. 8. 5.
• textsms

[백준] 1786 찾기 -KMP(JAVA)

문제링크 🚩 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net ​ 📕 문제 접근 📕 - 가장 이상적인 KMP문제인 것 같다 - 접미사와 접두사가 같은 영역을 찾기 위한 table을 만들고 - 이를 KMP 알고리즘에 대입하여 해결하면 되는 문제다 - KMP 알고리즘은 해당 포스팅에 자세하게 정리해뒀으니 참고 바란다. https://security-gom.tistory.com/36 KMP -JAVA KMP Algorithm : 문자열 검색 알고..

• format_list_bulleted JAVA/Algo 풀이
• · 2023. 8. 5.
• textsms

KMP -JAVA

KMP Algorithm : 문자열 검색 알고리즘 💡 **특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘. 워드 파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다.** 1. 단순 문자열 알고리즘 가장 간단한 문자열 매칭 알고리즘으로, 말 그대로 하나씩 확인하는 방법을 사용한다. 검색할 문자열 : ABDEGH 찾는 문자열 : DE 가장 앞 부분부터 찾는 문자열이 매칭될 때까지 탐색을 시작한다. 매칭이 이루어지지 않았다면 한 칸씩 옆으로 이동시킨다. 매칭이 이루어졌으면 탐색을 종료한다. 위와 같은 예시가 아닌, “A B A C A A B A”를 검색하는 패턴이 “A B A C A B”인 경우에서는, 불필요한 연산이 다시 진행되는 경우도 ..

• format_list_bulleted JAVA/Algo 개념
• · 2023. 8. 5.
• textsms