코딩인터뷰 퀘스천"메모" 검색,해싱,문자열 알고리즘

.

.

책 읽으면서 메모했던 내용들 옮겨봅니다.

​

-

챕터11 검색

불규칙 선형 검색 : 정렬되지 않아 순서를 모르는 배열. 최악의 경우 모든 요소 검사 O(n)

정렬/규칙 선형 검색 : 정렬된 배열에서 검색. O(n)

이진 검색 : 사전 검색처럼. 인접한 방향으로 추적. O(logn)

심볼 테이블 그리고 해싱 : 13장 심볼 테이블, 해싱 챕터 참조.

문자 검색 알고리즘 : 15장 문자열 알고리즘 챕터 참조.

​

챕터14 해싱

시간 복잡도 O(1) 로 만들기 위해.

해싱 구성 요소

- 해시 테이블 (Hash Table)

- 해시 함수 (Hash Functions) : 해시값 충돌 최소화/균일분포, 쉽고 빠른 연산, 모든 키의 정보로 해싱

적재 인수(Load Factor) : 저장데이터 수 / 해시테이블 크기

해시함수가 잘 분산시키는지 효율성 측정에 사용.

- 충돌 (Collisions)

- 충돌 해결 기법 (Collision Resolution Techniques)

개방 주소법 (Open Addressing) : 일반 배열로 구현됨

Linear probing

Quadratic probing

연쇄화 (Chaining) : 연결 리스트로 구현된 배열

더블 해싱(Double Hasing) : 두 개의 해시 함수를 사용

​

해시 테이블이 부적합한 경우

- 정렬된 데이터 필요한 경우

- 멀티미디어 데이터를 저장해야 할 때

- 키의 길이가 길고 가변적, 키에 대한 사전 검색이 필요할 때

- 조건에 따라 데이터가 동적으로변해야 할 때

- 데이터의 키가 유일하지 않을 때

​

챕터15 문자열 알고리즘

“자동완성”기능 = 문자열 데이터를 효율적으로 저장하는 자료 구조가 필요.

문자열 패턴 검색 = 문자열 매칭 알고리즘

- 전수 방법 (Brute Force Method) : 모든 위치에서 패턴 P 매치 여부 검토. O(n*m)

- Robin-Karp 문자열 매칭 알고리즘 : 찾으려는 P의 해시값과 문자열 위치들의 해시값 비교. O(m+n)

- 유한 오토마타(Finite Automata) 문자열 매칭 : 계산 이론(Theory of Computation) 개념 유한 오토마타 사용.

유한 오토마타 : 유한 오토마톤(단수형) F 는 5-tuple( Q, q0, A, Sig, δ ) // δ : 크로네커 델타 = 전이함수

시그마는 문자의 유한 집합. 전이함수 δ(크.델) 는 전이 테이블을 가짐. 수용하고 거부할 문자열 탐색.

- KMP 알고리즘 : Knuth, Morris, Pratt 가 제시한 알고리즘. 테이블을 사용. prefix function 혹은 prefix table. (fail function 으로도 부름) 패턴의 부분 부분들에 대한 패턴 매치 유형을 저장. 패턴 P에 대한 불필요한 유형 제거에 참조됨. 패턴 P, 문자열 T, prefix function F 를 입력으로 취하여 T에서 P를 찾는다.

- Boyer-Moore 알고리즘 : KMP 과 같이 사전 처리를 수행. last function. 패턴을 T의 상대적인 위치로 이동시켜 불필요한 비교를 제거. 긴 문자열에서 매우 빠름. 패턴이 짧으면 전수 조사 알고리즘이 더 좋음.

​

문자열 정렬을 위한 자료 구조

- 해시 테이블, 이진 검색 트리, 트라이(Tries), 3항 검색 트리(Ternary Search Tree)

​

해시 테이블은 문자열을 키로 하지만, 자료의 순서를 잃어버린다는 단점. 이진트리, 공간 효율은 좋지만 탐색 연산의 시간 복잡도가 상승한다는 단점.

​

트라이(Tries) 는 re”trie” 에서 따옴. 각 노드가 알파벳 문자의 수와 같은 개수의 포인터를 포함하고 있는 트리. 가령 알파벳 a~z 로 문자열이 구성되었다면, 트라이의 각 노드는 26개 포인터를 포함.

struct TrieNode {

char data; // 현재 노드 문자

int isEndOfString; // 루트에서 현재까지 경로 문자열이 문자열인지 아닌지

struct TrieNode *child[26]; // 다른 트라이 노드들 포인터

}

L이 한 단어의 길이일 때, 트라이 시간 복잡도는 O(L)

트라이는 빠르지만, 필요 메모리가 크다.

​

3항 검색 트리(Ternary Search Tree)

BST의 메모리 효율과 트라이의 시간 효율성 겸비.

struct TSTNode {

char data;

int isEndOfString;

struct TSTNode *left; //data 보다 작은 문자열

struct TSTNode *eq; // data와 동일한 모든 문자열. boat 이고 현재 data가 b 라면 eq는 o 가 됨.

struct TSTNode *right; // data 보다 큰 문자열

}

​

BST, Trie, TST 비교

BST, 해시테이블 = 각 노드에 완전한 문자열 저장

TST = 동적으로 크기가 변함, BST와 해시테이블이 지원하지 않는 부분검색 가능

TST = 정렬된 순으로 나말 출력. 검색이 빠름. 메모리 많이 필요.

해시테이블 = 정렬된 순으로 얻을 수 없음.

​

​

- 접미사 트리(suffix Tree)

문자열 중요 자료구조 중 하나. 질의에 응답 빠르게 수행. 사전 작업이 필요. 자료구조 복잡하지만, 문자열 관련 문제 선형 시간(linear time)내에 풀 수 있게 함. 하나의 문자열에 대한 질의와응답을 수행.

문자열 T의 접미사들로 채워진 트라이와 비슷한 자료구조.

​

접두사(Prefix)

T= banana일 때, T의 접두사는 b, ba, ban, bana... 등.

접미사(Suffix)

T = banana일 때, T의 접미사는 a, na, ana, nana... 등

​

T = accbkkbac 이고 패턴문자열P = kkb 일 때

P는 T접미사 kkbac 의 접두사면서

P는 T접두사 accbkkb의 접미사이기도 함.

​

- 1에서 n까지 번호가 붙여진 n개의 leaf 가짐

- 루트 제외, 각 내부 노드는 최소 2개의 자식을 가짐.

- 간선은 비어있지 않은 T의 하부 문자열로 표시

- 한 노드에서 출발한 두 개의 간선은 같은 문자로 시작할 수 없다

- 루트에서 leaf로의 경로들은 T의 모든 접미사

​

접미사 트리 구성 알고리즘. 모든 접미사를 만들고, 시작 문자를 기준으로 그룹핑 한다.

​

문자열T = tests

index Suffix

1 $

2 s$

3 ts$

4 sts$

5 ests$

6 tests$

​

위 테이블을 첫 글자로 정렬

index Suffix Group

1 $ S1

5 ests$ S2

2 s$ S3

4 sts$ S3

6 tests$ S4

3 ts$ S4

​

응용분야

정확한 문자열매칭. 가장 많이 반복되는 문자열 횟수 탐색, 가장 긴 회문(앞에서 읽으나 뒤에서 읽으나 동일한 문자열), 가장 긴 공통 부분 문자열 탐색, 정규표현식, 패턴P가 처음 나타나는 위치 탐색.

.

.

.