C++ Week 5
팀프로젝트 시작
Study
알고리즘 2문제,
Today I Learned
.find 와 string::npos
Overview
size_t pos = s.find("검색어");
if (pos != string::npos){
}.find 는 std::find와 달리 찾지 못할ㄹ시 string::npos 반환
npos = "no position"
s.find("검색어",7); 은 7번째부터 찾는다는 뜻. 검색어 찾는 기능 같은 곳에서 사용
하지만 시간 복잡도 상으로 O(n x m) 이므로 비효율적이다.
substr, replace
Overview
substr
문자열.substr(시작위치, 길이)
앞뒤 문맥만 떼어서 로그를 남기고 싶을 때 유용함
replace
문자열.replace(시작위치, 길이, "바꿀문자열")
문자열 특정 범위를 다른글자로 바꾸는 것.
두개를 이용해 채팅 검열 시스템을 만들 수 있지만 비효율적이라 다른 방법을 이용하는데 그게 아호코라식(Aho_Corasick)이다.
아호코라식(Aho_Corasick)
아호코라식 알고리즘은 여러 개의 패턴(문자열)을 한 번의 탐색으로 동시에 찾아내는 똑똑한 문자열 검색 알고리즘
핵심 원리 -> "트라이(Trie) + KMP"
- 트라이(Trie) -> 찾고자 하는 모든 단어들ㄹ을 먼저 '문자열 틜' 형태로 구성
- 실패 함수(Failure Function) -> KMP 알고리즘의 핵심 원리. AB와 BC를 탐색해야 한다면 AB를 찾으면서 B도 같이 찾은걸로 쳐서 다른건 다 넘기고 BC를 빨리 찾을 수 있다 이런 뜻이다.- 금지어가 몇 만 개여도 채팅 메시지를 딱 한 번만 읽으면 끝남
- 미친놈/미친 같은 단어를 완벽하게 잡아냄
rand()
Overview
rand() % 개수 + 시작숫자
int num = rand() % 10 + 1; -> 0~9까지 이지만, 최솟값 1을 더해서 1~10으로 만듦
그렇지만 rand()는 정해져 있는 숫자가 나오는 것일 뿐 랜덤 숫자가 아님
srand(time(NULL))라는 현실 시간 기준으로 main에 선언해줘야 제대로 랜덤이 나옴
그렇지만 실무에서는 rand()를 잘 안 쓴다고함.
