백준 알고리즘 강의 후기(코드플러스): 문자열1 & 문자열2
910 - 문자열 알고리즘 1
문자열 매칭 알고리즘 KMP, 라빈 카프, 해싱, 트라이, 아호 코라식에 대해서 알아봅니다.
1500 - 문자열 알고리즘 2
접미사 배열을 활용한 문제들을 해결해봅니다.
● 백준 코드플러스 알고리즘 강의 후기 - 중급2 - 문자열 알고리즘 1
강의: KMP
문자열 검색 알고리즘
문자열 S에서 패턴 P를 찾는 알고리즘
S에서 가장 먼저 나타나는 P 혹은 모든 P를 찾는 문제이다.
방법1. 모든 경우를 다 해볼경우 O(|S|X|P|) <- 이 방법은 너무 느리다.
방법2. 라빈 카프 알고리즘
라빈 카프 알고리즘
라빈 카프 알고리즘은 해시를 이용하는 것이다.
해시는 정수이고, 정수의 이점을 이용하는것이다.
- 정수의 이점은 비교 시간이 1이다.
- 정수의 또 다른 이점은 배열의 인덱스로 사용할 수 있다는 점이다.
근데 해시값 구하는게 왜 O(M) 일까?
단순 해시 비교는 O(NM) 이어서, 이전 문자열의 해시값을 다음 문자열로 이용할수 있는 방법을 찾아야함.
해시함수가 좋으면 O(N+M)이 나온다, 여전히 최악에는 O(NM)
라빈카프 알고리즘의 해시 함수는 라빈 핑거프린트이다.
256진법으로 각 알파벳들을 계산한다. 123->234로 바뀔때, 23은 간단히 계산하여 치환하고, 4만 더하면 된다.
소수 127을 이용하여 mod연산을 시켜준다.
라빈 카프를 구현할 때는 진법과 소수를 잘 정해서 비교가 최소로 일어나게 구현해야 한다.
이것저것 해보면서, 문제마다 가장 좋은 진법과 소수를 직접 만들어야 한다. 소수를 잘 정하는 방법은 경험과 운동이 필요하다.
KMP 알고리즘
문자열 매핑 알고리즘, Knuth, Morries, Prett의 KMP
KMP는 실패함수(fail)를 이용한다.
- 실패함수: fail[i] = P의 i까지 부분 문자열에서 prefix == suffix 가 될 수 있는 부분 문자열 중에서 가장 긴것의 길이
- prefix 가 P의 i까지 부분 문자열과 같으면 안된다.
26분 실제 시뮬레이션 여기가 중요한듯.
KMP: 문자열 S가 있을 때, 패턴 P를 찾는 알고리즘
강의: Trie
Trie : 문자열 N개가 있을 때, 문자열 S를 찾는 자료구조
N개 문자열을 정렬하는 것은 NMlogN(문자열길이 M인경우)
O(|길이|), depth가 문자열 길이이기 때문이다.
강의: Aho-Corasick
KMP: 문자열 S가 있을 때, 패턴 P를 찾는 알고리즘
Trie: 문자열 N개가 있을 때, 문자열 S를 찾는 자료구조
예) 출석부에서 내 전체 이름을 찾는 경우
Aho-Corasick: 문자열 N개가 있을 때, 패턴 P를 찾는 알고리즘
예) 출석부에서 나랑 성이 같은 사람 혹은 이름이 같은 사람을 찾는 알고리즘
fail[node] = node가 나타내는 문자열 s의 suffix 이면서, trie에 포함된 가장 긴 문자열
910 - 문자열 알고리즘 1
- 부분 문자열
- 찾기
- 광고
- Cubeditor : 여기까지 KMP
- 문자열 집합 : 트라이 이용
- 접두사 찾기 : 트라이에서 찾으면 바로 리턴
- 두 수 XOR : 숫자를 2진수로 바꿔서 트라이 이용, 자리수를 맞춰주기 위해 32비트로 변환한다.
- 문자열 집합 판별
- 돌연변이
11/23 완료
12/9 복습
광고
Cubeditor
두번 이상 등장하는 부분 문자열 중에서 가장 긴것의 길이
-> KMP의 fail 값 중 최대값을 출력하면 됨
-> 그런데 맨 처음부터 시작하는 KMP만 하는게 아니고, 모든 위치에서 시작하는 KMP를 구해야함.
단, 앞에서 부터 모든 위치에 대해 검사하는게 아니고, 뒤에서 부터 한글자씩 추가하면서 수행해준다. 즉, 문자를 먼저 뒤집어 놓고 수행하고 뒤집어서 답을 낸다.
// KMP 강의 끝
911 - 문자열 알고리즘 1 (연습)
912 - 문자열 알고리즘 1 (도전)
● 백준 코드플러스 알고리즘 강의 후기 - 고급1 - 문자열 알고리즘 2
강의: 접미사
Prefix와 Suffix를 먼저 알아봅시다. 한글로는 접두사와 접미사.
접미사의 특징은 정수하나로 표현가능하다는 것. 인덱스를 표현하는 정수가 그 이후 문자 전체를 대표함
접미사배열1,2 문제풀이 포함
강의: 접미사 배열
기존에는 N^2lgN 이었다. 정렬NlgN을 N번하는 방법.
이제 Nlg^2N 하는 방법 알려줌. 정렬 NlgN을 lgN번 반복하는것.
18분쯤에 LCP가 나온다.
접미사 배열에서 LCP는 lgN만에 구할수있으므로 모든 N에 대한것은 NlgN
기수 정렬(Radix Sort)
접미사 중심으로 넣어주는데, 절대 순서가 바뀌면 안된다는것이 주의점이다.
그후에 다시 합치는 것이다.
O(dN), d는 수의 자리수
1500 - 문자열 알고리즘 2
백준 11656 접미사 배열
백준 13013 접미사 배열 2
- 접미사 배열 2 : 접미사강의1, 결과가 있을때 만들수 있는 문자열을 찾는것.
백준 13012 접미사 배열 1
백준 13264 접미사 배열 2
백준 11478 서로 다른 부분 문자열의 개수
중복된것은 빼고 한번씩 세주는 문제, abcd => a, b, c, d, ab, bc, cd, da, ba, cb, dc, ad abc ...
모든 부분 문자열은 suffix의 prefix다.
접미사배열의 정의: 접미사를 정렬한것. 결과적으로 프리픽스가 비슷한것들끼리 뭉쳐있게 되고, 이것이 서픽스의 프리픽스가 된다.
LCP(Longest Common Prefix)를 통해서 이 문제를 해결한다
앞에서부터 얼마나 비슷한지 하나씩 비교해나간다.
LCP구하는데는 N^2걸린다, 문제의 제한은 1000이므로, 가능하다.
백준 11479 서로 다른 부분 문자열의 개수 2
- 서로 다른 부분 문자열의 개수 2 : 두번째 강의에서 다룸 LCP를 lgN에 구하는것이 핵심.
백준 9248 Suffix Array
- Suffix Array : 두번째강의 마지막, SA와 LCP 만으로도 상당히 많은 문제를 해결할수 있으며 이어서 연습슬라이드에서 해보겠다.
두번째강의 마지막, SA와 LCP 만으로도 상당히 많은 문제를 해결할수 있으며 이어서 연습슬라이드에서 해보겠다.
1501 - 문자열 알고리즘 2 (연습)
백준 1701 Cubeditor
백준 1605 반복 부분문자열
백준 5582 공통 부분 문자열
백준 9249 최장 공통 부분 문자열
백준 3789 Hidden Password
백준 13275 가장 긴 팰린드롬 부분 문자열
1502 - 문자열 알고리즘 2 (도전)
백준 12917 문자열 함수 계산
