안녕하세요! 이번 글에서는 C++를 활용한 문자열 찾기 문제에 대해 알아보겠습니다. 알고리즘 문제를 해결하는 것은 프로그래밍 능력을 발전시키고, 코딩 테스트에서 좋은 성적을 얻는 데 도움이 됩니다. 특히 최근 몇 년 동안 코딩 테스트에서 문자열 처리 문제는 매우 자주 출제되고 있습니다. 따라서 이 주제에 대한 충분한 이해와 연습이 필요합니다.
문제 설명
이번 강의에서는 주어진 텍스트에서 특정 문자열(패턴)을 찾아서 해당 문자열이 텍스트에 몇 번 등장하는지 세는 문제를 다루어 보겠습니다. 이 문제는 문자열 검색 알고리즘의 기초적인 예로, 다음과 같은 문제를 해결할 것입니다.
문제:
주어진 문자열 text와 pattern이 있을 때, pattern이 text에 몇 번 나타나는지를 구하는 프로그램을 작성하시오.
입력 형식
- 첫 번째 줄: 문자열
text(1 ≤ |text| ≤ 100,000) - 두 번째 줄: 문자열
pattern(1 ≤ |pattern| ≤ 100,000)
출력 형식
- 일치하는 패턴의 개수를 출력한다.
접근 방식
문제 해결을 위해 사용할 수 있는 여러 알고리즘이 있지만, 여기서는 간단한 브루트 포스 방법을 살펴보겠습니다. 이 방법은 텍스트의 각 위치에서 패턴을 비교하여 그 일치 여부를 판단합니다. 성능은 O(n * m)으로, n은 텍스트의 길이, m은 패턴의 길이입니다. 이 방법은 간단하고 직관적이지만, 더 효율적인 방법인 KMP 알고리즘이나 Rabin-Karp 알고리즘 등을 고려할 수도 있습니다.
코드 구현
이제 코드를 구현해보겠습니다. 아래는 C++로 작성된 문자열 찾기 프로그램입니다:
#include <iostream>
#include <string>
int countOccurrences(const std::string &text, const std::string &pattern) {
int count = 0;
int textLength = text.length();
int patternLength = pattern.length();
for (int i = 0; i <= textLength - patternLength; i++) {
// substring를 통해 부분 문자열 비교
if (text.substr(i, patternLength) == pattern) {
count++;
}
}
return count;
}
int main() {
std::string text, pattern;
std::cout << "텍스트를 입력하세요: ";
std::getline(std::cin, text);
std::cout << "패턴을 입력하세요: ";
std::getline(std::cin, pattern);
int occurrences = countOccurrences(text, pattern);
std::cout << "패턴은 " << occurrences << " 번 나타납니다." << std::endl;
return 0;
}
코드 설명
위의 C++ 코드는 문자열 찾기 문제를 해결합니다. 사용자가 제공한 text와 pattern을 기반으로 기능을 수행합니다.
- countOccurrences 함수: 이 함수는 주어진
text에서pattern의 발생 횟수를 세는 역할을 합니다. 이 함수는 텍스트의 각 위치에서 서브스트링을 추출하고 주어진 패턴과 비교하여 일치할 때마다 카운트를 증가시킵니다. - main 함수: 기본적인 입출력을 처리하는 부분입니다. 사용자로부터 문자열을 입력받고,
countOccurrences함수를 호출하여 결과를 출력합니다.
성능 분석
위의 브루트 포스 방법은 최악의 경우 O(n * m)의 시간 복잡도를 가지게 됩니다. 텍스트의 길이가 길어질수록 성능이 떨어질 수 있습니다. 그러나 코드의 간결성과 직관성을 중시한다면 이 방법은 유용할 수 있습니다.
다음으로, 효율적인 해결을 원한다면 KMP(Knuth-Morris-Pratt) 알고리즘을 고려해 볼 수 있습니다. KMP 알고리즘은 패턴의 부분 반복을 활용하여 문자열 검색을 최적화합니다. 이 알고리즘은 O(n + m)의 시간 복잡도를 갖습니다.
KMP 알고리즘 소개
KMP 알고리즘은 패턴 검색 문제를 해결하기 위해 만들어진 알고리즘으로, 이전에 일치했던 부분을 이용하여 반복 검사를 줄이는 방식입니다. 이 알고리즘은 두 가지 주요 단계로 구성됩니다. 첫 번째 단계는패턴에 대한 ‘LPS(Longest Prefix Suffix)’ 배열을 구축하는 것이고, 두 번째 단계는 이 LPS 배열을 활용하여 텍스트에서 패턴을 검색하는 것입니다.
LPS 배열 구축
LPS 배열은 패턴의 각 접두사(prefix) 중에서 가장 긴 접두사와 접미사(suffix)의 길이를 저장하고 있습니다. 예를 들어, 패턴 “ABAB”의 경우 LPS 배열은 [0, 0, 1, 2]가 됩니다. 이는 다음의 의미를 갖습니다:
- 인덱스 0에 해당하는 A까지는 접두사와 접미사가 없으므로 0
- 인덱스 1에서 B는 접두사와 접미사가 없으므로 0
- 인덱스 2에서 AB는 A가 접두사이자 접미사이므로 1
- 인덱스 3에서 ABA는 AB가 접두사이자 접미사이므로 2
KMP 알고리즘 구현
아래는 KMP 알고리즘을 구현한 C++ 코드입니다:
#include <iostream>
#include <string>
#include <vector>
std::vector computeLPS(const std::string &pattern) {
int m = pattern.length();
std::vector lps(m);
int len = 0;
lps[0] = 0;
int i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
int KMP(const std::string &text, const std::string &pattern) {
std::vector lps = computeLPS(pattern);
int n = text.length();
int m = pattern.length();
int i = 0;
int j = 0;
int count = 0;
while (i < n) {
if (pattern[j] == text[i]) {
i++;
j++;
}
if (j == m) {
count++;
j = lps[j - 1];
} else if (i < n && pattern[j] != text[i]) {
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
return count;
}
int main() {
std::string text, pattern;
std::cout << "텍스트를 입력하세요: ";
std::getline(std::cin, text);
std::cout << "패턴을 입력하세요: ";
std::getline(std::cin, pattern);
int occurrences = KMP(text, pattern);
std::cout << "패턴은 " << occurrences << " 번 나타납니다." << std::endl;
return 0;
}
마무리
이번 글에서는 C++로 문자열 찾기 문제를 해결하는 방법에 대해 알아보았습니다. 브루트 포스 방법을 소개한 후, 효율적인 KMP 알고리즘이 어떻게 작동하는지 살펴보았습니다. 문자열 관련 문제는 기본적인 알고리즘 지식을 토대로 더욱 발전할 수 있습니다. 따라서 이러한 문제를 꾸준히 연습하여 프로그래밍 능력을 향상시키는 것이 중요합니다.
여러분도 다양한 문자열 문제를 풀면서 자신만의 알고리즘을 개발해보세요! 코딩 테스트에 대한 자신감을 가질 수 있을 것입니다. 감사합니다!