Algorithm 공부 #27 - KMP알고리즘 ✏️ 단순 문자열 비교 알고리즘 말 그대로 단순히 for문을 돌리면서 문자열을 하나하나씩 비교하는 알고리즘 하지만 이렇게 돌리게 되면 두 문자열의 길이를 n과 m이라고 했을 때 시간복잡도가 O(n*m)이고 n과 m이 1,000,000이상만 넘어가도 많은 시간이 걸리게 되는 단점이 있음 먼저 긴 문자열을 parent(BCDEF)라 하고 찾을 문자열을 DE라고 하면 가장 먼저 찾을 문자열을 parent맨 앞에 위치시키고 비교 => 맞지 않음 다시 인덱스를 한 칸 뒤로 옮겨서 비교 => 맞지 않음 다시 인덱스를 한 칸 뒤로 옮겨서 비교 => 정답 이런 식으로 비교를 하게 되면 짧은 문자열은 상관이 없지만 문자열이 길어질수록 시간이 오래 걸리게 됨 ✏️ KMP 알..
✏️문제 링크 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i~i+m-1번 문자와 P의 1~m www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 문제의 설명이 상당히 길게 나와 있는데 사실 저 말들은 모두 KMP알고리즘의 실패함수 처리 부분과 KMP알고리즘을 구현하는 방법에 대한 설명을 말로 풀어논 것입니다. 따라서 KMP알고리즘을 시행해서 몇 번 나타나는지, 그리고 어디서 일치하는지를 출력하면 됩니다. https://pooreumjung.tistory.com/358 Algorithm 공부 ..
- Total
- Today
- Yesterday
- 투 포인터
- BFS
- 알고리즘 공부
- c++ string
- 우선순위 큐
- Do it!
- 스프링 부트 crud 게시판 구현
- HTML5
- 자바
- js
- java
- 유니온 파인드
- 카운팅 정렬
- 반복문
- DP
- DFS
- 유클리드 호제법
- html
- 에라토스테네스의 체
- 스택
- 알고리즘
- 백준
- 세그먼트 트리
- 자바스크립트
- 이분 매칭
- 자료구조
- C++ Stack
- C++
- CSS
- 백준 풀이
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |