c (4) 썸네일형 리스트형 [C/C++ 공부] 깊은 복사와 얕은 복사 차이? (feat.복사 생성자) 객체를 생성하고 초기화시킬 때 멤버 변수를 어떻게 초기화하느냐에 따라 깊은 복사가 될 수 있고, 얕은 복사가 될 수 있습니다. *디폴트 생성자가 아닌 일반 생성자는 생성자의 인수를 전달 받아 멤버 변수를 초기화시킵니다. 복사 생성자는 별도 생성자를 선언하지 않는다면, 암시적 생성자로 인수로 제공된 객체의 멤버 변수를 복사하여 새롭게 생성하는 객체의 멤버 변수를 생성합니다. ※디폴트 생성자란? 명시적인 초기화 값을 제공하지 않았을 때 객체를 생성하는 데 사용하는 생성자. 사용자가 어떠한 생성자도 정의하지 않을 경우에만 컴파일러가 디폴트 생성자를 제공 ▶ 복사 생성자 밑에 보이는 프로그램은 아마 오류가 날 것입니다. 왜 그럴까요? #include #include #include class MyString {.. [알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(2) 앞서 Boyer-Moore 알고리즘에 사용되는 두 원리 중 Bad Character 원리를 살펴 보았다. 이번에는 그 나머지 원리인 Good Suffix 원리를 배워보려고 한다. 2021.07.26 - [Algorithm/Pattern Searching] - [알고리즘 공부] Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) [알고리즘 공부] Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. ↓그 전 KMP 알고리즘 관련 글 2021.07.23 - [Algori bblackscene21.tistory.com .. [알고리즘 공부] 보이어 무어 알고리즘 Boyer-Moore Algorithm(문자열 검색 알고리즘)(1) Boyer-Moore 알고리즘 또한 앞서 봤던 KMP 알고리즘과 같이 문자열을 검색할 때, 패턴을 둘 이상 이동할 수 있도록 패턴에 대한 사전 처리를 진행합니다. ↓그 전 KMP 알고리즘 관련 글 2021.07.23 - [Algorithm/Pattern Searching] - [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘) 이 알고리즘을 이 두 가지 접근법을 조합한 것입니다. 각각의 접근법에 대해 패턴을 처리하고, 검색을 수행할 때 두 접근법이 제안하는 값 중 최대값만큼 패턴을 이동합니다. (두 가지 원리 모두 각각 독립적으로 사용해도 문자열 검색이 가능합니다.) 1) Bad Character 2) Good Suffix 이번 글에서는 Bad Character 원리부터 살펴보겠습니다. .. [알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘) 밑에 보이는 예시는 KMP 알고리즘 사용 전인데 효율이 떨어져 보입니다. 텍스트와 패턴이 일치하는지 차례대로 순회하면서 비교해보기 때문에 시간복잡도는 O(문자열 길이 * 패턴 길이) = O(N)으로, 시간이 오래 걸립니다. KMP 알고리즘이란? 패턴과 텍스트의 불일치를 감지할 때마다 그 전에 검사해왔던 텍스트의 문자들이 무엇인지 알고 있습니다(처음 검사할 때 A B A B 로 B에서 불일치가 발생했을 때, 불일치 발생 전 문자들이 A, B, A). KMP 알고리즘은 이를 이용해 불필요한 검사는 스킵합니다. 시간 복잡도는 최악의 경우, O(문자열 길이 * 패턴 길이) 이므로 위와 같이 O(N)입니다. 알고리즘 구성 lps[ ] : 패턴 문자열에서 접두사와 접미사가 일치하는 최대 길이를 저장하는 배열 (밑에.. 이전 1 다음
