알고리즘 자료구조 - 9

8장

1)
문자열(string): 문자의 나열을 의미, 빈 문자열도 문자열
 - 문자열을 끝낸다는 표현으로 널문자('\0')를 사용한다
   (즉, 널문자까지 문자열로 인식한다)

문자열 리터럴(string literal): 문자의 나열을 2개의 큰따옴표("")로 묶은 것. 
 - 상수의 특징을 가지고 있다
 - 문자열 리터럴은 char *로 알려주기 때문에, 일반 문자열 크기+문자 포인터의 크기를 가진다
   (즉, 배열에 저장한 문자열보다 더 많은 메모리 영역을 차지한다)

관련 함수
 - strlen
    헤더: string.h
    원형: size_t strlen(const char *s)
    설명: 널문자를 제외한 문자열의 길이(byte)를 반환한다

 - strchr
    헤더: string.h
    원형: char *strchr(const char *s, int c)
    설명: 문자열 s의 처음에서 부터 문자 c(int이지만 문자로 인식)를 찾으며, 찾은 문자에 대한 '포인터'를 반환. 없을 경우 널포인터 반환

 - strrchr
    헤더: string.h
    원형: char *strrchr(const char *s, int c)
    설명: 문자열 s의 끝에서 부터 문자 c(int이지만 문자로 인식)를 찾으며, 찾은 문자에 대한 '포인터'를 반환. 없을 경우 널포인터 반환

** 초기의 C언어는 함수로 전달하는 매개변수로 char, short형 등의 변수를 int로 형변환하여 받았다
   따라서 표준 라이브러리 함수에서 문자를 주고받을 때는 int형으로 주고 받는다

 - strcmp
    헤더: string.h
    원형: int strcmp(const char *s1, const char *s2)
    설명: 문자열 s1, s2를 비교. 같으면 0, s1이 크면 양의정수, s2가 크면 음의 정수를 반환한다

 - strncmp
    헤더: string.h
    원형: int strncmp(const char *s1, const char *s2, size_t n)
    설명: 문자열 s1, s2를 n번째 문자까지 비교. 같으면 0, s1이 크면 양의정수, s2가 크면 음의 정수를 반환한다

 - strstr
    헤더: string.h
    원형: int strstr(const char *s1, const char *s2)
    설명: 문자열 s1의 처음에서 부터 문자열 S2를 찾으며, 찾은 문자열의 첫번째 문자를 가리키는 포인터를 반환. 없을 경우 널포인터 반환


** 아스키코드(ASCII)
 - 컴퓨터에서 사용하는 기본 문자코드
 - https://www.asciitable.com


2)
문자열 검색(string searching) 알고리즘
 - 종류: 브루트-포스, KMP, Boyer-Moore
 - 패턴(pattern): 검색할 문자열(키워드), 텍스트(text): 문자열 원본


3)
브루트-포스(brute force method) 법
 - 선형검색을 확장한 알고리즘
 - 텍스트에 패턴이 여러 개 있는 경우 가장 먼저 검색되는(가장 앞의) 텍스트의 인덱스를 반환
 - 패턴을 사용하여 텍스트의 한글자씩 검색하며, 불일치할 경우, 텍스트의 다음 문자부터 검색 시작
 - 패턴과 텍스트의 각각의 인덱스를 나타내기 위한 변수 2개를 사용하여 비교 검색한다

 - 시간복잡도: O(mn) ~ O(n)


4)
KMP 법
 - 이전의 비교검사했던 결과를 버리지 않고 활용하는 알고리즘

 - 첫 검색이후 다음 검색부터 일치한 문자 이후의 문자부터 비교검색을 하면 된다
    - 패턴의 경우 이전의 비교검사에서 패턴의 일부가 일치한 다음 문자부터 비교검색
    - 문자열은 이전의 비교검사 다음 문자부터 비교검색

 - 몇 번째 문자부터 다시 검색을 시작해야할지에 대한 판단을 위해 표를 만들어 해당 정보를 저장
 - 즉, 구현시 재 비교시 사용하는 표 - 문자열 비교 순으로 작성한다

 - 시간복잡도: O(n)


5)
Boyer-Moore법
 - 문자열 검색에 널리 사용하는 알고리즘
 - 방법은 Bad Character Heuristic와 Good Suffix Heuristic가 있으며, 책에서 설명하는 방법은 Bad Character Heuristic이다

 - 방법
     패턴을 텍스트의 앞에서 부터 시작하되, 패턴의 제일 뒷글자부터 비교한다
     만약 일치하지 않는 부분이 나오면 패턴의 나머지부분(패턴에서 일치하지 않는 요소의 앞에 해당하는 글자들)과 일치하는지 비교
     일치하지 않을 경우 패턴의 첫글자를 텍스트의 일치하지 않는 글자+1에 위치시키고 패턴의 제일 끝 글자부터 비교검색 반복
     일치할 경우 패턴과 텍스트의 상태를 그대로 유지하고 패턴의 제일 끝 글자부터 비교검색 반복
 - 즉 패턴의 일치여부에 따라 건너뛰기거리(패턴의 이동거리) 가 결정되어야 한다
   이에 대한 정보가 저장되는 건너뛰기 표(이동경로 테이블, 스킵테이블, BC)을 작성해야한다

 - 이동경로 테이블은 패턴을 기반으로, 전체 문자에 대한 이동거리를 결정하는 표이며, ('문자열은 대문자로만 구성한다'와 같은 조건이 없다면)전체 문자를 반영해야한다
   (크기는 UCHAR_MAX+1개이다. UCHAR_MAX는 unsigned char형이고 limits.h에 객체형식 매크로로 정의되어 있으며, 표현할 수 있는 문자의 개수를 의미한다)
   ** 이동경로 테이블 작성법은 KMP의 건너뛰기 표 작성법을 참조한다

 - 이동경로 테이블을 만들기 위한 기본 개념은 다음과 같다
    - 패턴의 문자열 길이가 n(널문자 제외한 전체길이)
      현재 검색에서 불일치하는 문자가 발견되었을 때 패턴을 움직이며 일치하는 패턴의 문자를 찾고, 제일 처음 일치하는 문자의 위치가 k
      패턴에서 제일 마지막 일치하는 이라면, 텍스트의 다음 검색 위치는 다음과 같다
    - 패턴에 없는 문자를 만났을 때 
       : 텍스트 다음 검색을 위한 요소의 이동거리 = n
        (즉, 비교검색시 패턴과 불일치하는 문자의 텍스트 문자열 요소위치 + n번째 요소부터 패턴의 제일 끝 글자(요소)부터 검색 시작)
    - 패턴에 존재하는 문자이지만 현재 패턴의 위치(요소)와 비교시 불일치 하는 문자이며, 나머지 패턴의 문자들과 불일치하는 경우
       : 이동거리 = n
    - 패턴에 존재하는 문자이지만 현재 패턴의 위치(요소)와 비교시 불일치 하는 문자이며, 나머지 패턴의 문자들과 비교하는 과정에서 일치하는 문자가 있을 경우
       : 이동거리 = n-k-1

 - 시간복잡도: O(n) ~ O(n/m)
 

** 책에서 언급하기로는 '테이블과 하나의 배열만 사용해서 검사하는 방법은 간단하게 구현한 알고리즘이다. 원래의 알고리즘은 2개의 배열로 문자열을 검사하는 방식이다'라고 되어 있다
   배열 2개가 텍스트와 패턴인지, 텍스트 2개를 의미하는지는 모르겠다.(인터넷을 둘러봐도 나와있지 않다. 영문사이트를 찾아보면 나올지도..)

** 관련 사이트
 - https://m.blog.naver.com/cestlavie_01/221055516242
 - https://devwooks.tistory.com/12
 - https://ee-22-joo.tistory.com/8