알고리즘) 문자열(1)

 

 

왜 r+2[   ]

 

 

---

 

 

 

 

내 앞 팀들의 인원수를 모두 더한 값"**이 곧 **"나의 시작 번호"**가 되는 수학적 원리입니다.

 

 

 

 

 

 

이제 aux에 있는 걸 다시 a로 옮겨야 하는데, 루프는 **i = lo (100)**부터 시작합니다.

• i가 100일 때, aux의 0번 값을 가져와야 함  100 - 100 = 0
• i가 101일 때, aux의 1번 값을 가져와야 함  101 - 100 = 1
• i가 110일 때, aux의 10번 값을 가져와야 함  110 - 100 = 10

공식이 보이시나요?

a[i] = aux[i - lo]

여기서 i - lo가 바로 **"전체 주소(i)에서 시작 주소(lo)를 빼서 0부터 시작하는 상대적인 번호로 바꾸는

 

 

 

 

 

 

 

 

for (int i = lo; i <= hi; i++)
a[i] = aux[i-lo];

 

(재귀할떄도 lo+)

 

 

 

count[r+1] += count[r];
이 루프를 돌고 나면 count[0]은 무조건 0이 됩니다. (그 전 단계에서 count[0]에는 아무것도 안 더했으니까요.)

 

자, count[0]이 0이라는 건 무슨 뜻일까요?
**"제일 첫 번째 문자 그룹은 aux의 0번 인덱스부터 집어넣어라"**라고 명령을 내린 겁니다.

 

 

 

 

 

 

우리가 정렬하려는 전체 배열 a의 크기는 100입니다. 그런데 지금은 재귀 호출이 깊게 들어와서 **50번 칸부터 54번 칸까지(총 5개)**만 정렬하고 있다고 가정해봅시다.

• lo = 50
• hi = 54

이 5개 구역에 들어있는 글자가 다음과 같다고 칩시다. (첫 글자 기준)
a[50]="apple", a[51]="banana", a[52]="ace", a[53]="box", a[54]="air"

2. count 배열이 계산하는 것 (상대적 위치)

이 코드에서 count 배열이 계산하는 숫자는 **"지금 내가 보고 있는 이 5명 중에서 몇 번째인가?"**입니다.

1st, 2nd, 3rd loop를 다 돌고 나면 count 배열에는 이런 식의 숫자가 남습니다. (계산 과정 생략하고 결과만 보면)

• 'a'로 시작하는 애들: 3명 (apple, ace, air) -> 얘네는 이 구역에서 0, 1, 2번째를 차지함.
• 'b'로 시작하는 애들: 2명 (banana, box) -> 얘네는 이 구역에서 3, 4번째를 차지함.

이때, count[0] (첫 번째 문자인 'a'의 시작점) 값은 0이 됩니다.
그리고 count[1] (두 번째 문자인 'b'의 시작점) 값은 3이 됩니다.

 

 

우리가 가진 count[1] = 3이라는 정보는 **"기준점(lo)으로부터 3칸 뒤"**라는 뜻입니다.

• 진짜 시작 위치 = lo (기준점 50) + count[1] (상대적 거리 3) = 53번 인덱스
• 진짜 끝 위치 = lo (기준점 50) + count[2]-1 (상대적 거리 4) = 54번 인덱스

 

 

 

 

 

 

1. LSD에서의 방식: aux[--count[key]] (뒤에서부터 채우기)

보통 알고리즘 교재에서 LSD를 설명할 때 이 방식을 많이 사용합니다.

• 누적합의 의미: count[r]이 r이라는 문자가 끝나는 **마지막 위치(Exclusive)**를 가리키게 설계합니다.
• 채우는 방향: 배열을 뒤에서부터(hi to lo) 읽으면서 버킷의 뒷칸부터 채워 넣습니다.
• 증감 연산자: 뒷칸을 먼저 차지해야 하므로, **전위 감소(--)**를 사용하여 인덱스를 하나 줄인 뒤 그 자리에 데이터를 넣습니다.

---

2. 현재 MSD 코드의 방식: aux[count[key+1]++] (앞에서부터 채우기)

제시해주신 MSD 코드(Robert Sedgewick의 방식)는 이와 정반대입니다.

• 누적합의 의미: 2단계 누적합 루프와 +2, +1 오프셋 계산 덕분에, count[charAt(...) + 1]은 해당 문자 그룹이 시작되는 **첫 번째 위치(Inclusive)**를 가리키게 됩니다.
• 채우는 방향: 배열을 앞에서부터(lo to hi) 읽으면서 버킷의 앞칸부터 차곡차곡 채워 넣습니다.
• 증감 연산자: 현재 count가 가리키는 시작 지점에 데이터를 바로 넣고, 다음 데이터를 위해 인덱스를 하나 키워줘야 하므로 **후위 증가(++)**를 사용합니다.

 

 

 

 

 

• Java String 내부 구조:
  • String 소스코드를 보면 내부적으로 byte[] 배열에 문자가 저장됩니다. (과거엔 char[]였으나 변경됨)
  • 이 배열은 **final**로 선언되어 있습니다. 즉, 한 번 저장되면 수정이 불가능한 불변(Immutable) 객체입니다.
  • hashcode 값을 캐싱하여 가지고 있습니다.

 

 

 

 

 

 

 

 

 

 

 

추가)

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

 

 

계수 정렬은 "숫자의 크기 자체"**를 보고 한 번에 정렬하는 방식이고,

**기수 정렬은 "숫자의 자릿수"**를 나누어 여러 번 정렬하는 방식입니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

(계수정렬)

주소는 arr에서 찾아야하는거고

실제 값은 A에서 찾아야 하니깐,

(B[--  arr[A[i]] 위치 ] = A[i]  값)

 

 

 

자바에서 char(문자)는 내부적으로 정수(ASCII/Unicode 값)로 취급되기 때문에 가능
Integer.valueOf('4')하ㅣ면 안되고 
Integer.valueOf(String.valueOf('4))해야하나 

 

 

 

 

 

 

 

 

 

 

1. 1st loop: 빈도 세기 단계 (Counting)

코드로 치면 count[c+2]++ 를 한 직후의 모습입니다.

• 0번 칸: 항상 0입니다. (아무도 여기에 개수를 세지 않으니까요.)
• 1번 칸: **-1(단어 끝)**이 몇 명인지 적혀있습니다.
• 2번 칸: **'a'**가 몇 명인지 적혀있습니다.
• 3번 칸: **'b'**가 몇 명인지 적혀있습니다.
• 핵심: 문자의 원래 번호보다 두 칸 뒤에 인원수를 적어놓은 상태입니다.

2. 2nd loop: 주소 생성 단계 (Cumulative Sum)

코드로 치면 count[i+1] += count[i] 를 해서 앞 칸 숫자를 계속 더한 직후입니다. 이제 숫자가 **'인원수'**에서 **'의자 번호(위치)'**로 바뀝니다.

• 0번 칸: 0번 칸은 그대로 0입니다. (그래서 -1의 시작 위치가 됩니다.)
• 1번 칸: 앞의 0번 칸(0) + 원래 1번 칸(-1의 수)을 더한 값입니다. (이게 'a'의 시작 위치가 됩니다.)
• 2번 칸: 앞의 1번 칸(-1의 수) + 원래 2번 칸(a의 수)을 더한 값입니다. (이게 'b'의 시작 위치가 됩니다.)
• 핵심: 한 칸씩 밀리면서 더해졌기 때문에, count[c+1] 칸에 문자 c가 시작할 주소가 예쁘게 들어앉은 상태입니다.

3. 3rd loop: 데이터 이동 및 경계선 확정 단계 (Moving)

실제로 데이터를 aux[]로 옮기면서 count[c+1]++ 를 계속 수행한 후의 최종 모습입니다.

• 0번 칸: 원래 0이었는데, -1 그룹 애들이 들어올 때마다 ++를 했습니다. 그래서 다 끝난 뒤에는 -1 그룹이 끝난 지점의 숫자가 적혀있습니다. (결국 -1의 총 인원수와 같음)
• 1번 칸: 'a' 그룹 애들이 들어오면서 ++를 했습니다. 그래서 -1부터 'a'까지 다 합친 인원수가 적혀있습니다.
• 핵심: 이 단계가 끝나면 count 배열은 각 그룹의 **"끝나는 경계선"**이 됩니다.

 

 

count[r]이 이미 r-1번 문자가 끝난 지점이자 r번 문자가 시작되는 지점을 가리키고 있기 때문입니다