26년1학기/알고리즘

알고리즘)26.3.11

kimchangmin02 2026. 3. 11. 13:51

계수정렬에서 중간지점 c`갱신[ ]

시간복잡도에 대해서, 무슨 계산과정있엇는데

병합정렬, 성능 개선방법
(자료구조 pdf에는 배열 서로 바꾸는 거 있엇는데, 이 슬라이드에는 없는 이유가 뭐지)

제자리 정렬과 아닌것(정렬별 특징)

코드구현(병합, 기수)

System.arraycopy(src, 0, a, 0, N)작동방식

[강의 요약] 선형 정렬 알고리즘 및 병합 정렬

1. 선형 정렬 알고리즘 (Linear Sorting Algorithms) 개요

기존에 배웠던 삽입 정렬이나 선택 정렬은 데이터끼리 크기를 비교하는 '비교 기반 정렬'입니다. 반면, 선형 정렬은 키(Key)에 대한 추가적인 제약 조건을 활용하여 비교 없이 더 빠르게 정렬하는 방식입니다.

제약 조건 예시: 데이터가 특정 범위(예: 0~99) 내의 정수이거나, 자릿수가 고정된 숫자/문자열인 경우.

2. 계수 정렬 (Counting Sort)

데이터의 개수를 세어서 정렬하는 방식입니다.

(1) 작동 원리 (3단계)

카운트(Count): 전체 데이터를 한 번 읽으면서 각 숫자가 몇 번 나오는지 배열 C에 기록합니다. (마치 투표 집계와 같음)
누계(Accumulate): 배열 C를 누적합으로 변환합니다. 이는 특정 숫자 앞에 몇 개의 데이터가 와야 하는지(즉, 위치 정보)를 결정합니다.
배치(Distribute): 원래 배열 A를 뒤에서부터 앞으로 읽으며, 누적합 배열 C를 참조해 결과 배열 B에 데이터를 배치합니다.
- 중요: 뒤에서부터 읽는 이유는 동일한 값들의 원래 순서를 유지하기 위해서입니다 (안정 정렬, Stable Sort).

3. 버킷 정렬 (Bucket Sort)

데이터를 여러 개의 그룹(버킷)으로 나누어 정렬하는 방식입니다.

단계: 분할(데이터를 버킷에 배분) → 정렬(각 버킷 내부 정렬) → 수집(버킷들을 순서대로 합침)
특징: 버킷 수가 2개인 가장 대표적인 사례가 **퀵 정렬(Quick Sort)**입니다. (피벗을 기준으로 작은 그룹, 큰 그룹 분할)

4. 기수 정렬 (Radix Sort)

데이터의 **자릿수(Digit)**를 이용하여 정렬하는 방식입니다.

(1) 방식 구분

MSD (Most Significant Digit): 높은 자릿수부터 정렬. (예: 백의 자리 → 십의 자리 → 일의 자리)
- 직관적이지만, 그룹 내에서 또 정렬해야 하는 등 알고리즘이 복잡해질 수 있습니다.
LSD (Least Significant Digit): 낮은 자릿수부터 정렬. (예: 일의 자리 → 십의 자리 → 백의 자리)
- 하나의 안정 정렬(주로 계수 정렬) 알고리즘을 자릿수만큼 반복하면 됩니다. 구현이 더 단순하고 효율적일 수 있습니다.

(2) LSD 기수 정렬의 특징

안정성 필수: 하위 자릿수에서 정렬된 순서가 상위 자릿수 정렬 시에도 유지되어야 하므로 반드시 Stable Sort를 사용해야 합니다.
장점: 모든 데이터의 자릿수가 같을 때 매우 강력합니다. (예: 자동차 번호판, 카드 게임의 무늬와 숫자 등)
한계: 문자열의 길이가 제각각일 경우 적용하기 까다로울 수 있습니다.

5. 병합 정렬 (Merge Sort) - Top-down 방식

분할 정복(Divide and Conquer)의 대표적인 사례입니다.

(1) 작동 원리

분할(Divide): 배열을 반으로 나눕니다.
정복(Conquer): 나뉜 왼쪽과 오른쪽을 각각 재귀적으로 정렬합니다.
결합(Merge): 정렬된 두 부분을 하나로 합칩니다.

(2) 병합(Merge) 과정의 디테일

두 개의 정렬된 부분 배열에서 가장 작은 값들을 비교하여 더 작은 값을 임시 배열(aux)에 옮깁니다.
값이 같을 때는 왼쪽 배열의 값을 먼저 선택하여 **안정성(Stability)**을 유지합니다.

(3) 복잡도 및 특징

시간 복잡도: 항상 (최악의 경우에도 성능이 보장됨).
O(nlog⁡n)O(nlogn)
공간 복잡도: (병합을 위한 임시 배열이 필요함).
O(n)O(n)
특징: 자바(Java)의 객체 배열 정렬 등에서 실제로 널리 사용됩니다.

(4) 성능 개선 방법 (Java 등에서 사용되는 기법)

Cutoff: 데이터 개수가 작아지면(예: 7개 이하) 리커전을 멈추고 **삽입 정렬(Insertion Sort)**을 수행합니다. (작은 데이터에선 리커전 오버헤드보다 삽입 정렬이 빠름)
이미 정렬된 경우 체크: 왼쪽 마지막 원소가 오른쪽 첫 번째 원소보다 작거나 같으면 이미 정렬된 상태이므로 병합 과정을 생략합니다.
배열 복사 최소화: 매번 임시 배열로 복사하는 대신, 재귀 호출 시 배열의 역할을 교차(A→Aux, Aux→A)하여 복사 오버헤드를 줄입니다.

계수정렬

계수정렬 배열 여러개

배열 이름	역할	크기
A	정렬 전 데이터 (원본)	n(데이터 개수)
C	숫자가 몇 번 나오는지 세고, 어디에 넣을지 계산하는 표	k(숫자 범위)
B	정렬이 끝난 데이터가 담기는 통	n(데이터 개수)

인덱스=갯수-1(문제풀때)

1. 뒤에서부터 읽어야 하는 이유 (교수님 방식: 누적합 = 끝 위치)

교수님 강의 예시에서 누적합을 구하면 C[i]는 값 i가 들어갈 수 있는 가장 오른쪽(마지막) 인덱스를 알려줍니다.

예를 들어, 데이터에 0이 두 개(0번, 1번) 있다고 합시다. A = [0(첫째), 0(둘째)]
누적합 결과 C[0] = 2가 나왔다면, 이는 "0은 **2번째 칸(인덱스 1)**까지 들어갈 수 있다"는 뜻입니다.

이때 뒤에서부터 읽으면 (A의 마지막 0부터):

가장 뒤에 있던 0(둘째)를 먼저 만납니다.
C[0]을 보고 2번째 칸(인덱스 1)에 0(둘째)를 넣습니다.
C[0]을 1로 줄입니다.
그다음에 앞에 있던 0(첫째)를 만납니다.
줄어든 C[0]을 보고 1번째 칸(인덱스 0)에 0(첫째)를 넣습니다.

결과: [0(첫째), 0(둘째)] → 순서 유지 (Stable!)

반대로 앞에서부터 읽으면:

앞에 있던 0(첫째)를 먼저 만납니다.
C[0]이 2니까, 2번째 칸(인덱스 1)에 0(첫째)를 넣습니다.
그다음에 뒤에 있던 0(둘째)를 만나서 1번째 칸(인덱스 0)에 넣습니다.

결과: [0(둘째), 0(첫째)] → 순서가 뒤바뀜 (Unstable!)

2. "앞에서부터 읽을 수도 있지 않나요?" (학생의 생각)

네, 맞습니다! 질문하신 대로 인덱스 계산 방식만 살짝 바꾸면 앞에서부터 읽어도 Stable하게 만들 수 있습니다.

방법: C[i]가 '마지막 위치'가 아니라 **'시작 위치'**를 가리키게 만드는 것입니다.
가령 0이 인덱스 0부터 시작하고, 1은 0의 개수만큼 떨어진 인덱스부터 시작하게 표를 미리 한 칸씩 밀어서 작성한다면, 앞에서부터 읽으면서 첫 번째 0을 0번 칸에 넣고 인덱스를 하나씩 더해주는(++) 방식으로 구현할 수 있습니다.

1. 표를 만드는 사람 (C배열 계산)

우리는 그냥 숫자를 차례대로 더하는 게 제일 편합니다.

0이 3개, 1이 2개, 2가 4개 있다고 칩시다.
그냥 쭉 더하면: 3, 5(3+2), 9(5+4) ...
이 숫자가 의미하는 건? **"거기까지가 끝!"**이라는 팀의 뒷경계선입니다.
- 0번 팀은 3번 자리에서 끝!
- 1번 팀은 5번 자리에서 끝!
- 2번 팀은 9번 자리에서 끝!

수학적으로 이게 가장 깔끔한 이유:
그냥 다음 칸 = 현재 칸 + 이전 칸 이라는 단순한 규칙 하나로 표가 완성되기 때문입니다.

2. 시작 위치를 구하려면 표를 ‘공사’해야 해요

만약 시작 위치를 알고 싶다면, 표를 한 번 더 손봐야 합니다.

우리가 구한 표는 [3, 5, 9] (끝 위치)입니다.
시작 위치로 바꾸려면? [0, 3, 5] 로 바꿔야 하죠. (한 칸씩 옆으로 밀고 맨 앞은 0 채우기)
결과: 컴퓨터한테 **"표를 다 만든 다음에, 옆으로 한 칸씩 미는 작업을 또 해!"**라고 명령을 추가해야 합니다.

수학자들은 생각했습니다. "어차피 표에 ‘끝’ 위치가 적혀 있는데, 그냥 뒤에서부터 채우면 되는 거 아냐? 왜 굳이 표를 옆으로 밀고 난리를 쳐?"

//젤 마지막숫자가 99이면 k=99인건가 
//arr[99] != int[] arr= new int[99] //얘는 인덱스로치면 100까지있는거

1. "마지막 숫자가 99이면 K=99인가요?"

정답은 NO입니다. K는 100이어야 합니다.

계수 정렬에서 배열 C는 0부터 최댓값까지 모든 숫자의 개수를 셀 수 있어야 합니다.
만약 최댓값이 99라면, 우리는 C[0]부터 C[99]까지 칸이 필요합니다.
0부터 99까지 숫자는 총 몇 개인가요? 바로 100개입니다.
따라서 new int[K]를 할 때 K는 100이 되어야 C[99]라는 칸에 접근할 수 있습니다.
공식: 보통 로 설정합니다.
K=(최댓값+1)

2. "int[] arr = new int[99]는 인덱스 100까지 있는 건가요?"

0~98이니깐

아니요, 반대입니다! 인덱스는 98까지 있습니다.
자바에서 배열을 선언할 때 들어가는 숫자는 **'칸의 개수'**입니다.
(인덱스랑 갯수사이)

B[ --C[ A[i] ] ] = A[i]; 뜯어보기

이 한 줄에는 4단계의 작업이 숨어 있습니다. A[i]가 **'8'**이라고 가정하고 순서대로 따라가 보세요.

A[i] : "지금 줄 서 있는 애 누구야?" "8입니다."
C[ A[i] ] : "표(C) 가져와 봐. 숫자 8은 어디까지 앉을 수 있어?" 표에 **"8번 팀은 총 5명이야(5번 자리까지야)"**라고 적혀 있다고 칩시다.
--C[...] (핵심!) : 여기서 두 가지 일이 동시에 일어납니다.
- 인덱스 맞추기: 자바 배열은 0부터 시작하죠? 5명 중에 마지막 자리는 인덱스로 4번입니다. 그래서 5를 4로 깎습니다.
- 다음 사람 자리 예약: 이제 숫자 8 한 명을 앉혔으니, 다음에 또 8이 오면 걔는 3번 자리에 앉아야겠죠? 그래서 아예 표 값 자체를 5에서 4로 바꿔버리는 것입니다.
B[ 4 ] = 8 : 드디어 결정된 4번 자리에 숫자 8을 앉힙니다!

(전위 연산자 --)

자바에서 --가 변수 앞에 붙으면(--C[...]), **"값부터 깎고 나서, 그 깎인 값을 사용해라"**라는 뜻입니다.

C[ A[i] ]을
--c[4]

"한 번 깎는 행위"가 "나의 인덱스"를 결정함과 동시에 "다음 사람의 시작점"을 하나 뒤로 밀어주는 효과를 내는 것입니다.

C[8]에 들어있는 **값 5는 '개수

왜 두 번 깎을 필요가 없을까요?

학생분은 아마 이렇게 생각하셨을 거예요.

5에서 4로 깎아서 내 자리를 찾는다. (1번 깎음)
그리고 다음 사람을 위해 4에서 3으로 또 깎아둔다. (2번 깎음?)

하지만 이렇게 하면 안 되는 이유:
만약 첫 번째 사람이 3까지 깎아버리면, 두 번째 사람은 3에서 또 깎아서 2번 자리로 가버립니다. 그럼 3번 의자가 비어버리게 되죠!
진짜 원리:

**"내가 깎아서 만든 내 번호"**가 곧 **"다음 사람이 참고할 기준점"**이 되는 것입니다.

for (i = 0; i < N; i++)
    C[   A[i]   ]++; //c는 숫자 자체가 인덱스 //이미 여기서 각 숫자가 몇개인지 계산은 끝낸거고


for (i = 1; i < K; i++) //얘는 N이 아니라 K를 돌면서
    //1부터시작이네 i-1떄문에
    C[i] += C[i - 1];

// 3. 정렬된 배열을 생성
for (i = N - 1; i >= 0; i--)
    //뒤에서부터 오면서, 배열에 넣어주는건가
    B[  --C[  A[i]  ]   ] = A[i];

(경곗값)

버킷정렬

1. 일반적인 분할 정복 (예: 병합 정렬) = "무조건 반띵 청소"

방에 장난감이 100개 어질러져 있다고 해봅시다.

방법: 일단 장난감을 보지도 않고 왼쪽 50개, 오른쪽 50개로 반을 딱 나눕니다.
문제: 나누기는 쉬운데, 나중에 합칠 때가 문제예요. 왼쪽 장난감이랑 오른쪽 장난감을 하나하나 비교하면서 다시 순서를 맞춰야 하거든요. (합치는 과정이 힘듦)

2. 버킷 정렬 = "종류별 상자 청소"

똑같이 장난감이 100개 있습니다.

방법: 방 바닥에 **'인형 상자', '로봇 상자', '블록 상자'**를 미리 둡니다.
분할: 장난감을 집어 들면서 "어, 이건 로봇이네?" 하고 로봇 상자에 던져 넣습니다.
정복: 각 상자 안에 들어있는 장난감들끼리만 예쁘게 정렬합니다. (상자가 작으니 금방 하겠죠?)
합치기: 이제 고민할 필요가 없습니다. 인형 상자 → 로봇 상자 → 블록 상자 순서대로 바닥에 깔면 끝입니다! (합치는 과정이 매우 쉬움)

3. 왜 "분할 정복"이라고 딱 잘라 말하지 않을까?

우리가 교과서에서 배우는 **'분할 정복'**은 보통 **나누는 규칙이 일정(무조건 반으로!)**하고, 합칠 때 정성을 들여야 하는 것들을 말해요.
반면에 **'버킷 정렬'**은:

값의 범위를 보고 나눈다. (0~9는 1번 상자, 10~19는 2번 상자...)
나눌 때 이미 **순서(상자 번호)**가 정해져 있어서, 나중에 합칠 때 비교를 안 해도 된다.

그래서 "나눠서 해결한다"는 원리는 같지만, 컴퓨터 과학에서는 이를 **'분포 기반 정렬'**이라는 멋진 이름으로 따로 부르는 경우가 많습니다.

요약하자면!

분할 정복: "일단 반으로 쪼개고 나중에 고생해서 합치자!"
버킷 정렬: "처음부터 끼리끼리 나눠 담아서 나중에 합칠 고생을 없애자!"

(왜 merge는 아니라고 했더라)
"자료구조에서 배웠던 바텀업(Bottom-up) 머지는 버킷과 무관하다"고 하신 건 이런 뜻입니다.

바텀업 머지: 처음부터 1개씩, 2개씩, 4개씩 옆에 있는 애들끼리 그냥 묶어서 합칩니다. 여기엔 데이터를 특정 구간(버킷)으로 보낸다는 '분배'의 개념이 아예 없습니다.
탑다운 머지: 위에서 아래로 내려가며 쪼개긴 하지만, 역시 '값'을 보고 쪼개는 게 아니라 '중간 지점'을 보고 쪼개기 때문에 버킷 정렬과는 거리가 멉니다.

기수정렬

1. MSD (Most Significant Digit) 정렬

의미: **"가장 높은 자리(중요한 자리)"**부터 정렬하는 방식입니다.
카드 예시: 먼저 '무늬(스페이드, 다이아 등)' 별로 카드를 나눕니다.
1. 스페이드 묶음, 다이아 묶음, 하트 묶음, 클로버 묶음으로 4개의 버킷에 담습니다.
2. 그다음, 각 묶음 안에서 다시 '숫자' 순서대로 정렬합니다.
특징:
- 사람이 정렬할 때 쓰는 방식이라 매우 직관적입니다.
- 단점: 무늬별로 나눈 뒤에, **그 안에서 또 숫자로 정렬하는 별도의 과정(혹은 재귀 호출)**이 필요합니다. 그래서 교수님이 "알고리즘이 두 개(나누는 거 하나, 안에서 정렬하는 거 하나) 필요해서 조금 복잡할 수 있다"고 하신 것입니다.

2. LSD (Least Significant Digit) 정렬

의미: **"가장 낮은 자리"**부터 정렬하는 방식입니다.
카드 예시: 무늬는 신경 쓰지 말고, 일단 '숫자(A, 2, 3... K)' 순서대로 먼저 정렬합니다.
1. 숫자별로 정렬한 카드들을 다 합칩니다.
2. 그 상태 그대로, 이번에는 '무늬' 순서대로 다시 정렬합니다.
특징:
- 장점: 똑같은 정렬 알고리즘(예: 계수 정렬)을 자릿수만 바꿔서 반복하면 끝납니다. "나누고 합치고, 나누고 합치고"만 반복하면 정렬이 턱! 완료됩니다. 그래서 구현이 훨씬 심플합니다.
- 핵심 조건: 반드시 **안정 정렬(Stable Sort)**을 써야 합니다. 그래야 낮은 자리에서 정렬해둔 순서가 높은 자리를 정렬할 때 뒤섞이지 않기 때문입니다.

3. 왜 LSD를 더 많이 쓰나요? (교수님 강조 포인트)

교수님은 LSD 방식을 더 추천하셨는데, 그 이유는 다음과 같습니다.

알고리즘의 단순함: MSD는 그룹을 나눈 뒤 그 안에서 또 정렬을 관리해야 하지만, LSD는 그냥 전체 데이터를 대상으로 자릿수만 옮겨가며 정렬하면 됩니다. (알고리즘 하나만 있으면 됨!)
효율성: 자릿수가 고정되어 있다면(예: 3자리 정수), 그냥 3번만 돌리면 정렬이 끝납니다.

1. MSD(높은 자리 먼저)의 문제점: "바구니가 계속 늘어난다"

예를 들어 19, 12, 21 세 숫자가 있다고 합시다.

십의 자리(높은 자리)로 먼저 정렬:
- [12, 19] 묶음이 앞에 오고, [21] 묶음이 뒤에 옵니다.
여기서 주의! 이제 전체를 한꺼번에 섞어서 일의 자리로 정렬하면 안 됩니다.
- 그냥 섞어서 일의 자리로 정렬해버리면 일의 자리가 1인 21이 맨 앞으로 튀어나오겠죠? (19, 12보다 21이 작다고 착각함)
해결책: 그래서 MSD는 [12, 19]라는 바구니 안에서만 따로 정렬을 또 해야 합니다. 바구니가 많아질수록 관리하기가 아주 복잡해지죠.

2. LSD(낮은 자리 먼저)의 마법: "나중에 하는 놈이 주인공이다"

LSD는 반대로 **"힘이 약한 놈(일의 자리)"**부터 정렬하고, **"가장 힘이 센 놈(백의 자리)"**을 마지막에 정렬합니다.
동일하게 19, 12, 21로 해볼까요? (반드시 안정 정렬을 써야 합니다!)

일의 자리(낮은 자리)로 정렬:
- 일의 자리가 1인 21이 맨 앞, 2인 12가 중간, 9인 19가 맨 뒤로 갑니다.
- 결과: 21, 12, 19 (아직은 엉망이죠?)
십의 자리(높은 자리)로 정렬 (주인공 등판!):
- 십의 자리가 1인 애들(12, 19)을 앞으로 보내고, 2인 애(21)를 뒤로 보냅니다.
- 여기서 마법! 12와 19 중에 누가 더 앞에 올까요? 아까 1단계에서 12가 19보다 앞에 있었죠? 안정 정렬은 그 순서를 지켜주기 때문에 12, 19 순서가 유지됩니다.
- 결과: 12, 19, 21 (정렬 완료!)

가정 조건: "키가 이렇게 개의 요소들로 되어 있다. 즉 자릿수가 d자리라는 걸 딱 우리가 가정한다면 써먹을 수 있는 알고리즘이에요." (녹취록에는 '비(d)계'라고 적혀 있습니다.)
dd
기수의 정의: "그 기수라는 게 그 자릿수라는 겁니다. 그 자릿수가 고정이 될 때 써먹을 수 있는 알고리즘이 기수 정렬이다."
구체적 예시: "이름이 세 자리 문자다(d=3)", "자동차 번호판(자리수가 고정됨)" 등.

2. 왜 자릿수가 고정되어야 할까? (교수님의 설명)

특히 LSD(낮은 자리부터 정렬) 방식을 쓸 때 자릿수가 다르면 문제가 생깁니다.

문자열의 문제: "문자열에 대해서는 모든 문자열의 길이가 똑같을 때만 LSD를 쓸 수 있고, 길이가 다르면 (LSD 정렬 시) 여기 0이 있다고 생각할 수 있는 건가요? 아니잖아..."
비교의 기준: 예를 들어 '9'와 '19'가 있을 때, 숫자는 '09'라고 생각해서 비교할 수 있지만 문자열은 그렇게 앞자리를 채우는 것이 정렬 기준과 맞지 않을 수 있기 때문입니다.
결론: 그래서 교수님은 "문자열 길이가 다르면 앞부분부터 비교하는 MSD 방식을 써야 할지도 모른다"고 덧붙이셨습니다.

숫자 체계의 '기초가 되는 수'
기수(基數)**라고 쓰는데, 쉽게 말하면 **"몇 진법을 쓰느냐

**기수 정렬(Radix Sort)**을 설명하며 **계수 정렬(Counting Sort)**이나 버킷(바구니) 개념이 등장하는 이유는, 기수 정렬이 각 자릿수별로 데이터를 나누어 정렬할 때 내부적으로 '계수 정렬'이나 '버킷'의 원리를 그대로 가져다 쓰기 때문입니다.

1. 기수 정렬은 '자릿수만큼 반복하는' 계수 정렬입니다.

기수 정렬은 한 번에 전체 숫자를 비교하는 것이 아니라, 1의 자리, 10의 자리, 100의 자리 순으로 나누어 정렬합니다. 이때 **각 자릿수(0~9)를 정렬하는 가장 효율적인 방법이 바로 '계수 정렬'**입니다.

예를 들어 1의 자릿수를 정렬할 때, 0인 숫자들은 0번 바구니(계수)에, 1인 숫자는 1번 바구니에 담는 식입니다.
본문에서도 "이 스테이블 소팅을 우리가 쓸 수 있는 게 앞에서 봤던 조금 전에 봤던 카운팅 소트(계수 정렬)를 쓰면..."이라고 언급하며 두 알고리즘을 연결하고 있습니다.

2. '안정성(Stable)'이 필수이기 때문입니다.

기수 정렬(LSD 방식)이 성공하려면 낮은 자릿수에서 정렬된 순서가 높은 자릿수를 정렬할 때도 유지되어야 합니다(Stable 정렬).

계수 정렬은 대표적인 **안정 정렬(Stable Sort)**입니다.
교수님이 설명하신 "원래 데이터의 값이 같을 때는 그 순서를 유지하자. 이게 스테이블한 속성이다"라는 부분은, 기수 정렬의 내부 로직으로 계수 정렬을 써야만 하는 결정적인 이유를 설명한 것입니다.

(Radix, 기수)의 의미

은 **"한 자릿수가 가질 수 있는 값의 가짓수"**를 의미합니다. 즉, **'바구니(버킷)를 몇 개 준비해야 하는가'**를 결정하는 숫자입니다.

10진수 정렬을 할 때: 한 자릿수는 0~9까지 총 10개의 숫자를 가질 수 있죠? 그래서 ****이 됩니다. (코드의 new int[10] 부분)

m: 배열 안에서 가장 큰 숫자. (가장 큰 숫자가 몇 자리인지 알아야 몇 번 반복할지 정할 수 있어요. 900이면 100의 자리까지 3번 해야 하니까요.)
exp: 자릿수를 나타냅니다. (1부터 시작. 1 -> 10 -> 100 순서로 10씩 곱해집니다.)
B: 임시 보관함. 자릿수별로 줄을 세운 결과를 잠시 담아두는 새 배열입니다.
C: 0부터 9까지의 숫자가 각각 몇 개인지 세는 카운터 (버킷) 배열입니다.

"높은 자리부터 정렬해놓고, 나중에 낮은 자리로 다시 전체를 정렬하면 기껏 해놓은 게 다 망가지지 않나?"
질문자님께서 "이동하는 범위가 있는 건가?" 라고 추측하신 부분이 정확히 정답입니다!

1. 왜 문자열 "9"와 "19"를 정렬할 때 LSD는 망할까?

먼저 숫자와 문자열(사전순) 의 정렬 방식 차이를 알아야 합니다

LSD가 문자열에서 망하는 이유:
LSD는 태생적으로 "맨 뒷글자(오른쪽 끝)" 부터 비교를 시작합니다.
그런데 문자열은 길이가 들쭉날쭉하죠. "19"의 뒷글자는 '9'이고, "9"의 뒷글자는 '9'입니다. 문자열은 왼쪽(앞글자)이 중요한데, LSD는 무조건 오른쪽 끝부터 맞추려고 하니까 사전순 정렬의 기준(왼쪽부터 비교) 자체가 완전히 박살 나버리는 것입니다.
강의록에서 교수님이 "문자 같으면 9를 하고 앞에 0이 있으니까 이게 안 된다고요" 라고 하신 게 바로 이 뜻입니다. 문자열은 앞에 0을 붙여서 자릿수를 맞추면 안 되고, 왼쪽부터 차례대로 봐야 하기 때문입니다.

2. MSD는 어떻게 이 문제를 해결할까? (질문자님의 천재적인 의문!)

질문자님 말씀대로, MSD(가장 높은 자리부터 정렬)를 썼을 때, 첫 글자로 정렬해놓고
두 번째 글자로 "전체를 다시" 정렬해 버리면 앞선 정렬이 다 망가집니다.
그래서 MSD는 LSD처럼 "전체를 다시" 돌리지 않습니다.
질문자님이 예상하신 대로 "이동하는 범위(그룹, 버킷)"를 쪼개서 가둬버립니다.

💡 MSD의 마법: "버킷(바구니) 쪼개기"

문자열 "19", "123", "9" 를 사전순(MSD)으로 정렬해 보겠습니다.
[1단계] 첫 번째 글자(가장 높은 자리) 기준으로 분류합니다.

'1' 바구니 : "19", "123"
'9' 바구니 : "9"

[2단계] 여기가 핵심입니다! 바구니를 '벗어나지 않고' 그 안에서만 다음 자리를 정렬합니다.

이제 전체를 섞는 게 아닙니다. '1' 바구니 안에서만 두 번째 글자를 봅니다.
'1' 바구니 안의 "19"와 "123"의 두 번째 글자 비교: '9' vs '2'
'2'가 더 작으니까 '1' 바구니 안의 순서가 ["123", "19"] 로 정렬됩니다.
'9' 바구니는 혼자니까 정렬 끝!

1단계: 가장 큰 숫자 찾기codeJava

int i, m = A[0], exp = 1, n = A.length;
int[] B = new int[n]; 

for (i = 1; i < n; i++)
    if (A[i] > m) m = A[i];

해설: A 배열에서 제일 큰 숫자를 찾아서 m에 저장합니다. 만약 제일 큰 숫자가 345라면 세 자릿수니까, 1의 자리, 10의 자리, 100의 자리까지 총 3번 돌려야 한다는 걸 알 수 있습니다.

2단계: 자릿수별로 정렬 시작 (while 루프)codeJava

while (m / exp > 0) {

해설: m(가장 큰 수)을 exp(현재 자릿수)로 나누었을 때 0보다 클 때만 반복합니다.
- 예: 제일 큰 수가 345일 때
- exp = 1일 때: 345 / 1 = 345 (진행 O) -> 1의 자리 정렬
- exp = 10일 때: 345 / 10 = 34 (진행 O) -> 10의 자리 정렬
- exp = 100일 때: 345 / 100 = 3 (진행 O) -> 100의 자리 정렬
- exp = 1000일 때: 345 / 1000 = 0 (종료 X) -> 끝!

3단계: 현재 자릿수의 숫자 개수 세기 (발정(正)자 쓰기)codeJava

int[] C = new int[10]; // 0~9를 담을 바구니 10개 준비

for (i = 0; i < n; i++)
    C[(A[i] / exp) % 10]++;

해설: 현재 보고 있는 자릿수의 숫자가 0~9 중 무엇인지 빼내서, 그 개수를 셉니다.
핵심 꿀팁 (A[i] / exp) % 10 란? 자릿수 숫자만 쏙 빼내는 마법의 공식입니다.
- 숫자가 345고, exp가 10(10의 자리)라면? -> (345 / 10) % 10 -> 34 % 10 -> 4 (10의 자리인 4만 쏙 빠져나옵니다!)
- 즉, "너 10의 자리가 4네? 그럼 C[4] 바구니에 1개 추가!"라는 뜻입니다.

(3,4단계에 있는건 계수정렬할떄랑 똑같네)

🎟️ 4단계: 영화관 지정석 할당하기 (누적합)codeJava

for (i = 1; i < 10; i++)
    C[i] += C[i - 1];

앞선 3단계에서 우리는 0번 팀(끝이 0)이 2명, 2번 팀(끝이 2)이 2명이라는 걸 셌습니다.
이제 이 팀들에게 1번부터 4번까지 있는 영화관 좌석을 배정해 줄 겁니다.

0번 팀 (2명): 제일 먼저 쭈욱 앉으세요. 1번, 2번 좌석을 쓰면 됩니다. -> (0번 팀의 마지막 좌석은 2번)
1번 팀 (0명): 사람이 없네요. 패스.
2번 팀 (2명): 0번 팀 다음부터 앉으세요. 3번, 4번 좌석을 쓰면 됩니다. -> (2번 팀의 마지막 좌석은 4번)

4단계 코드는 바로 이 **"각 팀이 쓸 수 있는 가장 마지막 좌석 번호"**를 기록해 두는 과정입니다.

C[0] = 2 (0번 팀은 2번 좌석까지 앉아라)
C[2] = 4 (2번 팀은 4번 좌석까지 앉아라)

🚶‍♂️ 5단계: 표 받고 자리에 앉히기 (B 배열에 넣기) ★제일 헷갈리는 곳codeJava

for (i = n - 1; i >= 0; i--)
    B[--C[(A[i] / exp) % 10]] = A[i];

이제 사람들을 줄 세워 빈 방(B 배열)에 앉힙니다.
왜 원본 배열(A)의 맨 뒤에서부터(i = n - 1) 부를까요?
원래 줄 서 있던 순서를 지켜주기 위해서입니다. (먼저 온 10이 뒤에 온 20보다 앞에 있어야 함)
자, 맨 뒤에서부터 사람을 불러서 앉혀봅시다. 원본 A는 [42, 10, 32, 20] 입니다.

맨 뒤에 있는 20 부름:
- "너 끝자리가 0이니까 0번 팀이네?"
- "아까 적어둔 표(C)를 보자. 0번 팀의 마지막 빈자리는 2번 좌석이네."
- "좋아, 20은 2번 좌석에 앉아!" (B의 2번째 칸에 20 저장)
- "이제 0번 팀 자리는 하나 줄었으니까, 다음 0번 팀이 오면 1번 좌석에 앉혀야지." (--C 로 좌석표 업데이트)
그다음 뒤에 있는 32 부름:
- "너 끝자리가 2니까 2번 팀이네?"
- "표(C)를 보자. 2번 팀 마지막 빈자리는 4번 좌석이네."
- "32는 4번 좌석에 앉아!" (B의 4번째 칸에 32 저장)
- "다음 2번 팀이 오면 3번 좌석에 앉혀야지." (--C 업데이트)
그다음 10 부름:
- "너 0번 팀이네? 아까 0번 팀 다음 자리는 1번 좌석이라고 업데이트 해놨지."
- "10은 1번 좌석에 앉아!"
맨 앞의 42 부름:
- "너 2번 팀이네? 2번 팀 다음 자리는 3번 좌석이지."
- "42는 3번 좌석에 앉아!"

결과 확인:
임시 방 B의 좌석 1, 2, 3, 4번에 순서대로 [10, 20, 42, 32] 가 앉게 되었습니다.
끝자리가 같은 애들끼리 예쁘게 뭉쳤고, 원래 순서도 안 망가졌죠? 성공입니다!

🧹 6단계: 원본으로 옮기고 다음 자릿수 준비codeJava

for (i = 0; i < n; i++)
    A[i] = B[i]; 

exp *= 10;

이제 임시 방(B)에서 예쁘게 정렬된 [10, 20, 42, 32] 를 그대로 원래 있던 방(A)으로 복사해 옵니다.
(이제 A 방은 1의 자리를 기준으로 깔끔하게 정렬된 상태입니다.)
exp *= 10; : "자, 1의 자리 검사는 끝났다! 이제 곱하기 10 해서 10의 자리 숫자들 가지고 방금 한 거 똑같이 다시 하자!" 하고 다음 루프로 넘어갑니다.

1. 6단계: 왜 굳이 정렬된 B를 다시 A로 복사해 오나요? (A = B)

결론부터 말하면: "다음 자릿수(10의 자리, 100의 자리) 정렬을 할 때, 방금 정렬해 둔 결과를 '이어서' 써야 하기 때문" 입니다.
기수 정렬은 while문을 돌면서 1의 자리 -> 10의 자리 -> 100의 자리 순서로 계속 반복 작업을 합니다.
그런데 코드 안쪽을 자세히 보시면, 숫자를 읽어올 때는 항상 A[i] 에서 읽어옵니다.
만약 B에 예쁘게 정렬해 놓고 원본 A에 덮어쓰지 않은 채로 다음 10의 자리 정렬로 넘어가면 어떻게 될까요?
컴퓨터는 다시 "아무렇게나 섞여 있던 맨 처음 상태의 A" 를 보고 10의 자리를 정렬하게 됩니다.
즉, 1의 자리에서 힘들게 줄 세워 놓은 노력이 다 날아가 버리는 겁니다.
그래서 "1의 자리 정렬 끝! 자, 이 결과(B)를 메인 무대(A)로 다시 올려놔! 이제 이 예뻐진 상태(A)에서 10의 자리를 보자!" 하고 업데이트해 주는 과정이 반드시 필요한 것입니다.

2. 1단계 코드, 이게 뭔가요?codeJava

for (i = 1; i < n; i++) {
    if (A[i] > m) m = A[i];
}

이 코드는 프로그래밍에서 아주아주 유명하고 기초적인 "배열에서 1등(가장 큰 숫자) 찾기" 공식입니다.

m = A[0] : 일단 맨 앞에 있는 사람(A[0])을 "임시 1등(m)" 자리에 앉힙니다.
for (i = 1; ...) : 두 번째 사람(A[1])부터 끝까지 한 명씩 불러냅니다.
if (A[i] > m) : 방금 부른 사람(A[i])의 키가, 현재 임시 1등(m)보다 큰가요?
m = A[i] : 만약 더 크다면, 임시 1등 자리를 그 사람에게 넘겨줍니다!

이 과정을 끝까지 반복하면, 결국 m에는 이 그룹에서 진짜로 제일 큰 숫자가 남게 됩니다.
(기수 정렬에서는 가장 큰 숫자가 몇 자리인지(예: 999면 3자리) 알아야 while문을 3번 돌릴지, 4번 돌릴지 정할 수 있어서 이 작업이 처음에 꼭 필요합니다.)

3. 마의 5단계 코드 해부하기 (개념은 아는데 코드가 왜 저래?)codeJava

B[--C[(A[i] / exp) % 10]] = A[i];

이 한 줄이 미치도록 안 읽히는 이유는, 개발자가 4줄짜리 코드를 억지로 1줄로 압축해 놨기 때문입니다. (개발자들의 나쁜 습관 중 하나죠 😂)
이 암호문을 사람이 읽기 편하게 4단계로 쭉 풀어헤쳐 보겠습니다. 똑같이 작동하는 코드입니다.codeJava

// 맨 뒤(n-1)부터 시작해서 한 명씩 부릅니다.
for (i = n - 1; i >= 0; i--) {
    
    // 1번 행동: 지금 부른 사람의 원래 숫자
    int 현재_숫자 = A[i];  // 예: 32
    
    // 2번 행동: 이 사람의 '팀 번호 (현재 자릿수)' 구하기
    int 팀_번호 = (현재_숫자 / exp) % 10;  // 예: 32의 1의 자리는 2 (2번 팀)
    
    // 3번 행동: 내 팀의 '빈 좌석 번호' 뽑기 (그리고 좌석 하나 줄이기)
    // C[2]에 4가 적혀있다면 4번째 자리라는 뜻인데, 
    // 배열은 0부터 시작하니까 실제 인덱스는 3입니다. 
    // 그래서 --를 먼저 써서 4를 3으로 깎은 뒤에 좌석표로 씁니다!
    C[팀_번호] = C[팀_번호] - 1;       // 2번 팀 좌석표를 4에서 3으로 하나 줄임
    int 내_좌석표 = C[팀_번호];        // 내 자리는 인덱스 3번 자리!
    
    // 4번 행동: 임시 방(B)의 내 자리에 들어가서 앉기
    B[내_좌석표] = 현재_숫자;        // B[3] 자리에 32가 쏙 들어감
}

이걸 거꾸로 다시 합쳐볼까요?

A[i] (현재 숫자)
(A[i] / exp) % 10 (팀 번호 구하기)
C[팀 번호] (그 팀의 좌석 번호표 보기)
--C[...] (좌석 번호 1 빼기. 빼기를 먼저 해야 배열 인덱스가 맞음)
B[ --C[...] ] = A[i] (최종: B의 해당 인덱스에 현재 숫자를 넣기)

이렇게 한 줄에 우겨 넣은 코드입니다. 코드가 너무 복잡해 보일 때는 이렇게 의미 단위로 잘라내서 변수로 선언해 보면 마법처럼 이해가 됩니다!

❌ 1. % 10을 안 했을 때 (대참사 발생)

식: 345 / 10
결과: 34 (자바에서 정수 나눗셈은 소수점을 버리니까요)
문제점: 우리는 10의 자리 숫자인 **4**번 팀을 찾고 싶었는데, 결과가 **34**번 팀이 되어버렸습니다!

/ exp의 역할: 내가 원하는 자릿수의 숫자를 맨 끝(1의 자리)으로 밀어내는 역할. (345 -> 34)
% 10의 역할: 맨 끝으로 밀려난 숫자 딱 1개만 남기고, 앞에 있는 불필요한 숫자들을 싹둑 잘라내는(가위) 역할. (34 -> 4)

수 / exp 의 수학적 역할 (Shift 연산):
내가 원하는 타겟 숫자를 1의 자리()로 끌어내리는 역할을 합니다. (하위 자릿수 소거)

% 10 의 수학적 역할 (Masking 연산):
1의 자리로 끌어내려진 타겟 숫자 위에 붙어있는 10의 배수들(상위 자릿수들)을 수학적으로 모조리 0으로 소거하여, 순수하게 1의 자리 숫자 딱 1개만 남기는 역할을 합니다.

(%10하면 일의 자리(내가 진짜 원하는 자리의 수만 남으니깐)

병합정렬

(top-down)

1. 🤝 병합 정렬의 기초: '병합(Merge)'이란 무엇인가?

병합 정렬의 가장 핵심은 **"이미 정렬된 두 개의 덩어리를 하나로 합치는 것"**입니다.

상황: 배열이 반으로 나뉘어 있고, 왼쪽 반(low ~ mid)도 정렬되어 있고, 오른쪽 반(mid+1 ~ high)도 정렬되어 있습니다.
합치는 방법:
1. 왼쪽 덩어리의 제일 작은 값과 오른쪽 덩어리의 제일 작은 값을 비교합니다.
2. 둘 중 더 작은 값을 임시 배열(aux)에 먼저 내려놓습니다.
3. 한쪽 덩어리가 바닥날 때까지 이 비교를 계속합니다.
4. 한쪽이 먼저 바닥나면, 남은 덩어리의 숫자들은 그냥 뒤에 쭉 이어 붙이면 됩니다.
🌟 핵심 특징 (안정 정렬, Stable): 만약 왼쪽 값과 오른쪽 값이 같다면? 무조건 왼쪽(앞에 있던) 값을 먼저 내려놓습니다. 그래야 원래 데이터의 순서가 뒤죽박죽되지 않고 유지됩니다.

2. 🪓 전체 정렬 과정: 탑다운(Top-down) 분할 정복

전체 배열을 어떻게 정렬할까요? 아주 단순하고 무식(?)한 재귀(Recursion) 방식을 씁니다.

마법의 주문 (재귀 호출):
1. 왼쪽 반틈을 정렬해! (재귀)
2. 오른쪽 반틈을 정렬해! (재귀)
3. 두 개를 병합해!
진행 순서: 처음에는 반으로 쪼개고, 또 쪼개고, 또 쪼개서 데이터가 1개가 될 때까지 계속 쪼갭니다. (데이터가 1개면 이미 정렬된 상태니까요).
그다음부터 가장 작은 조각들(1개짜리들)을 2개로 병합하고, 4개로 병합하고, 8개로 병합하면서 점점 위로 올라와 결국 전체가 정렬됩니다. (교수님이 포스트 오더(Post-order) 형태라고 비유하신 이유입니다.)

3. ⏱️ 복잡도 (성능 평가)

4. 🚀 실전 응용: 자바(Java)는 어떻게 성능을 개선했을까?

녹취록의 백미입니다. 이론적인 병합 정렬을 실제 자바 라이브러리에서는 3가지 꼼수(최적화)를 써서 훨씬 빠르게 만들었습니다.

Cutoff (작은 배열은 재귀 금지):
데이터가 1억 개면 반씩 쪼개는 게 효율적이지만, 쪼개다 보니 데이터가 7개 이하로 작아졌다면? 10개짜리를 정렬하려고 재귀 함수를 부르는 게 오히려 컴퓨터한테는 더 무겁습니다.
해결책: 쪼개진 덩어리가 특정 개수(예: 7개) 미만이면, 복잡한 병합 정렬을 멈추고 단순한 **삽입 정렬(Insertion Sort)**로 정렬해 버립니다. (삽입 정렬도 '안정 정렬'이라 속성이 유지됩니다.)
병합 생략 (이미 정렬된 경우):
왼쪽 반틈을 정렬하고 오른쪽 반틈을 정렬했습니다. 그런데 우연히 [왼쪽 덩어리의 가장 큰 값 오른쪽 덩어리의 가장 작은 값] 이라면?
해결책: 이미 전체가 완벽하게 정렬된 상태입니다! 굳이 하나씩 비교하며 병합할 필요 없이 병합 과정을 아예 건너뜁니다(Skip).
보조 배열 복사 줄이기:
병합할 때마다 임시 배열(aux)에 복사했다가 다시 원본 배열(A)로 옮기는 작업은 시간이 오래 걸립니다.
해결책: 처음부터 A와 aux를 복사해 두고, 한 번은 A에서 aux로 병합하고, 다음 단계에선 aux에서 A로 병합하도록 **역할을 교대(Toggle)**시킵니다. 그러면 쓸데없이 배열을 통째로 다시 복사하는 시간을 아낄 수 있습니다.

merge함수는 똑같고
sort함수만 다른가
top,down이

merge 함수는 똑같고, sort 함수가 전체 과정을 어떻게 운영하느냐(전략)만 다릅니다.

점화식

1. Top-Down 방식의 복사 (이미지 2번 참고)

Top-Down 방식에서 사용하는 merge 함수 본문을 다시 보시면, 가장 윗부분에 이런 코드가 있습니다.codeJava

// merge 함수 내부
for (int k = lo; k <= hi; k++)
    aux[k] = a[k];  // <--- 바로 이 부분!

어떻게 처리하나: merge가 불릴 때마다 일단 현재 정렬할 구간(lo~hi)을 aux 배열에 미리 다 복사해 놓습니다.
왜 이렇게 하나: 원본 배열 a에 바로 결과를 적으면, 아직 비교도 안 한 데이터가 덮어씌워져서 사라질 수 있기 때문입니다. 그래서 aux에 복사본을 만들어놓고 거기서 값을 읽어와서 a에 채워넣는 식입니다.
단점: merge가 수없이 많이 호출되는데, 그때마다 for문을 돌며 복사를 하니 조금 비효율적입니다.

2. Bottom-Up 방식의 복사 (이미지 4번 참고)

두 번째 이미지의 Bottom-Up 코드는 훨씬 영리한 "핑퐁(Ping-Pong)" 기법을 쓰고 있습니다codeJava

// sort 함수 내부의 핵심 로직
merge(src, dst, ...); // src에서 읽어서 dst로 합치기
tmp = src; src = dst; dst = tmp; // <--- 두 배열의 역할을 통째로 바꿈!

어떻게 처리하나:
1. 처음에는 src에서 데이터를 읽어 정렬한 뒤 dst에 저장합니다.
2. 그다음 단계(예: 2개씩 합치기 → 4개씩 합치기)로 갈 때는, 방금 저장한 dst를 src로 쓰고, 원래 src였던 곳을 dst로 써서 다시 저장합니다.
3. 즉, 내용물을 일일이 복사하는 게 아니라, "내가 이번에 읽을 곳"과 "쓸 곳"의 이름표만 바꿔치기 하는 것입니다.
마지막 처리:이리저리 이름표를 바꾸며 정렬하다 보니, 최종 결과가 원본 배열 a가 아닌 임시 배열에 들어있을 수도 있습니다. 그래서 마지막에 딱 한 번만 배열 전체를 원본 a로 복사해서 마무리하는 것입니다.Java
```
if (src != a) System.arraycopy(src, 0, a, 0, N);
```

요약하자면

Top-Down: merge 함수가 실행될 때마다 부분적으로 계속 복사가 일어납니다. (코드 안의 aux[k] = a[k])
Bottom-Up (제시된 코드): 단계마다 배열 전체의 참조(이름표)만 바꿈으로써 복사 횟수를 획기적으로 줄였습니다. 마지막에 결과가 엉뚱한 배열에 있으면 그때 한 번만 System.arraycopy를 해줍니다.

메모리에 100번지와 200번지라는 두 공간이 있다고 가정해 봅시다.

[초기 상태]

원본 상자(100번지): [3, 1, 4, 2] (뒤섞인 데이터)
빈 상자(200번지): [ , , , ] (비어있음)
src 리모컨: "나는 100번지를 조종할래!"
dst 리모컨: "나는 200번지를 조종할래!"

[작업 수행: merge(src, dst)]

src(100번지)에서 데이터를 읽어 정렬해서 dst(200번지)에 씁니다.
이제 200번지에 정렬된 데이터 [1, 2, 3, 4]가 들어갔습니다.

[핑퐁 단계: 이름표 바꾸기]

이제 다음 정렬을 하려면 200번지에 있는 걸 읽어와야 합니다. 보통은 200번지 내용을 다시 100번지로 복사하지만, 이 코드는 리모컨 주소만 바꿉니다.

temp는 주소 서로 바꾸기 위한거고

src (Source, 소스): "데이터를 가져올 곳" (원래 재료)
dst (Destination, 데스티네이션): "데이터를 저장할 곳" (합친 결과)

[2단계: 이름표 바꾸기 (Swap)]
이제 다음 단계 정렬을 하려면, 아까 만든 요리(dst)가 다시 재료가 되어야 합니다.
그래서 손에 든 리모컨 이름표를 바꿉니다.

src 리모컨: 이제 요리가 들어있는 그릇을 가리킴. (재료가 됨)
dst 리모컨: 이제 비어있는 그릇을 가리킴. (새 결과를 담을 곳이 됨)

merge를 할 때는 dst가 정렬을 완료하는 곳이 맞지만, 그 직후에 이름표를 바꿔버려서 결국 최신 데이터는 항상 src가 들고 있게 됩니다.

merge(src, dst) 할 때: 맞습니다! 이때는 dst 상자에 정렬된 새 데이터가 담깁니다. (dst가 주인공)
tmp = src; src = dst; dst = tmp; 할 때: 하지만 바로 다음 줄에서 이름표를 바꿔버립니다. 방금 요리가 끝난 상자(dst)에 src라는 이름표를 새로 붙여주는 거예요.

(또 병합해야하니깐, 근데 재료가 src니깐)

1. 진짜 상자는 2개입니다

상자 1 (원본): 주인님이 처음 준 상자 (이름표 a)
상자 2 (임시): 우리가 새로 만든 빈 상자 (코드에서 new Comparable[a.length])

2. 리모컨의 처음 상태

처음에 코드를 보면 리모컨을 이렇게 설정하죠?

a 리모컨: 상자 1을 가리킴 (주인님용, 절대 안 바뀜)
src 리모컨: 상자 1을 가리킴 (src = a 라고 했으니까요!)
dst 리모컨: 상자 2를 가리킴 (새로 만든 상자)

2. 초기 세팅 (코드: src = a;)

처음엔 이렇게 시작합니다.

리모컨 a → 상자 1을 가리킴.
리모컨 src → 상자 1을 가리킴. (방금 src = a라고 했으니까요!)
리모컨 dst → 상자 2를 가리킴.

3. 왜 a는 무조건 상자 1만 가리킨다고 했나요?

교수님 코드를 아무리 눈 씻고 찾아봐도 a = ... 라고 해서 a 리모컨의 방향을 바꾸는 코드는 없기 때문입니다.

src와 dst는 tmp를 써서 src = dst; dst = tmp; 하면서 계속 방향을 바꾸죠? (핑퐁)
하지만 a 리모컨은 한 번도 안 건드려요. 처음 줬던 그 상태 그대로 상자 1만 쳐다보고 있습니다.

그럼 a랑 src랑 똑같은 거 아니야?"라고 생각하실 수 있는데, 처음에만 똑같고 나중엔 달라집니다.

처음: a와 src가 둘 다 상자 1을 가리킴.
1라운드 후: a는 상자 1을 가리키는데, src는 상자 2를 가리킴. (둘이 찢어짐!)
2라운드 후: a는 상자 1을 가리키는데, src가 다시 상자 1로 돌아옴. (다시 만남!)

'26년1학기 > 알고리즘' 카테고리의 다른 글

알고리즘) 26.3.16 (0)	2026.03.16
알고리즘) 병합정렬 구현 (0)	2026.03.15
알고리즘) 계수,기수 정렬 구현/복잡한 증감연산자 (0)	2026.03.14
알고리즘)26.3.9 (4)	2026.03.09
알고리즘)복습할것 (0)	2026.03.04

현재글알고리즘)26.3.11

kimchangmin02 님의 블로그

kimchangmin02 님의 블로그 입니다.

자바, 마인크래프트 모딩, 몹 ai, 모드 개발, 모딩 강좌, 포지, Forge, 커스텀 몹, 1.18.2, 몹 만들기, 포지 모딩, 게임개발, 주민 ai, 개발일지, 마인크래프트 모드, Ai, 마인크래프트모딩, 게임 개발, Java, 마인크래프트,

Today :
Yesterday :

« 2026/06 »
일	월	화	수	목	금	토
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30