알고리즘) 문자열(2)

 

 

시간복잡도

코드

 

---

 

 

• 최적화 (Cutoff): 데이터 양이 적어지면(하이-로우 갭이 작으면) 재귀를 멈추고 **삽입 정렬(Insertion Sort)**을 사용합니다. 이때 앞부분 d개 글자는 이미 같으므로, 그 이후부터 비교하도록 최적화합니다.
• 성능: 접두사가 다양하면 빠르지만, 모든 문자열이 비슷하면 최악의 경우( W⋅N )까지 느려질 수 있습니다.

 

 

 

② 3-way String Quick Sort

• 원리: 퀵 소트의 피봇(Pivot) 개념과 MSD의 방식을 결합한 것입니다.
• 동작: 피봇 문자열의 d번째 문자를 기준으로 전체 데이터를 세 그룹으로 나눕니다.
  1. 피봇보다 작은 문자 그룹
  2. 피봇과 같은 문자 그룹
  3. 피봇보다 큰 문자 그룹
• 재귀: '작은 그룹'과 '큰 그룹'은 현재 위치 d에서 다시 정렬하고, '같은 그룹'만 다음 글자인 d+1 위치로 넘어가 정렬합니다.
• 장단점: MSD처럼 큰 카운트 배열을 매번 만들 필요가 없어 메모리 효율적이지만, 안정 정렬(Stable Sort)이 아니라는 단점이 있습니다.

 

 

 

 

 

트라이(Trie) 자료구조

문자열 검색을 위해 이진 검색 트리나 해싱을 쓸 수 있지만, 각각 단점이 있습니다. (트리는 비교 비용이 비싸고, 해싱은 범위 검색/접두사 검색이 안 됨). 이를 해결하는 것이 **트라이(Trie)**입니다.

① 구조와 특징

• 구조: 각 노드는 알파벳 개수( r)만큼의 링크(포인터)를 가집니다.
• 검색 원리: 루트부터 시작해 문자열의 각 글자를 따라 내려갑니다. 데이터가 100만 개든 1000만 개든, 문자열의 길이만큼만 내려가면 검색이 끝납니다.
• 값 저장: 문자열이 끝나는 지점의 노드에 Value를 저장합니다. 중간 노드들은 값이 없을 수도 있습니다.

② 주요 연산

• Get (검색): 키를 따라 내려가다 링크가 null이거나 끝에 도달했는데 Value가 없으면 찾는 값이 없는 것입니다.
• Put (삽입): 키를 따라 내려가며 노드가 없으면 새로 생성하고, 마지막 글자 위치에 값을 저장합니다.
• Prefix Search (접두사 검색): "김"으로 시작하는 모든 이름을 찾고 싶을 때, "김"까지 내려간 후 그 아래에 달린 모든 자식 노드를 탐색하여 결과를 큐(Queue)에 담아 반환합니다. 이때 경로를 기억하기 위해 StringBuilder를 사용합니다.

③ Delete (삭제) - Pruning(가지치기)

• 단순히 마지막 노드의 Value를 null로 바꾸는 것으로 끝나지 않습니다.
• 삭제 후, 해당 노드에 자식 링크가 하나도 없고 Value도 없다면 불필요한 메모리 방지를 위해 해당 노드를 부모로부터 제거해야 합니다. 이 과정을 루트 방향으로 올라가며 재귀적으로 수행하여 더 이상 쓸모없는 경로를 지웁니다.

 

 

 

 

---

 

반복문 안에서 결정이 나지 않았다는 것은 **"두 문자열 중 짧은 쪽이 끝날 때까지 모든 글자가 완벽하게 똑같았다"**는 뜻입니다.

 v.length() < w.length()

 

 

else { // <--- 이 부분이 문제입니다!
        return true; 
    }
}

• 문제 내용: 이 코드는 두 문자가 **같을 때(v1 == w1)**도 바로 true를 리턴하고 함수를 끝내버립니다.
• 예시: v = "apple", w = "apple" 이라고 해봅시다.
  1. 첫 번째 글자 'a'와 'a'를 비교합니다.
  2. v1 > w1이 아니므로 else 블록으로 들어갑니다.
  3. true를 리턴합니다.
  4. 결과: "apple"이 "apple"보다 작다는 잘못된 결과가 나옵니다. (원래는 false여야 함)

두 문자가 같으면 결론을 내리지 말고, 그다음 문자로 넘어가야(continue) 합니다.

(if 두개 써야함)

 

 

 

 

lsd

w(n+r)

코드에서 반복문 구조 보면 

 

msd

 

 

 

최악의 상황에서 MSD는 LSD가 하는 일을 재귀라는 형식을 빌려서 똑같이 다 하기 때문

 

(lsd랑 코드 비슷한 부분 ) 

         for (int i = 0; i < n; i++) {
             count[charAt(a[i],d)+2]++;
         }
         for (int i = 1; i <r ; i++) {
             count[i]+=count[i-1];
         }

         for (int i = 0; i <n ; i++) {
             aux[ count[charAt(a[i],d)+1]++ ]=a[i];
         }
         //이해가 안감
         for (int i = 0; i < n; i++) {
             a[i]=aux[i-lo];
         }

 

 

 

 

 

 

 

w는 "재귀가 얼마나 깊이 내려갈 수 있는가(최대 깊이)"를 의미

 

 

 

 

 

 

 

 

MSD가 스테이블한 이유는 '앞에서부터 넣어서'가 아니라, 데이터를 넣을 때 '먼저 온 놈을 앞자리에 넣어주는 법칙'을 지키기 때문입니다.

 

 

 

gt일때

i++안하는 이유

 

 

우리가 i번째 자리에 있는 문자열(t)을 검사했는데, 피봇(v)보다 크다는 것을 알게 되었습니다.

1. 동작: 큰 놈이니까 맨 뒤쪽 구역인 gt 자리에 있는 문자열과 자리를 바꿉니다(exch).
2. 질문: 자, 이제 i 자리에 새로 온 문자열(원래 gt 자리에 있던 놈)은 어떤 놈인가요?
3. 답: 모릅니다. 이 문자열은 아직 루프가 도달하지 않은 구역(gt)에서 가져온 것이기 때문에, 이 녀석이 피봇보다 작은지, 큰지, 아니면 같은지 아직 한 번도 검사하지 않은 상태입니다.

 

 

 

lt일때는 

 

내가 지금 i번째 놈을 검사했는데 피봇보다 작아요. 그럼 왼쪽(lt 쪽)으로 보내야겠죠?

1. 동작: exch(a, lt, i)를 합니다.
2. 질문: 자, 이때 lt 자리에 있던 놈은 원래 어떤 놈이었나요?
3. 답: 위 구역 나눔을 보세요. lt는 "피봇과 같은 놈들 구역"의 시작점입니다. 즉, lt 자리에는 항상 피봇과 같은 값이 들어있습니다. (이미 앞선 루프에서 검사가 끝난 놈들이죠!)

 

 

lo ~ lt-1	작은 놈들 구역	글자 < v (피봇보다 작음)
lt ~ gt	같은 놈들 구역	글자 == v (피봇과 똑같음)
gt+1 ~ hi	큰 놈들 구역	글자 > v (피봇보다 큼)

 

아무튼 lt,gt포함 안된다는거 같은데 

 

 

 

 

 

 

녹취록에서 **"잘 안 나누어지면 구리다"**고 한 것은 MSD이고, 3-way String QuickSort는 바로 그 MSD의 단점(긴 접두사에서 발생하는 메모리/시간 낭비)을 보완하기 위해 카운트 배열 없이 3구역 분할만 사용하기 때문에 긴 접두사에 더 강한 것입니다!

 

 

 

 

결론부터 말씀드리면: "제일 처음 만든 root 노드는 'a'가 아닙니다. 'a', 'b', 'c' 등 모든 글자의 '뿌리(시작점)' 역할을 하는 빈 노드입니다."

1. 트라이의 구조: 노드는 '방'이고, 글자는 '문'이다

트라이에서 **노드(x)**는 글자 그 자체가 아니라, **글자들이 나가는 '출발점'**입니다.

• 맨 처음 root = new Node()가 하는 일:
  아무 글자도 없는 **"중앙 로비"**를 하나 만드는 것입니다. 이 로비에는 256개(혹은 알파벳 개수만큼)의 문(next 배열)이 있습니다.

 

 

 

 배열 전체를 넘기는 게 아니라, "배열의 특정 칸 하나"를 넘기고 있습니다. 그리고 x == null 체크는 바로 그 **"배열 칸이 비어있는지"*

 

 

 

 

 

1. "길이 없으면 만든다" (Creation vs. Failure)

• get (Search): 내려가다가 x == null을 만나면 "찾는 단어가 없네" 하고 null을 반환하며 종료합니다. (포기)
• put (Insertion): 내려가다가 x == null을 만나면 **x = new Node()**를 통해 새로운 노드를 만듭니다. 즉, 길이 없으면 길을 만들면서 끝까지 내려갑니다.

2. "연결을 갱신한다" (x.next[c] = put(...))

이 부분이 구조적으로 가장 큰 차이입니다.

• get: 단순히 return get(...)을 합니다. 밑에서 가져온 결과값을 부모에게 전달만 하면 끝입니다.
• put: x.next[c] = put(...) 처럼 반환된 값을 다시 자식 노드 자리에 대입합니다.
  • 왜 그럴까요? 방금 만든(또는 수정한) 자식 노드를 부모 노드와 확실하게 연결하기 위해서입니다