알고리즘) 중간고사_대비_1장

 

 

 

a[j]=a[j-1] vs a[j-1]=a[j] 중 무엇인가?"

• a[j] = a[j-1]이 맞습니다. 왼쪽(j-1)에 있는 큰 값을 오른쪽(j) 빈칸으로 밀어내어, 작은 값이 들어갈 자리를 만드는 과정입니다.

(일단 exch방법 사용

 

 

 

방법 A: 강의 슬라이드(11p) 방식 (exch 사용)

가장 추천하는 방법입니다. temp 변수를 쓰지 않고 두 값을 계속 교환(swap)합니다.

• 조건: less(a[j], a[j-1]) 유지
• 내용: exch(a, j, j-1); 수행 (슬라이드 6p에 정의된 메서드)

방법 B: 작성하시던 방식 (Shifting 사용)

temp에 보관한 값과 왼쪽 값을 비교해야 합니다.

• 조건: less(temp, a[j-1])로 수정
• 내용: a[j] = a[j-1]; 유지 (값을 오른쪽으로 한 칸 밀기)

---

 

 

• 의문점: "j-1은 왜 나오나?"
  • 답변: 삽입 정렬은 '이미 정렬된 앞부분'에 현재 값을 끼워넣는 것입니다. 따라서 내 바로 왼쪽(j-1)이 나보다 크다면 내가 왼쪽으로 계속 이동해야 하기 때문에 j-1과 비교합니다.

 

• 의문점: "마지막에 exch(a, i, j)는 왜 하나?" (수정 필수)
  • 답변: 이 부분은 삭제해야 합니다. PDF 방식(Swap 방식)에서는 루프 안에서 계속 자리를 바꾸며 이동하므로 루프가 끝나면 이미 제 자리에 가 있습니다. 만약 temp를 쓰는 Shifting 방식을 쓰신다면 마지막엔 a[j] = temp;라고 대입해야 합니다.

 

• 치명적 누락: h를 줄여나가는 루프가 없습니다.
  • 수정: 전체 로직을 while (h >= 1) { ... h /= 3; }으로 감싸야 합니다. 쉘 정렬은 큰 간격(h)부터 시작해 1이 될 때까지 간격을 좁히며 삽입 정렬을 반복하는 알고리즘입니다.

• 의문점: "i 루프의 시작점?" (수정 필수)
  • 답변: i는 0이 아니라 **h**부터 시작해야 합니다. 0번 인덱스와 비교할 대상이 0 - h이므로 인덱스 오류가 나거나 의미 없는 비교가 됩니다.

 

만약 내림차순(Descending)으로 바꾸고 싶다면?

• 가장 큰 값을 찾아서 앞으로 보내야 합니다.
• 방법 1: if(less(a[minIdx], a[j])) 로 바꿉니다. (내 현재 최강자보다 j가 더 큰가?)

선택정렬에서

 

 

 

근데 왜 최솟값을 찾으면 오름차순이 되고, 최댓값을 찾으면 내림차순이 되지? 

• 1회전 (i=0, 맨 첫 번째 자리):
  • 누구를 앉힐까? 전체 중에 **제일 작은 놈(최솟값)**인 1을 찾아서 맨 앞(0번 자리)에 앉힙니다.
  • 결과: [1, 3, 5, 2, 4] (1이 맨 앞에 옴)

 

• i=0일 때: "여긴 전교 1등 자리야." → 최솟값을 찾아서 넣으면 오름차순.
• i=0일 때: "여긴 전교 꼴등 자리야." → 최댓값을 찾아서 넣으면 내림차순.

 

 

 

 

 

 

• "j=i+1 이었지만, 삽입정렬에서는 i=j인가?"
  • 네, 맞습니다. 선택 정렬은 현재 위치의 '오른쪽'군단에서 최솟값을 찾으러 나가지만, 삽입 정렬은 현재 원소(i)를 들고 '왼쪽'으로 거슬러 올라가며 자리를 찾으므로 j = i부터 시작하여 j-- 하는 것이 맞습니다.

 

 

h를 줄여주는 시점은 "해당 h 간격에 대한 모든 정렬(h-sorting)이 끝난 뒤" 입니다.

• 즉, for (int i = h; i < n; i++) 루프가 완전히 종료되어 배열 전체가 h 간격으로 정렬된 상태가 되었을 때, 비로소 h = h / 3을 수행하여 더 촘촘한 간격으로 넘어갑니다.
• 작성하신 코드의 위치(h = h / 3;)는 아주 정확합니다. (가장 바깥쪽 while문 안쪽, for문 바깥쪽)

 

 

for (int i = h

1 쉘정렬에서 i도 h부터 시작해야함

2 j랑 j-h랑 비교하니깐, j>=h부터인거고 

 

 

less(j, j-h)

이렇게 쓰시면 배열의 값을 비교하는 게 아니라, **방 번호(인덱스)**를 비교하게 됩니다.

 

 

---

 

 

 

 

1. B[] 배열을 왜 만드는가?

• 이유: 계수 정렬은 '제자리 정렬(In-place Sort)'이 아니기 때문입니다.
• 숫자들의 개수를 센 뒤에 그 숫자들이 정렬된 배열의 어느 위치에 들어가야 할지 계산은 했지만, 원본 배열 A에 바로 덮어씌워 버리면 아직 정렬되지 않은 다른 데이터들을 잃어버리게 됩니다. 그래서 안전하게 **정렬된 결과를 담을 새 바구니 B**가 필요합니다.

2. 자바 배열의 초깃값

• 맞습니다. 자바에서 int[] 배열을 생성하면 모든 칸은 0으로 자동 초기화됩니다. 따라서 C 배열을 0으로 채우는 코드는 따로 짤 필요가 없습니다.

 

 

누적합을 구하면 좋은 점:

이제 1번 숫자에게 "너 어디 앉아?"라고 물으면, 누적합 결과인 C[1]을 보고 **"응, 나는 5번 자리(까지)가 내 구역이야!"**라고 바로 알 수 있습니다.

 

 

int pos = C[value] - 1; // 2. 그 값이 갈 방 번호를 계산한다 (0부터 시작하니까 -1).

 

 

 

• i = 0부터 하면: 정렬은 되지만 **'불안정 정렬'**이 된다. (데이터 순서가 뒤바뀜)
• i = n-1부터 하면: 정렬도 되고 **'안정 정렬'**도 된다. (원본 순서 유지)

 

 

기수 정렬(Radix Sort)

"계수 정렬(Counting Sort)을 일의 자리부터 시작해서 자릿수별로 여러 번 반복하는 것"

 

 

 

 

계수 정렬은 한 번 하면 끝이지만, 기수 정렬은 '일의 자리 정렬 결과'를 가지고 '십의 자리 정렬'을 해야 합니다.

• 그래서 B 배열에 정렬된 결과를 담은 후, 반드시 다시 A 배열로 복사해줘야 합니다. 그래야 다음 자릿수 정렬 때 그 결과가 이어집니다. (이게 안 되면 정렬이 다 깨집니다.)

 

 

자릿수 꺼내기 (가장 중요한 부분)

공식: (A[i] / exp) % 10

 

 

예시: 1234에서 '3'(십의 자리) 꺼내기

1단계: / 10 (나누기) — "원하는 숫자를 맨 뒤로 밀기"

우리가 원하는 '3'은 지금 뒤에서 두 번째 자리에 있죠? 이걸 맨 끝자리로 옮기고 싶습니다.

• 1234 / 10을 하면? → 결과는 **123**입니다. (자바 정수 계산이라 끝에 있던 4는 버려집니다.)
• 보이시나요? 이제 우리가 찾던 3이 맨 끝으로 왔습니다!

2단계: % 10 (나머지) — "맨 끝자리 하나만 쏙 빼오기"

이제 맨 끝에 있는 3만 가져오면 됩니다. 어떤 숫자든 10으로 나눈 나머지를 구하면 무조건 맨 끝자리 하나만 나옵니다.

• 123 % 10을 하면? → 123을 10으로 나눈 나머지는 **3**입니다.
• 성공! 우리가 원하던 3을 뽑아냈습니다.

 

 

그 이유는 우리가 쓰는 숫자가 **'10진법'**이기 때문입니다. 아주 간단한 원리인데, 숫자의 구조를 뜯어보면 바로 이해가 가실 거예요.

---

1. 숫자의 정체 (예: 457)

우리가 457이라고 쓰는 숫자는 사실 이런 뜻입니다.

• 400 + 50 + 7
• 다른 말로 하면: (10 × 40) + (10 × 5) + 7

2. 10으로 나누면 어떤 일이 벌어질까?

457을 10명이 똑같이 나눠 가진다고 생각해보세요.

• 400원은 10명이서 40원씩 깔끔하게 나눠 가질 수 있습니다. (나머지 0)
• 50원도 10명이서 5원씩 깔끔하게 나눠 가질 수 있습니다. (나머지 0)
• 그런데 마지막 7원은? 10명이서 나눠 가질 수 없죠. 그래서 나머지가 됩니다.

즉, **10의 배수 부분(450)**은 10으로 나누면 무조건 사라지고, **10보다 작은 마지막 자리 숫자(7)**만 쏙 남게 되는 것입니다.

 

 

 

 

 

// 1. 자릿수(exp)를 1부터 최대값의 자리까지 10배씩 키우며 반복

for (int exp = 1;   max / exp > 0; exp *= 10) {

 

while로 한다면 증감식이 마지막 부분에 있으면 되는거고 

 

 

(A[i]/exp)%10

 

1234/1 해서

1234 나오더라도

젤 마지막 수 가져오는건 

%10에서 하기때문에 

 

 

 

maxIndex 찾는 부분 (비교 오류)

• 현재 코드: if(A[i] > maxIndex)
• 문제점: A[i](값)를 maxIndex(인덱스 번호)와 비교하고 있습니다.
• 수정: if(A[i] > A[maxIndex]) (값과 값을 비교해야 합니다.)

---

a와 aux, 왜 a가 결과물인가? (철학)

• 복사 방향: a → aux (임시 저장) 후 다시 aux → a (정렬해서 담기)
• 이유: a는 우리가 최종적으로 정렬하고 싶은 원본 배열입니다.

 

 

 

 

• 루프 범위: i < hi가 아니라 **i <= hi**여야 합니다. (마지막 원소까지 복사해야 하니까요.)
• 비교 대상: 말씀하신 대로 aux를 보고 비교해야 합니다. a는 지금 값이 계속 바뀌고(덮어씌워지고) 있는 중이라 믿을 수 없기 때문입니다.

for (int k = lo; k <= hi; k++) { // lo부터 hi까지 복사!
    aux[k] = a[k];
}

// ... 중략 ...
else if (less(aux[j], aux[i])) { // aux(복사본)를 비교해서
    a[k] = aux[j++];            // a(원본)에 확정 대입!
}

 

 

 

if (lo >= hi) return; 의 의미

• lo == hi: 정렬할 범위에 원소가 딱 1개 남았다는 뜻입니다. (예: lo=5, hi=5)
• 원소가 1개인 배열은 이미 정렬된 상태라고 봅니다. 더 이상 쪼갤 수도 없죠.
• lo > hi: 잘못된 범위이거나 원소가 0개인 경우입니다.

 

//탑다운과 바텀업 차이는, sort안에서만이고, merge는 똑같았엇나

ㅇㅇ

 

 

 

 

• TD 방식의 merge: a를 aux에 복사한 뒤, 다시 a에 채워 넣음 (내부에 for 복사 루프 있음)
• 현재 코드(BU)의 merge: 복사 과정 없이, in 배열의 값을 비교해서 바로 out 배열로 쏴줘야 합니다. (내부에 복사 루프가 없어야 함)

---

연결리스트방식: 젤앞에 추가

head있음 

 

 

 

//배열이나 bst에서는 체일 가까이있는? 걸 리턴햇지만, 연결리스트방식에서는 어차피 순차 탐색이고, 젤 앞에 추가하기때문에
//search랑 get 메소드 분리를 안한건가

ㅇㅇ

 

 

• 연결 리스트(SequentialSearchST): 키들이 들어온 순서대로(정확히는 맨 앞에 추가된 순서대로) 뒤섞여 있습니다.
• 여기서는 **"있냐 없냐"**만 중요하지, "어느 위치 근처에 있냐"라는 개념 자체가 없습니다. 따라서 get이든 put이든 그냥 앞에서부터 끝까지 찾는 단순 반복문이라 굳이 로직을 복잡하게 분리할 필요가 없는 것입니다.

 

 

if(ptr.key.equals(key))

1. 자바의 모든 객체는 equals를 기본적으로 가지고 있어서 문법적으로 문제가 없습니다.
2. 심볼 테이블의 키로 주로 쓰이는 String이나 숫자 타입들은 이미 자바 내부적으로 equals가 오버라이딩 되어 있어서 우리가 직접 구현하지 않아도 값 비교가 잘 되는 것입니다.

만약 본인이 직접 만든 Student 클래스 같은 것을 키로 쓰신다면, 그때는 반드시 equals를 직접 오버라이딩 해주어야

 

 

 

 

1. 왜 SequentialSearchST(연결 리스트)는 equals()만 쓰나요?

• 목적: "똑같은 게 리스트에 있는가?"만 확인하면 됩니다.
• 특징: 정렬을 하지 않기 때문에 "누가 더 큰지"는 궁금하지 않습니다.
• 제네릭: 그래서 코드 상단에 그냥 <K, V>라고만 되어 있고, Comparable 제약이 없습니다. String이 Comparable을 가지고 있더라도, 이 클래스에서는 그냥 그 기능을 안 쓰고 **equals()**만 가져다 쓰는 것입니다.

2. 왜 BinarySearchST나 BST는 Comparable이 꼭 필요한가요?

• 목적: "왼쪽으로 갈까, 오른쪽으로 갈까?"를 결정해야 합니다.
• 특징: 정렬된 상태를 유지해야 하므로 equals()만으로는 부족합니다. equals()는 "같다/다르다"만 알려주지, "작다/크다"를 알려주지 못하기 때문입니다.
• 제네릭: 그래서 코드 상단에 K extends Comparable<K>라고 강제로 제약을 걸어둡니다. 그래야만 안심하고 key.compareTo()를 호출할 수 있으니까요.

 

 

User 2:54 PM

object는 equals는 있지만 compareTo는 없어서인가

ㅇㅇ

 

 

• 메소드: compareTo()
• 위치: Object에 없음. 오직 Comparable 인터페이스를 구현한 클래스에만 있음.

 

 

왜 자바는 Object에 compareTo를 넣지 않았을까요?

모든 객체가 "똑같은지"는 비교할 수 있지만, 모든 객체가 "순서(크기)"를 가질 수는 없기 때문입니다.

• 사람(객체): 이름 순으로 세울지, 나이 순으로 세울지 기준이 필요함.
• 버튼(객체): 버튼A가 버튼B보다 "크다"는 것이 논리적으로 성립하지 않을 수 있음.