![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/loFZr/btsGJdrNa0k/14OpoKYvTJKR3kB4tUa4kk/img.jpg)
Algorithm 공부 #27 - KMP알고리즘 ✏️ 단순 문자열 비교 알고리즘 말 그대로 단순히 for문을 돌리면서 문자열을 하나하나씩 비교하는 알고리즘 하지만 이렇게 돌리게 되면 두 문자열의 길이를 n과 m이라고 했을 때 시간복잡도가 O(n*m)이고 n과 m이 1,000,000이상만 넘어가도 많은 시간이 걸리게 되는 단점이 있음 먼저 긴 문자열을 parent(BCDEF)라 하고 찾을 문자열을 DE라고 하면 가장 먼저 찾을 문자열을 parent맨 앞에 위치시키고 비교 => 맞지 않음 다시 인덱스를 한 칸 뒤로 옮겨서 비교 => 맞지 않음 다시 인덱스를 한 칸 뒤로 옮겨서 비교 => 정답 이런 식으로 비교를 하게 되면 짧은 문자열은 상관이 없지만 문자열이 길어질수록 시간이 오래 걸리게 됨 ✏️ KMP 알..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/csdq5b/btsGJpMg7jV/fUQhlkvi36PRAsFPA6HEfK/img.png)
✏️문제 링크 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 일단 문제를 보기에 앞서 두 수를 a, b 라 하면 a와 b의 최대공약수는 m=gcd(a,b)이고, 최소공배수는 a*b/m입니다. 즉 문제에서 최대공약수와 최소공배수가 주어지는데 정답으로 출력하고자 하는 두 개의 자연수의 곱은 최대공약수 * 최소공배수가 되어야 합니다. 이는 최소공배수와 최대공약수를 구하는 식을 보시면 당연한 결과입니다 int형으로 하면 ..
- Total
- Today
- Yesterday
- Do it!
- C++
- 자료구조
- 투 포인터
- 에라토스테네스의 체
- 알고리즘 공부
- 백준 풀이
- C++ Stack
- html
- js
- DFS
- 이분 매칭
- 최단 경로
- 유니온 파인드
- CSS
- java
- 유클리드 호제법
- BFS
- HTML5
- c++ string
- 스택
- 백준
- 자바스크립트
- 자바
- 세그먼트 트리
- 카운팅 정렬
- 우선순위 큐
- 알고리즘
- 반복문
- DP
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |