an 다음부터~퀵소트
np부분
=
(앞부분은 W임
그리고 D에서는 vj로 하는데
W에서는 j로
n-k!
k!
(n-k)+k 하니깐 ==n임
공간복잡도
배낭문제
가격을 더해야지
lsd에서
count는 갯수에 대한거니깐
전위 감쇠(--count)를 쓰는 것이 일반적입니다. 왜 그런지 이유를 볼게요.
예시: 'A'라는 글자가 3개(0, 1, 2번 인덱스에 들어갈 예정)라고 가정
- 앞선 누적합 루프를 거치면 count['A']에는 3이라는 숫자가 들어있게 됩니다 (A가 끝나는 지점의 개수).
- 배열의 인덱스는 0부터 시작하므로, 3개인 경우 마지막 인덱스는 2가 되어야 합니다.
- 따라서 count값인 3을 바로 인덱스로 쓰면 에러(IndexOutOfBounds)가 납니다.
- 그래서 **--count (전위)**를 사용하여 3을 2로 먼저 깎은 다음에 그 자리에 데이터를 넣는 것입니다.
msd
- **--count**를 쓰는 이유는: 누적 합이 '개수'를 의미해서, 인덱스 범위를 벗어나지 않으려고 먼저 줄이는 것입니다.
- **count++**를 쓰는 이유는: 누적 합을 할 때 미리 한 칸 밀어둬서 **현재 값이 곧 '시작 인덱스'**이기 때문입니다. 하나 넣었으니 다음 칸을 가리키려고 나중에 키우는 것입니다.
젤 처음에 갯수 넣을떄는 count+2자리에,
실제 값넣을떄는 +1자리에
마지막 재귀할떈 그대로 하던데(p)
그리고 lsd는 자릿수만큼 반복하고, 이건 재귀로 cutoff까지 반복함,
재귀의 차이라서 마지막 부분차이있는것이고 ?
b(또는 aux) 배열은 0번 인덱스부터 채워지는
N-1부터 할 필요 없이
count 배열은 R+2개나 만들었는데, 왜 재귀는 딱 R번만 돌리는지
+2의 의미: 배열 크기를 넉넉하게 잡기 위한 공간적 여유였을 뿐, 실제 문자의 종류가 R+2개인 것은 아닙니다. 실제 문자는 0~R-1까지 R개입니다
재귀부분
우리가 전교생 중 100번부터 150번까지(lo=100, hi=150) 학생들을 데려다가 **'성씨'**별로 복도에 줄을 세웠다고 칩시다.
- 김씨 그룹: 100번 ~ 119번
- 이씨 그룹: 120번 ~ 139번
- 박씨 그룹: 140번 ~ 150번
이제 1단계(성씨 정렬)가 끝났으니, 2단계로 **"김씨들끼리만 모여서 이름의 두 번째 글자로 다시 정렬"**을 시켜야 합니다. 이때 선생님이 **"김씨들 다 일로 와!"**라고 하려면 시작 번호와 끝 번호를 알아야겠죠?
-1이 붙는 이유는 . 바로 **"내 그룹이 끝나는 지점은 다음 그룹이 시작되는 지점의 바로 앞 칸"**이기 때문입니다.
왜 i <= hi가 아니라 i <= gt
만약 i <= hi까지 돌린다면, 이미 우리가 gt--를 통해 **"여기는 기준보다 큰 놈들이라고 확정 지어놓은 구역"**까지 i가 다시 들어가서 중복으로 검사하게 됩니다.
| 구분 | MSD String Sort | 3-way String QuickSort |
| 기반 알고리즘 | Counting Sort (계수 정렬) | Quick Sort (퀵 정렬) |
| 분할 방식 | R-way (글자 수만큼, 256개 등) | 3-way (작다, 같다, 크다) |
| 메모리(공간) | 많이 사용 (aux, count 배열 필요) | 매우 적게 사용 (제자리 정렬) |
| 안정성 (Stable) | Stable (순서 유지됨) | Not Stable (순서 바뀔 수 있음) |
| 최고의 성능 | 랜덤한 문자열 정렬 시 유리 | 앞부분이 비슷한 문자열이 많을 때 유리 |
| 캐시 효율 | 낮음 (메모리 여기저기 점프함) | 높음 (연속된 메모리 사용) |
- MSD / 3-way 퀵소트: 흩어진 카드(문자열)들을 순서대로 줄 세우는 방법(동작)
- 트라이(Trie): 나중에 언제든 원하는 단어를 꺼내 볼 수 있게 정리해두는 서랍장(저장 공간)
트라이에서
언제 멈추는지[ ]
d == key.length()<<트라이에서는 계속 이거인것같은데
(d < key.length() - 1)
왜 else 블록 안에 재귀 호출이 있어야 하나요? (char c = key.charAt(d); 관련)
이유: 인덱스 범위 오류(StringIndexOutOfBoundsException) 방지 및 목적지 도달 확인
- if (d == key.length()) 조건이 참이라는 것은, 삭제하고자 하는 단어의 마지막 글자 노드에 도착했다는 뜻입니다.
- 만약 이 재귀 호출을 else 밖으로 빼버리면 어떻게 될까요?
- d가 key.length()인 상태에서 key.charAt(d)를 호출하게 됩니다.
- 자바의 문자열 인덱스는 0부터 length-1까지이므로, key.charAt(key.length())는 에러(IndexOutOfBounds)를 발생시킵니다.
- 또한, 단어의 끝에 도착했다면 더 이상 아래로 내려갈 필요가 없으므로 else 처리를 통해 "찾는 과정"과 "도착 후 처리 과정"을 명확히 분리하는 것입니다
흐름
- 내려가기 (Going Down): else 문 안의 delete(x.next[c], key, d+1)이 호출되면서 단어의 끝을 향해 계속 깊숙이 들어갑니다. (이때는 아직 아래쪽의 for문이나 return null 로직이 실행되지 않고 대기 상태입니다.)
- 목적지 도착: d == key.length()에 도달하여 x.val = null;을 실행합니다. (데이터만 지운 상태)
- 올라오기 (Backtracking - 중요!): 이제 재귀 함수가 반환(return)되면서 거꾸로 거슬러 올라오기 시작합니다.
public void delete(String key) { root = delete(root, key, 0); }
Fast search hit and even faster search miss, but waste space!"
"찾을 때도 빠르고 못 찾을 땐 더 빠르다, 하지만 메모리 낭비가 심하다!"
접두사(Prefix)가 유사할 때의 장점
"apple", "apply", "appointment"처럼 앞부분이 겹치는 단어들이 많으면, 그 앞부분 노드들을 서로 공유합니다.
이럴 때는 단어들을 따로 저장하는 것보다 메모리 효율이 좋아집니다. ("app"까지는 노드 3개만 있으면 되니까요.)
시작이 k인지 root인지의 차이인가
트라이
tst
x.c< key.charAt(d)
key가 찾아야하는거니깐
키가 ( 현재 있는 노드보다) 크다, 작다
bst 트라이 tst
'26년1학기 > 알고리즘' 카테고리의 다른 글
| 알고리즘)문풀2 (0) | 2026.06.01 |
|---|---|
| 알고리즘) 패턴매칭 (0) | 2026.06.01 |
| 알고리즘 )3장 문풀 (0) | 2026.05.30 |
| 알고리즘 )2장 문풀 (0) | 2026.05.28 |
| 알고리즘 )1장 문풀 (2) | 2026.05.28 |