# KMP

28개의 포스트

[알고리즘] KMP 문자열 매칭 (**추가작성필요)

Knuth-Morris-Pratt Algorithm, 단순비교 문자열 매칭의 비효율성을 보완한 알고리즘으로 탐색알고리즘의 대표적인 알고리즘이다.단순 문자열 매칭에서 비효율적인 연산량, 특히 모든 경우에 대해 문자열을 비교해야한다는 점에서 단순 문자열 매칭은 사용하지 않

4일 전
·
0개의 댓글
post-thumbnail

[알고리즘] KMP

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략을 보면서 정리한 내용입니다.문자열 N이 문자열 H의 일부인지 확인하기 하고, 일치한다면 그 H에서의 시작 위치를 담는 문제를 문자열 검색 문제라고 한다.예를 들어 H = "ABCDE", N = "BCD"이면 H\[1:

6일 전
·
0개의 댓글
post-thumbnail

☀️ 알고리즘:: KMP 문자열 매칭

KMP 알고리즘은 접두사와 접미사를 활용해 빠르게 문자열 매칭을 수행하는 알고리즘이다

2021년 11월 22일
·
0개의 댓글
post-thumbnail

[Algorithm] KMP(Knuth–Morris–Pratt)알고리즘 java

흔히 문자열검색은 전체문자열의길이가 짧은경우 2중 반복문으로 쉽게구현가능하나,최악의경우 시간복잡도는 (전체문자열길이N) x (찾으려는문자열길이M) 에 비례한 O(NM) 이 된다. 이를 효율적으로 계산하고자 만들어진 KMP알고리즘은 순차적으로 검색하며, 검색 실패할경우

2021년 10월 30일
·
0개의 댓글
post-thumbnail

효율적인 문자열 검색을 위한 KMP 알고리즘

텍스트에서 특정 문자열이 있는지 검색하고 있다면 해당 문자열의 시작 지점을 돌려주는 알고리즘을 만들고 싶다.가장 쉽게 생각할 수 있는 간단한 방법은 브루트포스(brute-force) 검색이다.말 첫 글자에서 시작해서 문자열 길이만큼 문자들을 비교해 일치하는지 확인하고

2021년 10월 24일
·
0개의 댓글
post-thumbnail

BOJ - 1786번 찾기

알고리즘 외로 겪었던 문제, 입력 문제

2021년 10월 21일
·
0개의 댓글
post-thumbnail

KMP 알고리즘 - Knuth, Morris, Prett

빠른 문자열 탐색 KMP 알고리즘

2021년 10월 20일
·
0개의 댓글
post-thumbnail

[개발일지]210924_TIL : KMP 알고리즘

2021년 9월 24일의 TIL : KMP 알고리즘

2021년 9월 24일
·
0개의 댓글
post-thumbnail

[BOJ] 1786 찾기 (Java)

KMPKMP 알고리즘을 그대로 적용시켜 풀면 된다

2021년 9월 23일
·
0개의 댓글

TIL [알고리즘] KMP 알고리즘

KMP 알고리즘

2021년 8월 14일
·
0개의 댓글
post-thumbnail

[백준]#1893 시저 암호

문제암호학에서, 시저 암호(또는 시프트 암호, 시저 코드, 시저 시프트)는 가장 간단하면서 많이 알려진 암호화 기술 중 하나이다. "시저 암호"라는 이름은 비밀 통신을 위해 이 방법을 개발한 율리우스 시저의 이름을 딴 것이다. 시저 암호는 대치 암호의 한 종류로써, 원

2021년 8월 6일
·
0개의 댓글
post-thumbnail

[Algorithm] 🔋백준 4354 문자열 제곱

🔋백준 4354 문자열 제곱 ☕Java 풀이

2021년 7월 6일
·
0개의 댓글
post-thumbnail

[Algorithm] 🔎백준 1786 찾기

🔎백준 1786 찾기 ☕Java 풀이

2021년 7월 5일
·
0개의 댓글
post-thumbnail

KMP 알고리즘

기존의 브루트포스 방식의 문자열 검색의 시간 복잡도인 O(NM) 의 비효율성을 생각하여 만들어진 알고리즘으로 KMP 알고리즘의 시간 복잡도는O(N+M) 으로 매우 빠른 성능을 보여줍니다. KMP 알고리즘에서는 먼저 접두사, 접미사의 개념과 Pi 배열의 개념을 알고 있어

2021년 6월 16일
·
0개의 댓글

(BOJ) 찾기_1786번

문제 https://www.acmicpc.net/problem/1786 문자열 T에 문자열 P가 몇 번 나오는지 출력 문자열 P가 문자열 T의 몇 번째 인덱스에 나오는지 나열 간단하게 말해서 이 두 가지를 구하는 문제이다. 접근 이 문제를 브루트 포스하게 풀게 되

2021년 5월 29일
·
0개의 댓글

[BOJ 1786] 찾기 (Python)

복습 요망!!이 문제의 포인트는 KMP 알고리즘을 사용하는 것이다. 문제의 설명 자체가 KMP 알고리즘의 원리이다. 결국 'KMP 알고리즘을 구현해봐!' 라는 문제의 의도를 파악할 수 있다.KMP 알고리즘이란 주어진 문자열에서 특정한 문자열을 빠르게 찾아내는 방법 중

2021년 5월 12일
·
0개의 댓글
post-thumbnail

KMP 알고리즘(문자열 매칭 알고리즘)

특정한 문자열이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘입니다. KMP에 대해 다루기 전에 먼저 단순 비교 문자열 매칭 알고리즘에 대해 알아봅시다. 단순 비교 알고리즘은 말그래도 하나씩 확인하는 알고리즘입니다. ABCDEF에서 DEF라는 문자열을 찾고

2021년 4월 5일
·
0개의 댓글
post-thumbnail

[백준]#9253 스페셜 저지

문제9249번 문제 (최장 공통 부분 문자열)의 채점 프로그램을 작성하시오.문제의 조건은 동일하다. 편의상 사용자가 출력한 문자열의 길이가 문제의 답과 동일하고, 답은 0보다 크다고 가정한다.입력두 문자열 A 와 B 가 한 줄에 하나씩 주어진다. 두 문자열 길이의 합은

2021년 4월 3일
·
0개의 댓글
post-thumbnail

KMP알고리즘

2021년 4월 3일
·
0개의 댓글