문자열 검색편집자 확인

문자열 검색의 대상이 되는 문자열은 문자들의 유한한 나열을 의미한다. 컴퓨터 과학에서는 일반적으로 알파벳이라는 고정된 집합에서 추출된 기호들의 시퀀스로 정의된다. 이때 문자는 영문자, 숫자, 공백, 구두점 등 다양한 유니코드 기호를 포함할 수 있다. 문자열의 길이는 그 문자열을 구성하는 문자의 총 개수를 나타낸다.

문자열은 텍스트 데이터를 표현하는 가장 기본적인 형태로, 프로그래밍 언어마다 문자열을 처리하는 내장 데이터 타입이나 라이브러리를 제공한다. 문자열 검색 알고리즘은 이러한 긴 텍스트 문자열 내에서 상대적으로 짧은 패턴 문자열의 출현 위치를 효율적으로 찾는 것을 목표로 한다. 문자열의 특성상, 검색 과정에서 부분 문자열 비교가 빈번하게 이루어진다.

문자열의 표현과 저장 방식은 검색 알고리즘의 성능에 직접적인 영향을 미친다. 예를 들어, C 프로그래밍 언어에서는 문자열 끝을 나타내는 널 문자를 사용하는 반면, 자바나 파이썬과 같은 현대 언어들은 문자열의 길이 정보를 별도로 관리한다. 이러한 내부 구현 차이는 문자열 접근 및 비교 연산의 효율성과 관련이 있다.

문자열 검색에서 패턴은 텍스트 내에서 찾고자 하는 대상 문자열을 가리킨다. 이는 단순히 특정 단어나 구문일 수도 있고, 정규 표현식과 같은 더 복잡한 규칙을 따르는 형태일 수도 있다. 검색 알고리즘의 목표는 주어진 긴 텍스트 문자열에서 이 패턴이 등장하는 모든 시작 위치를 정확히 찾아내는 것이다. 패턴의 길이는 일반적으로 텍스트의 길이보다 짧으며, 알고리즘의 효율성은 패턴의 길이와 특성에 크게 영향을 받는다.

패턴 검색은 텍스트 편집기의 '찾기' 기능, 데이터베이스에서의 특정 레코드 검색, 바이러스 백신 소프트웨어의 시그니처 매칭 등 일상적인 컴퓨팅 작업의 핵심을 이룬다. 또한 생물정보학에서는 DNA 서열 분석을 위해, 네트워크 보안에서는 패킷 데이터 내의 악성 코드 패턴 탐지를 위해 광범위하게 활용된다. 이러한 응용 분야에서는 단순한 문자열 일치를 넘어, 약간의 변형을 허용하거나 부분 일치를 찾는 고급 패턴 매칭 기법이 요구되기도 한다.

따라서 패턴 검색 알고리즘을 설계할 때는 패턴의 구조를 사전에 분석하여 불필요한 비교를 줄이는 전략이 중요하다. 예를 들어, KMP 알고리즘은 패턴 자체에 대한 사전 분석을 통해 검색 시 효율성을 높이고, 보이어-무어 알고리즘은 패턴의 뒷부분부터 비교하여 많은 경우 빠르게 이동할 수 있도록 한다. 선택된 알고리즘에 따라 검색의 시간 복잡도와 공간 복잡도가 결정되며, 이는 대규모 텍스트 데이터를 처리하는 성능에 직접적인 영향을 미친다.

문자열 검색에서 텍스트는 검색 대상이 되는 긴 문자열을 의미한다. 텍스트는 문자열로 구성되며, 알고리즘의 입력값으로 사용된다. 텍스트의 길이는 일반적으로 n으로 표기하며, 여기서 특정 패턴을 찾아내는 것이 문자열 검색의 핵심 목표이다.

텍스트는 다양한 형태와 출처를 가질 수 있다. 일반적인 문서 파일, 웹페이지의 HTML 코드, 데이터베이스의 레코드, 유전자 서열 데이터, 혹은 네트워크를 통해 전송되는 패킷의 데이터 페이로드 등이 모두 텍스트의 예시가 된다. 따라서 텍스트는 순수한 평문일 수도 있고, 구조화된 또는 이진 데이터를 포함한 문자열일 수도 있다.

검색 알고리즘은 이 텍스트 문자열을 처음부터 끝까지 순회하거나, 특정 전략에 따라 점프하면서 패턴과 비교한다. 성능 평가에서 중요한 요소인 시간 복잡도는 주로 텍스트의 길이 n과 패턴의 길이 m에 따라 결정된다. 텍스트가 매우 길거나 실시간으로 스트리밍되는 경우, 알고리즘의 효율성이 특히 중요해진다.

텍스트 처리의 맥락에서, 텍스트 편집기의 찾기 기능이나 정보 검색 시스템의 색인 생성은 모두 이 텍스트 문자열을 기반으로 이루어진다. 또한 바이오인포매틱스에서는 DNA 서열이라는 텍스트 안에서 특정 유전자 패턴을 검색하는 데 문자열 검색 기법이 응용된다.

단순 문자열 검색은 가장 직관적이고 기본적인 문자열 검색 방법이다. 이 알고리즘은 브루트 포스 방식으로, 텍스트 문자열의 첫 번째 문자부터 시작하여 패턴 문자열을 한 문자씩 순차적으로 비교한다. 비교 도중 문자가 일치하지 않으면, 텍스트에서 패턴의 시작 위치를 한 칸 뒤로 옮겨 다시 처음부터 비교를 반복한다. 이 과정은 텍스트의 끝까지 또는 패턴이 발견될 때까지 계속된다.

이 방식의 장점은 구현이 매우 간단하고 직관적이라는 점이다. 소스 코드를 이해하기 쉽고, 특별한 전처리 과정이 필요 없어 즉시 적용할 수 있다. 따라서 간단한 텍스트 편집기의 찾기 기능이나 소규모 데이터 처리에 빠르게 사용할 수 있다. 그러나 단점은 효율성이 낮다는 것이다. 최악의 경우, 텍스트의 모든 위치에서 패턴의 모든 문자를 비교해야 하므로 시간 복잡도가 O(n*m)에 달할 수 있다. 여기서 n은 텍스트 길이, m은 패턴 길이를 의미한다.

성능상의 한계로 인해 긴 텍스트나 빈번한 검색이 필요한 데이터베이스 시스템, 정보 검색 시스템 등에서는 일반적으로 사용되지 않는다. 대신, KMP 알고리즘이나 보이어-무어 알고리즘과 같이 불필요한 비교를 건너뛰어 효율성을 높인 고급 알고리즘이 널리 채택된다. 단순 문자열 검색은 이러한 고급 알고리즘의 동작 원리를 이해하는 기초가 된다는 점에서 교육적 가치를 지닌다.

KMP 알고리즘은 도널드 커누스와 제임스 H. 모리스, 프랫이 고안한 문자열 검색 알고리즘이다. 이 알고리즘의 핵심 아이디어는 검색에 실패했을 때, 이미 비교한 정보를 활용하여 불필요한 비교를 건너뛰는 것이다. 이를 위해 패턴 문자열 자체를 분석하여 '실패 함수' 또는 '부분 일치 테이블'이라고 불리는 보조 배열을 미리 계산한다. 이 테이블은 패턴의 각 위치에서 접두사와 접미사가 일치하는 최대 길이를 저장하며, 불일치 발생 시 패턴을 얼마나 앞으로 이동시킬지 결정하는 데 사용된다.

알고리즘의 동작 과정은 다음과 같다. 먼저 텍스트 문자열과 패턴 문자열을 왼쪽에서 오른쪽으로 한 문자씩 비교한다. 비교 중 문자가 일치하면 두 문자열의 인덱스를 모두 증가시킨다. 문자가 불일치하면, 부분 일치 테이블을 참조하여 패턴 문자열의 인덱스를 새로운 위치로 이동시킨다. 이때, 텍스트 문자열의 인덱스는 되돌아가지 않고 그대로 유지된다. 이 과정은 패턴이 텍스트 내에서 완전히 발견되거나, 텍스트의 끝에 도달할 때까지 반복된다.

KMP 알고리즘의 가장 큰 장점은 최악의 경우에도 시간 복잡도가 O(n+m)이라는 점이다. 이는 단순 문자열 검색 알고리즘의 최악의 경우 O(n*m)에 비해 매우 효율적이다. 특히 반복되는 문자가 많은 긴 텍스트나 패턴을 검색할 때 성능상의 이점이 두드러진다. 단점으로는 패턴의 길이에 비례하는 추가적인 공간(부분 일치 테이블)이 필요하며, 알고리즘의 구현이 단순 검색에 비해 다소 복잡하다는 점을 들 수 있다.

이 알고리즘은 텍스트 편집기의 찾기 기능, 바이러스 시그니처 탐지, 디지털 포렌식 도구, 그리고 DNA 서열 분석과 같은 생물정보학 분야에서 널리 응용된다. 패턴을 미리 처리하는 사전 계산 방식은 이후 등장한 보이어-무어 알고리즘이나 라빈-카프 알고리즘과 같은 다른 고급 문자열 검색 알고리즘에도 영향을 미쳤다.

보이어-무어 알고리즘은 1977년 로버트 보이어와 J 스트로더 무어가 고안한 효율적인 문자열 검색 알고리즘이다. 이 알고리즘의 핵심 특징은 패턴을 텍스트와 비교할 때, 비교 방향을 오른쪽에서 왼쪽으로 진행하며, 불일치가 발생했을 때 미리 계산된 두 가지 규칙(나쁜 문자 규칙과 좋은 접미사 규칙)을 사용해 패턴을 가능한 한 많이 점프시킨다는 점이다. 이러한 접근 방식은 특히 검색 대상 알파벳의 크기가 클수록 평균적인 성능이 매우 뛰어나며, 많은 실제 응용 프로그램에서 선호된다.

알고리즘의 동작은 크게 두 단계의 전처리와 검색 단계로 나뉜다. 전처리 단계에서는 패턴 문자열을 분석하여 나쁜 문자 이동 테이블과 좋은 접미사 이동 테이블을 생성한다. 나쁜 문자 규칙은 텍스트에서 패턴과 불일치한 문자에 기반하여 이동 거리를 결정하며, 좋은 접미어 규칙은 패턴 내에서 일치했던 부분(접미사)을 재활용할 수 있는 경우를 고려하여 더 효율적인 이동을 가능하게 한다. 실제 검색 시에는 이 두 규칙 중에서 더 큰 이동 거리를 선택하여 알고리즘을 진행한다.

보이어-무어 알고리즘의 최악의 경우 시간 복잡도는 O(n * m)에 달할 수 있지만, 평균적인 경우에는 O(n / m) 또는 그보다 더 빠른 성능을 보여준다. 이는 패턴 길이에 반비례하는 속도로, 패턴이 길수록 검색이 더 빠르게 이루어질 수 있음을 의미한다. 이러한 효율성 덕분에 이 알고리즘은 유닉스 계열 운영체제의 grep 명령어나 다양한 텍스트 편집기의 찾기 기능 등에 널리 채택되어 사용되고 있다.

라빈-카프 알고리즘은 해시 함수를 활용한 문자열 검색 알고리즘이다. 이 알고리즘의 핵심 아이디어는 검색 대상인 텍스트의 모든 가능한 길이 m의 부분 문자열에 대한 해시값을 계산하고, 이를 찾고자 하는 패턴 문자열의 해시값과 비교하는 것이다. 해시값이 일치하는 경우에만 실제 문자열을 한 문자씩 비교하여 정확한 매칭을 확인함으로써, 많은 경우 불필요한 문자 비교를 건너뛸 수 있다. 이 방식은 평균적인 경우 효율적이며, 특히 여러 개의 패턴을 동시에 검색해야 하는 경우에 유용하다.

알고리즘의 동작 과정은 다음과 같다. 먼저 패턴 문자열과 텍스트의 첫 번째 m개 문자로 이루어진 부분 문자열에 대한 해시값을 계산한다. 이후 텍스트를 한 문자씩 슬라이딩하며, 이전 부분 문자열의 해시값을 빠르게 갱신하여 새로운 부분 문자열의 해시값을 얻는다. 이때 사용되는 해시 함수는 롤링 해시로, 새로운 문자가 추가되고 오래된 문자가 제거될 때 해시값을 효율적으로 재계산할 수 있도록 설계된다. 해시값이 일치하면, 해시 충돌 가능성을 배제하기 위해 실제 문자 단위의 비교를 수행하여 최종적으로 패턴이 존재하는 위치를 찾아낸다.

이 알고리즘의 주요 장점은 평균적인 시간 복잡도가 O(n+m)에 가깝다는 점이다. 그러나 최악의 경우, 예를 들어 해시 충돌이 빈번하게 발생하는 경우에는 O(nm)의 성능을 보일 수 있다. 공간 복잡도는 추가적인 해시값 저장을 위한 상수 공간만 필요하므로 효율적이다. 라빈-카프 알고리즘은 텍스트 편집기의 찾기 기능, 데이터베이스에서의 풀텍스트 검색, 생물정보학에서의 DNA 서열 분석, 그리고 플라지어 검색이나 중복 문서 탐지와 같이 하나의 텍스트 내에서 여러 패턴을 찾아야 하는 응용 분야에서 널리 사용된다.

텍스트 편집기는 문자열 검색 알고리즘이 가장 일상적으로 활용되는 대표적인 응용 분야이다. 사용자가 문서 내에서 특정 단어나 구문을 빠르게 찾거나 일괄적으로 교체해야 할 때, 편집기의 '찾기' 및 '바꾸기' 기능은 내부적으로 효율적인 문자열 검색 알고리즘을 호출하여 작업을 수행한다. 이 과정은 사용자가 입력한 패턴을 문서 전체 텍스트에서 탐색하여 모든 발생 위치를 실시간으로 표시하거나, 지정된 새로운 문자열로 교체하는 방식으로 이루어진다.

초기의 단순한 텍스트 편집기는 단순 문자열 검색 알고리즘을 사용했지만, 문서의 크기가 커지고 반복적인 검색 요구가 늘어남에 따라 더 빠른 알고리즘의 도입이 필요해졌다. 현대의 고급 텍스트 편집기 및 통합 개발 환경(IDE)은 대용량 파일을 처리할 때 검색 성능을 최적화하기 위해 KMP 알고리즘이나 보이어-무어 알고리즘과 같은 선형 시간에 가까운 효율적인 알고리즘을 채택하고 있다. 특히, 정규 표현식을 지원하는 편집기는 더 복잡하고 유연한 패턴 매칭을 가능하게 하여, 프로그래밍 코드 리팩토링이나 로그 파일 분석 같은 작업을 강력하게 지원한다.

이러한 문자열 검색 기능은 단순한 텍스트 처리뿐만 아니라 소스 코드 편집, 마크업 언어 작성, 데이터 시각화를 위한 로그 파싱 등 다양한 전문 작업의 기반이 된다. 사용자 경험 측면에서도, 점진적 검색(타이핑하면서 실시간으로 결과 표시)이나 대소문자 구분/전체 단어 매칭 같은 부가 기능은 모두 핵심 검색 엔진 위에 구축된 편의성 레이어라 할 수 있다. 따라서 텍스트 편집기의 효율성과 기능성은 내재된 문자열 검색 알고리즘의 성능에 직접적으로 의존한다고 볼 수 있다.

데이터베이스 검색은 문자열 검색 기술의 핵심적인 응용 분야이다. 관계형 데이터베이스에서 SQL 질의어를 사용해 텍스트 데이터를 조회할 때, LIKE 연산자나 정규 표현식을 활용한 패턴 매칭이 내부적으로 문자열 검색 알고리즘에 의존한다. 특히 대용량의 레코드를 빠르게 필터링하거나, 전체 텍스트 검색 인덱스를 구축하여 키워드를 찾는 과정에서 효율적인 검색 기법이 필수적이다.

이 분야에서는 단순한 일치 검색을 넘어, 부분 일치, 접두사/접미사 검색, 와일드카드 검색 등 다양한 패턴을 처리해야 한다. 이를 지원하기 위해 데이터베이스 시스템은 종종 보이어-무어 알고리즘이나 라빈-카프 알고리즘과 같은 고급 알고리즘의 아이디어를 적용하거나, 트라이나 역색인과 같은 전용 인덱스 구조를 사용하여 검색 성능을 최적화한다. 정보 검색 시스템과 엘라스틱서치 같은 전문 검색 엔진도 데이터베이스 검색의 확장된 형태로 볼 수 있다.

데이터베이스 검색의 효율성은 시스템 전체의 응답 속도에 직접적인 영향을 미친다. 따라서 개발자는 쿼리 최적화 과정에서 문자열 검색 조건의 선택도와 데이터 분포를 고려하여 적절한 인덱싱 전략을 수립해야 한다. 이는 데이터 마이닝이나 비즈니스 인텔리전스 작업에서 대규모 텍스트 마이닝을 수행할 때도 중요한 기반 기술이 된다.

생물정보학은 유전체 서열 분석, 단백질 서열 분석, 유전자 발현 데이터 분석 등 다양한 분야에서 문자열 검색 알고리즘을 핵심 도구로 활용한다. 생물학적 데이터는 대규모의 염기 서열이나 아미노산 서열로 구성된 문자열 형태로 표현되는 경우가 많기 때문이다. 예를 들어, 특정 유전자나 프로모터 서열을 거대한 게놈 데이터베이스에서 찾거나, 단백질 데이터베이스에서 특정 기능을 가진 도메인의 서열 패턴을 검색하는 작업이 이에 해당한다.

이러한 검색은 단순히 정확히 일치하는 서열을 찾는 것을 넘어, 돌연변이나 다형성을 허용하는 유사 서열 검색이 더욱 중요하다. 이를 위해 BLAST나 FASTA와 같은 널리 사용되는 생물정보학 도구들은 효율적인 휴리스틱 알고리즘과 통계적 모델을 결합하여 방대한 데이터베이스에서 빠르게 유사성을 평가한다. 특히 시퀀싱 기술의 발전으로 생성되는 데이터의 규모가 기하급수적으로 증가함에 따라, 검색 알고리즘의 시간 복잡도와 정확도는 연구의 속도와 깊이를 결정하는 중요한 요소가 되었다.

네트워크 침입 탐지 시스템은 컴퓨터 네트워크를 모니터링하여 악의적인 활동이나 정책 위반을 탐지하는 보안 시스템이다. 이러한 시스템에서 문자열 검색 알고리즘은 네트워크 패킷의 페이로드나 로그 파일 데이터 스트림에서 알려진 악성 코드 시그니처나 공격 패턴을 실시간으로 찾는 핵심 기술로 활용된다. 예를 들어, 특정 바이러스나 웜이 네트워크를 통해 전파될 때 사용하는 고유한 코드 조각이나, SQL 삽입 공격에 사용되는 특정 쿼리 문자열을 패턴으로 정의하여 검색한다.

탐지 엔진은 수신되는 네트워크 트래픽을 연속적인 텍스트 문자열로 간주하고, 미리 정의된 위협 시그니처 데이터베이스의 패턴들을 대상으로 지속적으로 검색을 수행한다. 이 과정에서는 처리 속도와 효율성이 매우 중요하기 때문에, KMP 알고리즘이나 보이어-무어 알고리즘과 같이 최악의 경우에도 선형 시간에 가까운 성능을 보이는 알고리즘이 선호된다. 특히 라빈-카프 알고리즘은 해시 함수를 이용해 여러 패턴을 동시에 검색하는 데 유용하여, 다양한 공격 시그니처를 한 번에 스캔하는 데 적합하다.

네트워크 트래픽의 양이 방대하고 실시간 분석이 요구되는 환경에서, 문자열 검색 알고리즘의 성능은 전체 시스템의 효율성을 좌우한다. 따라서 낮은 시간 복잡도와 공간 복잡도를 갖는 알고리즘의 선택과 최적화가 필수적이다. 또한, 악성코드가 변형되거나 암호화되는 경우를 대비해 퍼지 매칭이나 정규 표현식을 결합한 확장된 패턴 매칭 기법도 함께 사용된다. 이는 단순한 문자열 일치를 넘어서 보다 복잡하고 유연한 규칙 기반의 위협 탐지를 가능하게 한다.

문자열 검색 알고리즘의 효율성을 분석할 때, 시간 복잡도는 핵심적인 평가 기준이다. 이는 주어진 텍스트 문자열의 길이를 n, 찾고자 하는 패턴 문자열의 길이를 m이라고 할 때, 알고리즘이 패턴을 찾기 위해 필요한 기본 연산의 횟수를 나타낸다. 가장 단순한 단순 문자열 검색 알고리즘은 최악의 경우 텍스트의 각 위치에서 패턴 전체를 비교하므로 시간 복잡도가 O(n*m)에 달할 수 있다. 이는 긴 텍스트에서 긴 패턴을 검색할 때 매우 비효율적일 수 있다.

보다 효율적인 알고리즘들은 전처리 과정을 도입하여 평균적이거나 최악의 경우에도 선형 시간에 가까운 성능을 보인다. 예를 들어, KMP 알고리즘은 패턴을 미리 분석하여 실패 시 되돌아갈 위치 정보를 담은 테이블을 구축한다. 이를 통해 텍스트의 각 문자를 최대 한 번씩만 검사하게 되어, 최악의 경우에도 시간 복잡도가 O(n+m)을 보장한다. 보이어-무어 알고리즘은 패턴을 오른쪽에서 왼쪽으로 비교하며, 불일치가 발생했을 때 미리 계산된 불일치 테이블과 건너뛰기 테이블을 사용해 패턴을 크게 건너뛸 수 있어, 평균적으로 매우 빠른 성능을 보이며 최악의 경우에도 O(n*m)보다는 훨씬 낫다.

라빈-카프 알고리즘은 해시 함수를 활용한 독특한 접근법을 사용한다. 패턴의 해시 값과 텍스트 내 각 가능한 부분 문자열의 해시 값을 비교하는데, 해시 값을 효율적으로 재계산하는 롤링 해시 방식을 사용한다. 이 알고리즘의 평균 및 최선의 경우 시간 복잡도는 O(n+m)이지만, 해시 충돌이 빈번하게 발생하는 최악의 경우에는 O(n*m)까지 성능이 저하될 수 있다. 따라서 실제 구현에서는 충돌을 최소화하는 강력한 해시 함수를 선택하는 것이 중요하다.

알고리즘 선택은 문제의 특성과 데이터의 성격에 따라 달라진다. 일반 텍스트 검색, 데이터베이스 인덱싱, 생물정보학에서의 유전자 서열 분석 등 응용 분야마다 텍스트와 패턴의 길이, 알파벳 크기, 반복 패턴의 유무 등이 다르기 때문이다. 개발자는 이러한 요소와 각 알고리즘의 시간 복잡도 특성을 종합적으로 고려하여 상황에 가장 적합한 검색 방법을 선택하게 된다.

문자열 검색 알고리즘의 공간 복잡도는 알고리즘이 실행되는 동안 추가적으로 사용하는 메모리 공간의 양을 의미한다. 이는 시간 복잡도와 함께 알고리즘의 효율성을 평가하는 핵심 척도이다. 공간 복잡도는 일반적으로 입력 크기(텍스트 길이 n과 패턴 길이 m)에 대한 함수로 표현되며, 점근 표기법을 사용하여 기술된다.

대부분의 기본적인 문자열 검색 알고리즘들은 추가 자료 구조를 거의 사용하지 않아 상수 공간 복잡도(O(1))를 가진다. 예를 들어, 단순 문자열 검색 알고리즘은 텍스트와 패턴을 순차적으로 비교하기 위해 몇 개의 인덱스 변수만을 유지한다. 그러나 더 효율적인 알고리즘들은 사전 계산을 위해 추가 메모리를 사용한다. KMP 알고리즘은 패턴의 접두사와 접미사 정보를 저장하는 실패 함수(또는 부분 일치 테이블)를 생성하는데, 이 테이블의 크기는 패턴의 길이 m에 비례하므로 O(m)의 공간이 필요하다. 보이어-무어 알고리즘은 불일치 발생 시 점프 거리를 결정하기 위한 건너뛰기 테이블을 사용하며, 이는 사용되는 문자 집합(예: ASCII 코드)의 크기에 따라 O(문자 집합 크기)의 공간을 요구한다.

공간 복잡도의 선택은 알고리즘의 적용 환경에 중요한 영향을 미친다. 임베디드 시스템이나 메모리 자원이 제한된 환경에서는 O(1)의 공간을 사용하는 알고리즘이 선호될 수 있다. 반면, 대용량 텍스트에서 반복적으로 검색을 수행해야 하거나 검색 속도가 매우 중요한 정보 검색 시스템이나 데이터베이스 인덱싱 엔진에서는 O(m) 또는 O(문자 집합 크기)의 추가 메모리 투자가 정당화된다. 라빈-카프 알고리즘은 해시 값을 계산하고 비교하는 과정에서 일반적으로 O(1)의 추가 공간만을 사용하지만, 해시 충돌을 처리하기 위한 연결 리스트 등을 관리할 경우 공간 사용량이 증가할 수 있다.