[스터디] 6월 5주차 스터디 면접관 [알고리즘 - 투 포인터, 문자열] - Githubissues

ggjae / Algorithm-CS

🎅 1일 1알고리즘

0 stars 0 forks source link

[스터디] 6월 5주차 스터디 면접관 [알고리즘 - 투 포인터, 문자열] #24

Closed ggjae closed 3 years ago

ggjae commented 3 years ago

문자열

우리가 흔히 사용하는 ctrl+f는 어떻게 문자열을 빨리 찾을 수 있을까?

가장 단순한 알고리즘

패턴을 옮겨가면서 같은지 비교한다. 패턴 문자열 [ABC]를 두고
ABCABABCD 를 검사할 때 ABC------ , -ABC-----, --ABC----, --.... , ------ABC까지 검사하는 것
텍스트의 길이를 N, 패턴의 길이를 M이라 할때 O(NM)의 시간복잡도가 소요된다.

KMP ( Knuth-Morris-Prett Algorithm )

O(N+M)의 시간복잡도로 위 알고리즘보다 빠르다.
접두사와 접미사를 이용하고, prefix와 suffix가 같을 수 있는 부분 문자열 중 가장 긴것의 길이인 pi 배열을 새로 만들어 줌
과연 무슨 차이로 시간복잡도가 이렇게나 차이나는 것일까? => 패턴을 무식하게 찾을 때 얻은 정보들을 하나도 활용하지 않으며 찾게 된다. 처음 비교하였을 때 틀리면 틀린만큼 먼저 이동하면 돼. 미리 전처리 해둔 pi배열을 이용하여 중간시도를 뛰어넘을 수 있음.
아이디어 : 탐색 문자열의 앞부분과 원본 문자열의 뒷부분이 동일한 부분까지는 문자열 탐색을 건너뛸 수 있다
begin 인덱스에 matched를 더해준 뒤 pi[matched-1]을 제거해주게 되면 다음 탐색 위치를 바로 얻음

라빈 카프 알고리즘 ( Rabin-Karp Algorithm )

해시를 이용하여 해시끼리 비교하는 알고리즘 ( 패턴 해시 구하고 계속 반복 돌려 )
mod연산을 사용하여 해시 충돌을 막고 문자열이 매우 커질 경우에는 충돌이 일어날 가능성이 커지므로 불안정하고 비효율적일 수 있지만, KMP보다 빠를 수도 있음.
해시가 같은 경우엔 충돌 발생 여부를 고려하여, 실제로 단순 비교에 들어감
찾았으면 나타내주고, 찾지 못했으면 다시 해시를 진행시킴
구현 자체도 쉽지만 문자열이 길 경우를 대비하여 안정적인 프로그래밍을 진행할 땐 해쉬값에 MOD를 꼭 사용하기 ( 오버플로우가 일어나도 해시값은 동일하다 )
일반적으로 아스키코드를 많이 사용하고 Rabin fingerprint 참조

LCS 적용 (문자열 전체)

문자열 A와 B의 한글자씩 비교해보고, 두 문자가 다르다면 LCS[i][j] 0 표시, 같다면 LCS[i-1][j-1] 값에 +1 합니다. 한글자씩 matrix를 채워나간다고 생각해도 좋다.

LCS 적용 (부분수열)

문자열 A와 B의 한글자씩 비교해보고, 두문자가 다르다면 LCS[i-1][j]와 LCS[i][j-1] 중에 큰 값을 표시하고, 두 문자가 같다면 LCS[i-1][j-1]값을 찾아 +1 한다.
부분수열은 연속된 값이 아니므로, 문자를 비교하는 과정 이전의 최대 공통부분수열은 계속해서 유지됨.
https://www.acmicpc.net/problem/9251

아호코라식 알고리즘 ( Aho-Corasick algorithm )

Keyword Tree, Failure link, Output link을 작성해야 함 각각의 쓰임에 대해 알아보자
Keyword Tree => 여러개의 문자열을 트라이형태로 저장하기
Failure link => 노드별로 실패링크를 만들어 불일치가 발생하면 이전까지 일치한 부분 문자열의 접미사를 접두사로 가지는 B 검색어 노드로 이동하도록 하는 link ( 인덱스 저장 )
Output link => 현재 노드(문자)가 비교중인 텍스트 원소와 일치한다면 이동할 노드 링크
KMP 알고리즘의 확장
트라이가 뭔데?

저장 공간의 크기가 크다는 단점이 있지만, Trie에서 KMP을 사용하는 것이 아호코라식 알고리즘이라고 생각하면 된다.
참조 : https://ansohxxn.github.io/algorithm/ahocorasick/

투 포인터

부분합 문제에서 자주 사용되는 투 포인터

start와 end point를 두고 증가시키는 방향으로 변화시켜 가면서, 부분 배열의 합이 M이 되는 횟수를 구할 때 사용
데이터가 커질수록 투 포인터의 위력이 증가하고 투 포인터의 경우 리스트가 이미 정렬되어 있다면 O(n), 정렬되어 있지 않더라도 O(n log n)으로 문제 해결 가능