병합정렬[ ]
계수정렬이랑 버킷정렬이랑 먼차인거지
계수정렬)
저장해서 뭘하려고 하는거지(지금 정렬)
어케 정렬하지<거꾸로 돌면서
(이게 기수정렬이랑 뭐가 다른거지)
"저장해서 뭘 하려는 거지?"에 대한 답은 **"내 자리가 어딘지 '예약 번호'를 뽑아두는 것"**입니다.
- 누적합(C')의 의미: "나보다 작거나 같은 숫자가 총 몇 개인가?"를 나타냅니다. 예를 들어 숫자 5의 누적합이 10이라면, "5는 1등부터 10등 사이 어딘가에 있어야 한다"는 뜻입니다.
계수 정렬 vs 기수 정렬
① 계수 정렬 (Counting Sort)
- 방식: 숫자의 값 전체를 한 번에 봅니다.
- 한계: 숫자의 범위(K)가 너무 크면 메모리를 너무 많이 씁니다. (예: 숫자가 10억이면 크기가 10억인 배열 C가 필요함)
- 비유: 전교생 100명을 점수(0~100점)대로 한 번에 줄 세우기.
② 기수 정렬 (Radix Sort)
- 방식: 숫자를 한 번에 안 보고 자릿수별로 쪼개서 여러 번 정렬합니다. (1의 자리 정렬 -> 10의 자리 정렬 -> 100의 자리 정렬...)
- 핵심: 이때 각 자릿수를 정렬할 때 사용하는 알고리즘이 바로 계수 정렬입니다!
- 비유: 수만 장의 우편물을 번표 끝자리부터 하나씩 분류해서 쌓아 나가는 방식.
- 계수 정렬은 숫자 범위가 작을 때 쓰는 단독 정렬법이고,
- 기수 정렬은 큰 숫자를 다루기 위해 계수 정렬을 자릿수만큼 뺑뺑이 돌리는 전략입니다.
불필요한 초기화?
- 자바에서 int[]를 생성하면 모든 칸이 자동으로 0으로 채워집니다. 그래서 for문을 돌려 0을 채우는 과정은 생략해도 됩니다.
왜 new int[K+1] 인가요? (배열의 크기)
상황: 우리가 가진 숫자 중 제일 큰 숫자가 **'5'**라고 해봅시다.
- 배열의 특징: 컴퓨터는 숫자를 0번부터 셉니다.
- 우리는 숫자 '5'가 몇 개인지 기록할 칸이 필요하죠? 그러면 arr[5]라는 칸이 있어야 합니다.
- 칸을 세어볼까요? arr[0], arr[1], arr[2], arr[3], arr[4], arr[5] -> 총 6개의 칸이 필요합니다.
- 결론: 제일 큰 숫자가 K라면, 0번 칸부터 K번 칸까지 다 써야 하므로 **K + 1**개를 만들어야 "아, 나 5번 칸에 숫자 적어야지!" 할 때 에러가 안 납니다
※ B[n-1-i] = index라고 쓰면 안 되는 이유
누적합(더하기) 과정 (왜 하나요?)
**"내 앞에 몇 명이 있는지를 알아내서, 내가 들어갈 '마지막 칸 번호'를 예약하는 것"**입니다.
- 그냥 개수 세기:
- 1은 1개 있네? → arr[1] = 1
- 2는 2개 있네? → arr[2] = 2
- 누적합(더하기):
- 1까지의 합: 1 (1은 1번째 칸까지 차지해)
- 2까지의 합: 1+2 = 3 (2는 3번째 칸까지 차지해)
결과: "1은 1번 자리가 끝이고, 2는 3번 자리가 끝이야!"라는 예약표가 완성되었습니다.
--부분
번째가 왜 중요ㅕ
int element = A[n-1-i]; // 내가 지금 정렬할 '값' (예: 5)
int index = --arr[element]; // 그 값이 들어갈 '방 번호' (예: 9)
B[n-1-i] = index; // (X) 이 코드는 "결과 배열에 방 번호를 저장해라"라는 뜻입니다.ㄴㄴ
한번에 합치는 코드
arr[i]+=A[i]; ㄴㄴ
arr[i]+=1;
(우리는 갯수를 세아렸으니깐)
(가령 한개있을때를 0으로 안하고, 1로 두기로 햇음 )
(근데 배열에서는 1개있으면 0번인덱스에 있으니깐
갯수와 인덱스의 충돌
- 갯수: "지금까지 총 6개의 숫자가 줄 서 있어!"
- 인덱스(의자 번호): "의자는 0, 1, 2, 3, 4, 5번까지 있어."
자, 여기서 질문! 6번째 숫자가 들어갈 마지막 의자 번호는 몇 번일까요?
바로 5번 의자입니다.
13개 24개이면 arr[2]=6이면, 이건, 2까지가 6개있음,
그러면 아 012345>6개니깐? 번쨰보단 갯수로 생각해본다면,
"6개(갯수)"**인데, 실제로 숫자를 집어넣어야 할 곳은 **"5번(인덱스)"**입니다.
int index= --arr[element];--가 변수 앞에 붙으면(전위 연산자), **"뭐든 하기 전에 일단 1부터 빼라!"**는 뜻입니다.
- 예시: arr[5]에 숫자 10이 들어있다고 칩시다.
- int index = --arr[5]; 를 실행하면?
- arr[5]에 있는 10을 먼저 9로 바꿉니다. (업데이트)
- 그 바뀐 숫자 9를 index에 넣습니다.
- 결과: index는 9가 되고, arr[5]도 9가 됩니다.
// 현재 코드
for (int i = 0; i < arr.length; i++) {
arr[A[i]] += 1;
}- 문제점: A 배열의 크기는 n인데, 반복문은 arr.length(즉, K+1)만큼 돌고 있습니다.
- 만약 K가 n보다 크면 A[i]를 참조할 때 배열 인덱스 초과 에러가 납니다.
- 반대로 K가 n보다 작으면 배열 A의 숫자를 다 세지 못합니다.
- 해결: 숫자를 세는 것은 **원본 배열 A의 개수(n)**만큼만 돌아야 합니다.
for (i = N-1; i >= 0; i--)
걍 접근자체를 인덱스로 하는게 낫나보네
(축약형으로 할땐 더 헷갈리니깐)
후위 연산자 B[ C[A[i]]-- ] = A[i]; 일 때 순서:
- 방 번호 계산 (LHS 평가):
- 컴퓨터가 B 배열의 대괄호 안을 봅니다. C[A[i]]--가 있네요.
- C[A[i]]가 10이라고 칩시다.
- 후위(--)의 특징: "지금 당장 이 식의 결과값은 10으로 내보내고, C의 실제 값은 나중에 깎아라."
- 컴퓨터는 **"오케이, 방 번호는 10번이구나!"**라고 주소를 딱 확정 지어 버립니다. (이때 이미 C는 조용히 9가 됩니다.)
- 값 가져오기 (RHS 평가):
- = 오른쪽의 A[i] 값(예: 5)을 가져옵니다.
- 최종 배달 (Assignment):
- 아까 확정한 10번 방에 숫자 5를 넣습니다.
a=b--는 알겟는데
c[b--]=4
이렇게 b--가 =기준으로 왼쪽에 있으니깐, 이거 순서를 모르겟어
컴퓨터는 무조건 인덱스(방 번호)부터 확정 지어야 배달을 할 수 있으니까요.
a[b--]=c[++b]
왼쪽(할당받는 쪽)의 인덱스부터 결정합니다.
i가 1인 상태에서 arr[i] = (++i)를 한다면?
우리는 보통 이 코드를 보고 **"1번 칸(arr[1])에 뭔가를 넣겠구나"**라고 기대합니다. 왜냐하면 문장이 시작될 때 i는 1이었으니까요.
1. 만약 오른쪽(RHS)부터 계산한다면? (자바가 안 하는 방식)
- 오른쪽 (++i)를 먼저 계산합니다.
- i가 2가 되고, 값은 2가 나옵니다.
- 이제 왼쪽을 봅니다. arr[i]에 넣으려고 보니, 방금 오른쪽 계산하느라 i가 2로 바뀌어 버렸네요?
- 결국 **arr[2]**에 값이 들어갑니다.
- 결과: 나는 1번 칸에 넣으려고 했는데, 오른쪽 계산하는 사이에 주소가 2번 칸으로 바뀌어 버린 거죠. (황당한 상황)
2. 자바 방식 (왼쪽 주소부터 결정 - LHS 우선)
- 왼쪽 arr[i]를 먼저 봅니다.
- i가 1이니까, **"오케이, 무조건 arr[1]에 넣을 거야!"**라고 주소를 딱 찜(Lock) 해버립니다.
- 그다음에 오른쪽 (++i)를 계산합니다. i가 2가 되고 값도 2가 됩니다.
- 이미 찜해둔 **arr[1]**로 가서 값 2를 넣습니다.
- 결과: 문장이 시작될 때의 i 값을 기준으로 안전하게 1번 칸에 배달되었습니다.
[문제] 다음 코드가 실행된 후, 각 배열의 상태와 변수 b의 값을 예측해보세요.
상황 설정
- int[] A = {0, 0, 0, 0, 0}; (0번~4번 인덱스)
- int[] C = {10, 20, 30, 40, 50};
- 변수 b의 초기값: int b = 2;
문제 1 (기초)
A[b++] = C[--b];문제 2 (사용자님이 질문한 패턴)
(초기값 b = 2에서 다시 시작한다고 가정)
A[b--] = C[++b];문제 3 (심화 - 조금 더 복잡함)
(초기값 b = 2에서 다시 시작한다고 가정)
A[--b] = A[b++] + C[b--];
1. 왼쪽 주소 계산에서 후위 연산자(i++)도 먼저인가?
ㅇㅇ
2. 안쪽에 있는 인덱스 먼저 계산하나? (a[b[--a[b++]]++])
이런 '괴물' 같은 코드는 **"가장 안쪽 + 가장 왼쪽"**부터 양파 껍질을 벗기듯이 계산됩니다. 자바의 규칙은 **"왼쪽에서 오른쪽으로, 안쪽에서 바깥쪽으로"**입니다.
3. A[--b] = A[b++] + C[++b]
아무튼 할당하는곳:왼쪽부터라는거임
(굳이 문제풀어볼필요는 없을지도)
B[i++] = 100; 처리의 진짜 순서
컴퓨터 내부에서는 = (대입)이 일어나기 전에 이미 주소 계산이 끝납니다.
- LHS(왼쪽) 주소 찾기 시작: B[i++]를 계산하러 갑니다.
- 값 추출: 현재 i의 값인 5를 꺼냅니다. (이 5가 인덱스로 예약됩니다.)
- 즉시 증가 (핵심!): 5를 꺼내자마자 컴퓨터는 i를 6으로 바꿔버립니다. (아직 100은 B 근처에도 못 갔습니다!)
- RHS(오른쪽) 확인: 이제 = 오른쪽의 100을 확인합니다.
- 최종 대입: 아까 예약해둔 B[5] 칸에 100을 집어넣습니다.
b[i++]=i;
// for (int i = 0; i < C.length; i++) {
// if(i==0){
// continue;//왜 이런부분없었지
// }
// //i=1부터 시작햇으니깐
// }
//걍 nowIndex안쓰고 싶어서 처음부터 인덱스로 계산할수있도록 만든건가
for (int i = 0; i < n; i++) {
int nowIndex=n-1-i;
B[ --C[ A[nowIndex] ] ]=A[nowIndex];
}
- C 배열 리셋: 자릿수가 바뀔 때마다(1의 자리 -> 10의 자리) 개수 세기 표(C)는 무조건 새로 만들거나 0으로 초기화해야 합니다.
B[ --C[ A[nowIndex] ] ]=A[nowIndex];인지
B[ C[ --A[nowIndex] ] ]=A[nowIndex];인지
우리가 깎아야( -- ) 할 대상은 '실제 숫자'가 아니라 '번호표(갯수)'이기 때문에 --가 C 앞에 붙어야 합니다.
int digit = (A[nowIndex] / exp) % 10;
한번에 하고싶으면 괄호치면되네
// 1. 이번에 정렬할 자릿수(0~9)를 먼저 구합니다.
int digit = (A[nowIndex] / exp) % 10;
// 2. 그 자릿수의 번호표(C)를 깎아서 인덱스를 구하고 배치합니다.
B[ --C[digit] ] = A[nowIndex];
이부분은 계수정렬이랑 다르네 계수정렬떄는 nowIndex였잖아
C 배열의 인덱스에 들어가는 값이 **[숫자 그 자체]**에서 **[특정 자릿수]
C가 0~9니깐
(계수정렬에서는 0~k가 c가 가질수있는 인덱스였고)
Arrays.copyOf의 진짜 문법
이 메서드는 "기존 배열을 복사해서 새로운 배열을 만들 때
방법 A: System.arraycopy (가장 빠르고 정확한 방법)
이미 만들어진 두 배열 사이에서 값을 복사할 때 씁니다.
// B의 0번부터 n개를 A의 0번 위치로 복사해라!
System.arraycopy(B, 0, A, 0, n);방법 B: 단순 for 문 (공부할 때 가장 추천하는 방법)
가장 직관적이고 실수가 없습니다.
for (int i = 0; i < n; i++) {
A[i] = B[i];
}
A[realJudge]의 실수: "지난번 대답을 재활용하면 안 돼요"
- 문제: B[ --C[ A[realJudge] ] ] 부분입니다.
- 이유: realJudge는 이전 for문이 다 끝나고 남은 찌꺼기 값입니다.
- 설명: 정렬할 때는 **지금 내 손에 들고 있는 숫자(A[nowIndex])**가 몇 점인지(자릿수)를 그 자리에서 다시 계산해서 그 번호표(C)를 찾아가야 합니다. 남이 계산했던 값을 쓰면 엉뚱한 자리에 앉게 됩니다.
**"방금 본 주소를 모든 편지에 똑같이 적용하려는 실수"**를 하고 있습니다.
1. 상황 예시 (숫자: 12, 35, 42를 정렬 중)
현재 10의 자리를 기준으로 정렬하고 있다고 가정합시다.
[루프 1: 갯수 세기]
- 12를 봅니다 → 10의 자리는 1. (realJudge = 1)
- 35를 봅니다 → 10의 자리는 3. (realJudge = 3)
- 42를 봅니다 → 10의 자리는 4. (realJudge = 4)
- 루프 종료! 이때 변수 realJudge에는 마지막으로 계산했던 4가 담겨 있습니다.
[루프 2: 결과 배열 B에 담기] - 사용자님의 코드 방식
이제 숫자를 하나씩 꺼내서 B에 담아야 합니다.
- 첫 번째 숫자 12를 집어 들었습니다.
- 이제 어디(C)에 물어봐야 할까요? 당연히 **12의 10의 자리인 '1'**에 물어봐야 합니다.
- 그런데 사용자님의 코드는? C[realJudge] 즉, **C[4]**에게 물어봅니다.
- 왜? realJudge가 아까 루프 1이 끝날 때 4인 상태로 멈춰 있었거든요.
- 결과: 숫자 12가 10의 자리가 4인 숫자들이 들어갈 자리에 엉뚱하게 들어갑니다.
2. 왜 "재활용"하면 안 된다고 하나요?
realJudge는 루프 1에서 마지막 숫자를 처리하고 남은 흔적일 뿐입니다.
- 루프 2에서 12를 집어 들었으면, 그 12한테 다시 물어봐야 합니다. "야, 너 10의 자리가 뭐야?" → "1인데요?" → "오케이, 그럼 C[1] 번호표를 깎자!"
- 그다음 35를 집어 들었으면 또 물어봐야 합니다. "너는 뭐야?" → "3인데요?" → "오케이, C[3] 깎자!"
왜 r을 미리 계산할 필요가 없나요?
사용자님은 아까 while문을 따로 써서 r (최대 자릿수)을 미리 구해두셨죠?
하지만 위에서 보신 것처럼, maxNum / exp > 0이라는 조건 하나만 걸어두면, 컴퓨터가 알아서 나눗셈을 해보다가 "어? 이제 나눌 숫자가 없네(0이네)?" 하고 스스로 멈춥니다.
//c여기서 선언해야하나, 매번 배열 만들필요있나"
상관없다네
c에 초깃값 넣을때도, 함축해서 할수있네(변수안쓰고)
(그러면 나중에, --있는 부분이랑 동일하네)
C[(A[i] / exp) % 10]++;
| 바구니의 의미 | 바구니 하나 = 값 하나 (예: 5번 바구니엔 5만 들어감) | 바구니 하나 = 0~9 숫자 (자릿수 기준) | 바구니 하나 = 값의 범위 (예: 10~20점 바구니) |
'26년1학기 > 알고리즘' 카테고리의 다른 글
| 알고리즘) 26.3.16 (0) | 2026.03.16 |
|---|---|
| 알고리즘) 병합정렬 구현 (0) | 2026.03.15 |
| 알고리즘)26.3.11 (1) | 2026.03.11 |
| 알고리즘)26.3.9 (4) | 2026.03.09 |
| 알고리즘)복습할것 (0) | 2026.03.04 |