문자열

KMP (문자열 중 특정 패턴을 찾아내는 탐색) 알고리즘 C++ 구현

개념 KMP 알고리즘은 문자열에서 특정 패턴을 효율적으로 찾을 수 있다. 살펴볼 문자열의 길이가 N, 찾고 싶은 패턴의 길이가 M이라면 O(N+M)의 시간 복잡도를 가지는 매우 효율적인 알고리즘이다. KMP 알고리즘이 얼마나 효율적인지 알기 전에, 모든 문자열을 일일이 비교하는 경우를 살펴보자. 모든 문자열을 일일이 비교하는 경우(브루트 포스 : Brute Force) "ABCDABCE"라는 문자열에서 "ABCE"라는 패턴을 찾는다고 해보자. 모든 문자열을 일일이 비교한 경우엔 아래와 같이 탐색을 진행할 것이다. 이처럼 모든 문자열을 비교하는 브루트 포스(Brute Force) 방식은 텍스트의 길이를 N, 찾고자 하는 패턴의 길이를 M이라고 했을 때 시간 복잡도가 O(NM)이다. 이는 매우 비효율적이다...

[C++] 문자열 입력 istream::getline()과 string의 getline()

1. std::istream::getline - cin.getline() 인자: s - C 형식 문자열을 저장할 배열을 가리키는 포인터 n - 저장할 문자의 최대 개수 (끝의 종료 널 문자를 포함한 값). 만약 입력 스트림의 최대 크기에 도달하여 입력이 중단되면 failbit 플래그가 설정된다. delim - 제한자로 이 문자에 도달시 추출이 중단다. 이 때 이 문자는 s에 기록되지는 않지만 스트림에서 사라지게 된다. 즉 istream을 상속받는 클래스에서 getline()함수를 사용할 수 있다. 콘솔에서 문자열을 입력받으려면 cin.getline()을, 파일으로부터 문자열을 가져오려면 파일입력스트림인 ifstream의 인스턴스에서 getline()을 호출하면 된다. #include #include //..

[C++] 문자열 (string) 함수 모음

length() 메소드와 size() 메소드 length() 메소드는 문자열의 길이를 반환하는 메소드다. size() 메소드도 length() 메소드와 언제나 같은 값을 반환하지만, 그 의미는 약간 다르다. length() 메소드는 문자열의 길이를 나타내지만, size() 메소드는 해당 string 객체가 메모리에서 실제 사용하고 있는 크기를 나타낸다. string str1; string str2 = "C++ Programming"; cout

[Python] 기본 자료형 1(숫자형, 문자열, bool형, None)

[숫자형] 숫자형에는 int(정수형), float(실수형), complex(복소수)가 있다. - integer(정수형) 말 그대로 양의 정수, 음의 정수, 0을 포함하는 자료형이다. a = 123 b = -123 c = 0 파이썬 2.x 버전에서는 엄청 큰 숫자를 담기 위한 long 타입이 존재했지만, 3.x부터는 long 타입이 사라지고, int 타입이 크기 제한이 없는 부호있는 정수형이 되었다. 파이썬 정수형의 크기는 컴파일러에 의해서가 아닌 컴퓨터 메모리에 의해서만 제한된다. 8진수(ex, 0o65)나 16진수(ex, 0x1FF)로도 표현이 가능하다. a = 0o65 b = 0x1FF - float(실수형) 실수형은 소수점이 포함된 숫자를 의미한다. 다른 언어처럼 float와 double 타입이 따..

[C] 포인터로 문자열 선언, 배열 문자열 선언과 차이. (문자열 내부 변경하기)

문자열(string)이란, 알파벳 하나하나가 메모리상의 연속적으로 나열되며, 마지막에는 '\0' (NULL)으로 끝나는 배열이다. 위 그림과 같이 문자열을 만드는 방법은 아래와 같다. char string[11] = "hello world"; char이므로 한칸당 1byte를 사용하며, "~~"문자열 맨 뒤에 \0 (NULL)문자는 자동으로 들어가게 된다. 고로 띄어쓰기를 포함한 모든 문자들 공간과 마지막의 NULL이 들어갈공간을 포함해 11개의 공간을 선언했다. C언어로 문자열을 표현하는 방법은 대표적으로 배열선언과 포인터 선언이 있다. 배열도 "상수형 포인터"로 결국 포인터와 동일한 역할을 한다. 배열으로 선언하는 방법은 메모리공간을 미리 할당하는 방법과, 컴파일러가 문자열 길이를 보고 알아서 할당시..

[C] 문자열(string) 입출력 (puts, fputs, gets, fgets) 사용법

문자열 출력 함수로 : puts, fputs 가 있다. 출력 함수 puts - 함수 원형: int puts(const char * string) - 반환형이 int인 이유? char형은 컴파일러마다 unsigned, signed가 다른데, int는 모든 컴파일러가 signed int로 처리함. - int형 이므로 어떤 컴파일러든 -1값(EOF)을 반환하는데 무리가 없다. - 자동으로 문자열 맨뒤 '\n' 개행이 붙는다. - char * 이므로 메모리상의 특정 문자열의 주소값이 그데로 전달 됨을 알 수 있다. 출력 함수 fputs - 함수 원형: int puts(const char * string, FILE * stdout) - 반환형이 int인 이유? char형은 컴파일러마다 unsigned, signe..

[실5] 4659 - 비밀번호 발음하기

#include #include #include using namespace std; bool IsVocal(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; } int maxCnt = 3; int main() { vector res; string s = ""; while (true) { string tmp = ""; bool hasVocal = false, flag = false, fail = false;; cin >> s; if(s == "end") break; for (int i = 0; i < s.size() + 1; i++) { char cur = i < s.size() ? s[i] : ' '; // 1. 모음(..

[C] 문자열에서 공백을 제거하는 함수

문자열 중앙에 있는 공백도 제거하는 함수가 필요해서 만들었다. 아래의 DeleteSpace함수는 인수로 받는 문자열에서 문자열에서 앞, 뒤, 가운데에 있는 모든 공백을 제거해서 제거된 문자열을 반환하는 함수다. 사용법: char *str = DeleteSpace("공백이 있는 문자열"); char str[] = DeleteSpace("공백이 있는 문자열"); #include #include char* DeleteSpace(char s[]) { char* str = (char*)malloc(sizeof(s)); int i, k = 0; for (i = 0; i < strlen(s); i++) if (s[i] != ' ') str[k++] = s[i]; str[k] = '\0'; return str; } i..

[C++] 공백 포함 문자열 입력받기

1. getline 이용 getline을 쓰면 알아서 공백 포함하여 문자열을 입력받는다. int main() { string s; getline(cin, s); cout

[C] 문자열(String) - 문자열 저장, 널문자, 문자열 배열, 문자열 크기

문자열(String) 문자의 집합 문자열이라고 하는 데이터 형식은 따로 존재하지 않는다. 문자열은 한문자(char)가 여러 개 이어져 있는 형태다. 문자열 저장 문자열 저장을 위해서는 문자열 길이에 1을 더한 만큼의 크기가 필요하다 왜냐하면 문자열의 끝을 표시하는 널문자(NULL, \0)가 존재하기 때문이다. 널문자 문자열의 끝을 알려주는 역할 \0, 하나의 문자로 취급, 화면에 출력 되지 않음 문자열 배열 문자열 저장 변수. 문자를 연속적으로 나열한 배열형태가 되어야 한다. 문자열의 크기) 실제 문자열 + 1 (NULL 문자) https://codedragon.tistory.com/5274