(TIL) 2025-01-02

문자열

---

• 문자열(String): 문자(character)의 순서(sequence) 또는 배열(array). (예: “hello”는 문자 ‘h’, ‘e’, ‘l’, ‘l’, ‘o’로 구성된 배열)
• 알파벳 집합: 문자열은 특정 문자 집합(예: ASCII, Unicode)을 기반으로 정의된다.
  • ASCII: 각 문자를 1바이트로 표현.
  • Unicode: 다양한 언어와 기호를 지원하며, 가변 길이 인코딩(예: UTF-8, UTF-16)을 사용.

문자열 자료구조의 구현 방식

문자열의 저장 및 조작 방식은 여러 가지 방법으로 구현됩니다.

1. 배열 기반 문자열 문자열은 보통 고정 길이 또는 가변 길이의 배열로 저장됩니다. 각 문자는 메모리의 연속된 공간에 저장된다.

• 장점 문자에 빠른 접근 가능(인덱싱). 단순한 구조.
• 단점 불변 문자열에서는 새로운 문자열을 생성해야 수정 가능. 길이 확장이 어렵거나 추가 메모리 할당이 필요.

char str[] = "hello"; // C에서 배열 기반 문자열

1. 링크드 리스트 기반 문자열 문자열의 각 문자는 노드에 저장되고, 노드는 다음 문자를 가리키는 포인터를 포함. 가변 길이 문자열에서 삽입과 삭제가 효율적.

• 장점 문자열 길이가 고정되지 않으므로 동적 처리 가능. 특정 위치에 문자 삽입/삭제가 효율적.
• 단점 추가적인 포인터 메모리 필요. 인덱스 접근 속도가 느림.

[h] -> [e] -> [l] -> [l] -> [o]

1. 트라이(Trie) 트리는 문자열을 효율적으로 저장하고 검색하기 위한 자료구조. 각 노드는 문자와 그 문자로 시작하는 하위 문자열을 나타냄.

• 장점 문자열 검색, 접두사 검색(prefix search)에 효율적. 사전(Dictionary) 구조에 적합.
• 단점 노드가 많아 메모리 사용량이 큼.

        (root)
       /   |   \
      h    w    b
     /    /     \
    e    o       a
   /    /         \
  l    r           t

1. 압축 문자열(Compressed Strings) 문자열을 효율적으로 저장하기 위해 압축 기법을 사용. 일반적인 방법으로 런렝스 인코딩(RLE), 허프만 코딩 등이 있음.

• 장점 메모리 절약. 대용량 데이터 처리에 적합.
• 단점 문자열 접근과 수정이 복잡. 압축 해제가 필요.

1. 로프(Rope) 긴 문자열을 작은 조각으로 나누어 이진 트리 구조로 저장. 조각은 수정, 병합, 분할이 효율적.

• 장점 문자열 조작(삽입, 삭제, 병합)에 효율적. 메모리 복사가 줄어듦.
• 단점 작은 문자열 처리에는 비효율적.

    Rope
    /    \
"Hello" " World"

문자열의 불변성

• 자바스크립트 문자열은 불변(immutable)이다. 이는 문자열의 내용을 변경할 수 없음을 의미한다. 대신 문자열을 조작하는 경우 항상 새로운 문자열이 생성된다.

let str = "Hello";
str[0] = "h"; // 무시됨, 문자열은 변경되지 않음
console.log(str); // "Hello"

str = str + " World"; // 새로운 문자열이 생성됨
console.log(str); // "Hello World"

문자열의 인덱스와 길이

• 문자열은 0부터 시작하는 인덱스를 통해 각 문자를 접근할 수 있다.
• .length 속성을 사용하면 문자열의 길이를 알 수 있다

const str = "Hello";
console.log(str[0]); // "H"
console.log(str.length); // 5