관리 메뉴
촉촉한초코칩
08. 문자열 본문
08-1 문자열의 기본
문자열 (String)
- 문자의 나열을 나타낸 것
- 문자 하나만 있어도 좋고, 비어 있어도 상관없다. 빈 문자열도 문자열이다.
문자열 리터럴 (String iteral)
- 문자의 나열을 2개의 큰따옴표(")로 묶은 것
- 문자열 안의 문자는 메모리 공간에 연속으로 배치된다.
- 컴퓨터는 문자열 리터럴의 끝을 나타내기 위해 널 문자(null character)를 자동으로 추가한다.
- 널문자의 비트 값은 0이다.
- 문자열 리터럴 값은 바꿀 수 없다.
- 자유롭게 읽고 쓰는 문자열은 배열로 구현해야 한다.
문자열을 구성하는 모든 문자의 값을 16진수와 2진수로 출력하기
#include <stdio.h>
#include <limits.h>
void str_dump (const char *s) {
do {
int i;
printf("%c %0*X ", *s, (CHAR_BIT + 3) / 4, *s);
for(i = CHAR_BIT -1; i>=0; i--)
putchar(((*s>>i) & 1U) ? '1' : '0');
putchar('\n');
} while(*s++ != '\0');
}
int main(void) {
str_dupm("STRING");
return 0;
}- 문자열 리터럴 자료형 : char형 배열
- 문자열 리터럴의 표현식을 평가하여 얻는 자료형 : char *s형 > 값은 첫번째 문자에 대한 포인터이다.
- 문자열 리터럴 메모리 영역 기간 : 정적 메모리 영역과 동일하다. 프로그램의 시작부터 끝까지 메모리 영역이 유지된다.
- 같은 문자열 리터럴이 여러 개 있는 경우 : 각각 다른 메모리 영역에 넣어두거나 같은 영역에 넣어두고 공유하는 컴퓨터 환경도 존재
- 변수가 아니라 상수 성질을 가지고 있어서 문자열 리터럴이 저장된 메모리 영역에 값을 대입할 수 없다.
- 문자열의 형식 문자열 : %s
배열에 문자열 저장하기
#include <stdio.h>
int main(void) {
char st[10];
st[0] = 'A';
st[1] = 'B';
st[2] = 'C';
st[3] = 'D';
st[4] = '\0'; //문자열의 끝을 나타낸다. st[5]에 문자를 대입해도 ABCD만 출력된다.
printf("문자열 st에는 \"%s\"가 들어 있습니다.\n", st);
return 0;
}
문자열 선언과 동시에 초기화하기
#include <stdio.h>
int main(void) {
char st[10] = "ABCD";
printf("문자열 st에는 \"%s\"가 들어 있습니다.\n", st);
//오류 코드
st = {'A','B','C','D','\0'};
st = "ABCD";
//요소 개수 생략하고 문자열 선언 : 초기화할 때 입력한 문자열의 요소 개수가 배열 요소 개수가 된다.
char st[] = "ABCD"; //요소 개수 : 5개
return 0;
}
포인터로 문자열 나타내기
#include <stdio.h>
int main(void) {
char *pt = "12345"; //pt는 메모리 영역의 첫번째 문자 1을 가리키며 초기화된다.
printf("포인터 pt는 \"%s\"를(을) 가리킵니다.\n", pt);
return 0;
}
배열과 포인터에 의한 문자열 메모리 영역 크기 비교
char st[] = "12345"; //배열에 의한 문자열 크기 : 6바이트
char *pt = "12345"; //포인터에 의한 문자열 크기 : sizeof(char*) + 6바이트- 포인터로 표현한 문자열은 문자열 리터럴을 저장하기 위한 영역 외에도 pt가 갖는 메모리 영역이 더 필요하다.
- pt를 위한 영역인 sizeof(char *) 바이트와 문자열 리터럴을 위한 영역인 sizeof("12345")바이트만큼 메모리 영역 필요
- 포인터로 표현한 문자열 영역 > 배열에 저장한 문자열 영역
문자열 리터럴을 가리키는 두 포인터의 값을 교환하는 프로그램
#include <stdio.h>
void swap_ptr (char **x, char **y) {
char *tmp = *x;
*x = *y;
*y = tmp;
}
int main(void) {
char *s1 = "ABCD";
char *s2 = "EFGH";
printf("포인터 s1은 \"%s\"를 가리킵니다.\n", s1);
printf("포인터 s2은 \"%s\"를 가리킵니다.\n", s2);
swap_ptr(&s1, &s2);
puts("\n포인터 s1과 s2의 값을 서로 교환했습니다.\n");
printf("포인터 s1은 \"%s\"를 가리킵니다.\n", s1);
printf("포인터 s2은 \"%s\"를 가리킵니다.\n", s2);
return 0;
}- 매개변수 x, y의 자료형은 포인터 (s1, s2)의 주소를 받아야 하기 때문에 char **형으로 정의한다. (포인터를 가리키는 포인터)
문자열 길이
- 컴퓨터는 배열에 저장된 문자열의 경우, 널 문자까지만 문자열로 인식 > 배열 전체를 문자열로 사용하지 않음
- 문자열의 첫문자부터 널문자까지 선형검색해서 문자열의 길이를 구하는 알고리즘을 사용해야 한다.
#include <stdio.h>
//버전 1
int str_len (const char *s) {
int len = 0;
while(s[len]) //널문자를 만나면 s[len]가 0이 되어 문자열 스캔을 중단한다.
len++;
return len;
}
//버전 2
int str_len(const char *s) {
int len = 0;
while(*s++)
len++;
return len;
}
//버전 3
int str_len(const char *s) {
const char *p = s;
while(*s)
s++;
return s-p;
}
int main(void) {
char str[256];
printf("문자열 : ");
scanf("%s", str);
printf("이 문자열의 길이는 %d입니다.\n", str_len(str));
return 0;
}
strlen 함수
| 헤더 | #include <string.h> |
| 형식 | size_t strlen(const char *s); |
| 해설 | s가 가리키는 문자열의 길이를 구한다. |
| 반환값 | 구한 문자열의 길이를 반환한다. |
문자열에서 널문자가 아닌 문자 검색하기
- 같은 문자가 여러 개 있는 경우 > 가장 앞쪽에 있는 문자 인덱스를 반환한다.
#include <stdio.h>
int str_chr (const char *s, int c) { //문자열 s에서 문자 c 선형검색하기
int i = 0;
c = (char)c;
while(s[i] != c) {
if(s[i] == '\0') //검색 실패
return -1;
i++;
}
return i; //검색 성공 > 찾은 문자의 인덱스 반환
}
int main(void) {
char str[64]; //이 문자열에서 검색
char tmp[64];
int ch; //검색할 문자
int idx;
printf("문자열 : ");
scanf("%s", str);
printf("검색할 문자 : ");
scanf("%s", tmp); //먼저 문자열로 검색할 문자를 읽어 들인다.
ch = tmp[0]; //첫번째 문자를 검색할 문자로 지정한다.
if((idx = str_chr(str, ch)) == -1) //처음 나오는 문자 검색
printf("문자 '%c'은(는) 문자열에 없습니다.\n", ch);
else
printf("문자 '%c'은(는) %d번째에 있습니다.\n", ch, idx+1);
return 0;
}
strchr, strrchr 함수 : 문자열 안에 들어있는 문자를 검색하는 함수
- 표준 라이브러리 함수에서 문자를 주고받을 때는 char형이 아니라 int형으로 주고받는다.
| strchr 함수 | |
| 헤더 | #include <string.h> |
| 형식 | char *strchr(const char *s, int c); |
| 해설 | s가 가리키는 문자열에서 가장 앞쪽에 있는 c를 찾는다. 이때 c는 널문자여도 된다. |
| 반환값 | 찾은 문자에 대한 포인터를 반환한다. > 가장 앞쪽의 문자 검색 문자가 없으면 널 포인터를 반환한다. |
| strrchr 함수 | |
| 헤더 | #include <string.h> |
| 형식 | char *strrchr(const char *s, int c); |
| 해설 | s가 가리키는 문자열 가운데 가장 뒤쪽에 있는 c를 찾는다. 이때 c는 널문자여도 된다. |
| 반환값 | 찾은 문자에 대한 포인터를 반환한다. > 검색할 문자가 문자열 안에 여러 개 있는 경우, 가장 뒤쪽 문자 검색 문자가 없으면 널 포인터를 반환한다. |
strcmp 함수 : 문자열 비교
- 문자 코드 체계에 따라 문자열을 비교하므로 반환하는 값은 컴퓨터 환경마다 다를 수 있다.
| stcmp 함수 | |
| 헤더 | #include <string.h> |
| 형식 | int strcmp(const char *s1, const char *s2); |
| 해설 | s1, s2가 가리키는 문자열의 대소 관계를 비교한다. 처음부터 순서대로 한 문자씩 unsigned char 형 값으로 비교한다. |
| 반환값 | 문자열이 같으면 : 0 s1이 s2보다 크면 : 양의 정수 s1이 s2보다 작으면 : 음의 정수 |
#include <stdio.h>
int str_cmp (const char *s1, const char *s2) {
while(*s1 == *s2) {
if(*s1 == '\0') //같음
return 0;
s1++;
s2++;
}
return (unsigned char)*s1 - (unsigned char) *s2;
}
int main(void) {
char st[128];
puts("\"ABCD\"와 비교합니다.");
puts("\"XXXX\"면 종료합니다.");
while(1) {
printf("문자열 st : ");
scanf("%s", st);
if(str_cmp("XXXX", st) == 0)
break;
printf("str_cmp(\"ABCD\", st) = %d\n", str_cmp("ABCD", st));
}
return 0;
}
strncmp 함수
- 3번째 인수로 지정한 문자열의 길이만큼만 비교할 수 있다.
- 널문자가 없는 '문자 배열' 간의 비교도 가능하다.
| strncmp 함수 | |
| 헤더 | #include <string.h> |
| 형식 | int strncmp(const char *s1, const char *s2 size_t n); |
| 해설 | s1, s2가 가리키는 문자 배열에서 n번째 문자까지의 대소 관계 비교 처음부터 순서대로 한 문자씩 unsigned char형 값으로 비교한다. 널 문자 이후의 비교는 하지 않는다. |
| 반환값 | 문자 배열이 같으면 : 0 s1이 s2보다 크면 : 양의 정수 값 s1이 s2보다 작으면 : 음의 정수 값 |
#include <stdio.h>
#include <string.h>
int main(void) {
char st[128];
puts("\"STRING\"의 처음 3개의 문자와 비교합니다.");
puts("\"XXXX\"를 입력하면 종료합니다.");
while(1) {
printf("문자열 st : ");
scanf("%s", st);
if(strncmp("XXXX", st, 3) == 0)
break;
printf("strncmp("\STRING\", st, 3) = %d\n", strncmp("STRING", st, 3));
}
return 0;
}
08-2 부루트-포스법 (brute force method)
문자열 검색
- 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어 있다면 그 위치 찾아내기
- 패턴 (pattern) : 검색할 문자열
- 텍스트 (text) : 문자열 원본
브루트 포스법
- 선형 검색을 확장한 알고리즘
- 첫번째 요소부터 비교해서 뒤로 한칸씩 옮겨가며 검색한다.
- 하지만 이미 검사를 진행한 위치를 기억하지 못한다.
#include <stdio.h>
int bf_match (const char txt[], const char pat[]) {
int pt = 0;
int pp = 0;
while(txt[pt] != '\0' && pat[pp] != '\0') {
if(txt[pt] == pat[pp]) {
pt++;
pp++;
else {
pt = pt - pp + 1;
pp = 0;
}
}
if(pat[pp] == '\0')
return pt - pp;
return -1;
}
int main(void) {
int idx;
char s1[256]; //텍스트
char s2[256]; //패턴
puts("브루트-포스법");
printf("텍스트 : ");
scanf("%s", s1);
printf("패턴 : ");
scanf("%s", s2);
idx = bf_match(s1, s2);
if(idx == -1)
puts("텍스트에 패턴이 없습니다.");
else
printf("%d번째 문자부터 match합니다.\n", idx+1);
return 0;
}bf_match 함수
- 텍스트에서 패턴을 검색 > 텍스트의 위치(인덱스) 반환
- 텍스트에 패턴이 여러 개 있는 경우 > 가장 앞쪽에 위치한 텍스트의 인덱스 반환, 검색에 실패하면 -1 반환
- 텍스트를 스캔하기 위한 변수로 pt 사용, 패턴을 스캔하기 위해 pp 사용
- 두 변수는 처음에 0으로 초기화하고 스캔하거나 패턴을 옮길 때마다 업데이트한다.
08-3 KMP법
KMP법
- 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고, 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫번째 문자부터 검색한다.
- 중간 검사 결과를 효율적으로 사용하는 알고리즘이다.
- 이미 검사를 마친 부분의 다음문자부터 패턴과 비교하여 일치하는지 검사한다.
- 하지만 몇번째 문자부터 다시 검색을 시작할지 패턴을 이동시킬 때마다 다시 계산해야 하는 단점이 있다. > 표로 만들어서 문제 해결
- 표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 한다. > KMP법 사용
int kmp_match(const char txt[], const char pat[]) {
int pt = 1;
int pp = 0;
int skip[1024];
skip[pt] = 0;
while(pat[pt] != '\0') { //표 만들기
if(pat[pt] == pat[pp])
skip[++pt] = ++pp;
else if(pp == 0)
skip[++pt] == pp;
else
pp = skip[pp];
}
pt = pp = 0;
//텍스트를 스캔하는 커서 pt는 다시 뒤로 돌아오지 않는다.
while(txt[pt] != '\0' && pat[pp] != '\0') { //검색 수행
if(txt[pt] == pat[pp]) {
pt++; pp++;
} else if(pp == 0)
pt++;
else
pp = skip[pp];
}
if(pat[pp] == '\0')
return pt - pp;
return -1;
}
08-4 Boyer-Moore 법
Boyer-Moore 법
- 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다.
- 텍스트와 패턴의 첫번째 문자를 위, 아래로 겹치고 패턴의 마지막 문잘ㄹ 검사한다.
- 텍스트 안에서 패턴이 들어있지 않은 문자를 찾으면 해당 위치까지의 문자는 건너뛸 수 있다.
패턴 길이가 n이라면, 현재 검사하고 있는 텍스트의 문자 위치로부터 '다음에 검사할 패턴의 마지막 문자 위치'가 n만큼 떨어질 수 있도록 패턴을 옮기면 된다. - KMP법과 동일하게 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표(건너뛰기 표)를 미리 만들어야 한다.
패턴 문자열의 길이가 n일 때 옮길 크기 결정하는 방법
1. 패턴이 들어 있지 않은 문자를 만난 경우
- 패턴을 옮길 크기 (n)만큼 옮긴다.
2. 패턴에 들어 있는 문자를 만난 경우
- 마지막에 나오는 위치의 인덱스가 k이면, 패턴을 옮길 크기는 n-k-1이다.
- 같은 문자가 패턴 안에 중복해서 들어있지 않다면, 패턴을 옮길 크기는 n이 된다.
건너뛰기 표의 요소 개수 : UCHAR_MAX + 1
패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산하고 저장해야 하기 때문
#include <stdio.h>
#include <string.h>
#include <limits.h>
int bm_match(const char txt[], const char pat[]) {
int pt;
int pp;
int txt_len = strlen(txt);
int pat_len = strlen(pat);
int skip[UCHAR_MAX+1];
for(pt = 0; pt<=UCHAR_MAX; pt++) //건너뛰기 표 만들기
skip[pt] = pat_len;
for(pt = 0; pt<pat_len - 1; pt++)
skip[pat[pt]] = pat_len - pt - 1;
while(pt < txt_len) {
pp = pat_len - 1;
while(txt[pt] == pat[pp]) {
if(pp == 0)
return pt;
pt--; pp--;
}
pt+= (skip[txt[pt]] > pat_len - pp) ? skip[txt[ppt]] : pat_len - pp;
}
return -1;
}
int main(void) {
int idx;
char s1[256];
char s2[256];
puts("Boyer-Moore법");
printf("텍스트 : ");
scanf("%s", s1);
printf("패턴 : "):
scanf("%s", s2);
idx = bm_match(s1, s2);
if(idx == -1)
puts("텍스트에 패턴이 없습니다.");
else
printf("%d번째 문자부터 match합니다.\n", idx+1);
return 0;
}
strstr 함수 : 문자열 검색하는 표준 라이브러리
| 헤더 | #include <string.h> |
| 형식 | char *strstr(const char *s1, const char *s2); |
| 해설 | s1이 가리키는 문자열에서 s2가 가리키는 문자열과 일치하는 (널 문자를 포함하지 않는) 문자열을 찾는다. 가장 앞쪽에 나오는 문자열을 찾는다. |
| 반환값 | 찾아낸 문자열에 대한 포인터 (첫번째 문자에 대한 포인터) 반환 찾지 못하면 > 널 포인터 반환 s2길이가 0인 문자열이면, s1을 반환한다. |
#include <stdio.h>
#include <string.h>
int main(void) {
char s1[256], s2[256];
char *p;
puts("strstr 함수");
printf("텍스트 : ");
scanf("%s", s1);
printf("패턴 : ");
scanf("%s", s2);
p = strstr(s1, s2);
if(p == NULL)
printf("텍스트에 패턴이 없습니다.\n");
else {
int ofs = p - s1;
printf("\n%s\n", s1);
printf("%*s|\n", ofs, "");
printf("%*s%s\n", ofs, "", s2);
}
return 0;
}
문자열 검색 알고리즘의 시간복잡도와 실용성
부르트-포스법
- 시간복잡도 : O(mn), O(n)
- 단순 알고리즘이지만 실제는 아주 빠르게 동작한다.
KMP법
- 시간복잡도 : O(n)
* 처리가 복잡하고 패턴 안에 반복이 없으면 효율이 좋지 않다. - 검색 과정에서 검사하는 위치를 앞으로 되돌릴 필요가 없어서 순서 파일을 읽어 들이며 검색할 때 많이 사용한다.
Boyer-Moore법
- 시간 복잡도 : O(n), 평균 : O(n/m)
- 2개의 배열을 사용하면 KMP법과 마찬가지로 배열을 만드는데 복잡한 처리가 필요해 효과가 떨어진다.
- 1개의 배열을 사용하는 방법으로 간단하게 구현한 Boyer-Moore법을 사용해도 충분히 빠르다.
* 가장 실용적인 문자열 검색 알고리즘 : Boyer-Moore법 (경우에 따라 브루트-포스법을 사용하기도 한다.)
'Algorithm' 카테고리의 다른 글
| 10. 트리 (0) | 2023.06.08 |
|---|---|
| 09. 리스트 (0) | 2023.06.05 |
| [미해결] 2023 인하대학교 프로그래밍 경진대회(IUPC) (A-모비스) (0) | 2023.05.21 |
| [백준] 25305(커트라인) c언어 (0) | 2023.05.21 |
| [백준] 2501(약수 구하기) c언어 (0) | 2023.05.21 |