알고리즘) 강의(26.3.18)

 

이진 검색 트리랑은 차이점이 뭐지[  ]

 

퀴즈에 어떻게 나오려나, 이름 ?(아니야 그렇게는 안낼것같은데... 개념 많아서 그런 문제도 있으려나 

 

 

이진 탐색 코드:경곗값[  ]

 

 

put get delete[  ]

 

 

 

"Iterator와 Iterable의 차이는?"

 

 

 

"왜 배열을 2개(keys[], vals[]) 쓰는가? 객체로 안 하고?"

자료구조 시간에 했던것이랑 차이 

 

 

---

put, delete 반복문의 < (두번째 부분 다름)

 

연결리스트로 할땐, <K extends Comparable<K>,v> 필요없는 이유가

그냥 나열이니깐, 

 

 

 

---

왜 뒤에서부터 시작하는지

3번 자리에 새 책을 넣으려고 3번에 있던 책을 4번으로 옮깁니다. (이때 4번에 있던 책은 지워져 버립니다!)

for (int j = N; j > i; j--) {
    keys[j] = keys[j-1];
    vals[j] = vals[j-1];
}

• int j = N: 현재 데이터가 N-1번 인덱스까지 차 있으므로, 비어있는 칸인 N번을 타겟으로 잡습니다.
• j > i: 새 데이터가 들어갈 자리(i) 직전까지 계속 이동합니다. (i번 자리가 비워지면 멈춤)

 

 

 

 

 

 

 

 

 

만약 등호를 붙여서 j가 i까지 가게 되면 어떤 일이 벌어질까요?
코드 내부 로직이 keys[j] = keys[j-1] 이기 때문에, j가 i가 되는 순간 다음과 같은 코드가 실행됩니다.

• keys[i] = keys[i-1];

이게 왜 문제일까요?

• i-1 자리에 있는 값은 내가 건드릴 필요가 없는(이미 정렬이 끝난) 앞쪽 데이터입니다.

"중간에 끼워 넣을 때는 덮어쓰니까 괜찮아 보일 수 있지만, '배열의 맨 앞'에 넣을 때 프로그램이 터져버리기(에러)" 때문에

 

 

 

 

 

 

 

1. j=4: keys[4] = keys[3] (G 이동) -> [A, C, E, G, G]
2. j=3: keys[3] = keys[2] (E 이동) -> [A, C, E, E, G]
3. j=2가 되는 순간: 2 > 2는 거짓이므로 루프 종료.
4. 결과: keys[2] 자리에 E가 남아있지만, 어차피 'D'로 덮어쓸 예정이라 상관없음. (안전하게 E는 3번으로 대피 완료!)

(마치 삽입정렬처럼)

 

 

 

 

 

왜 4번 읽나 

젤 처음에 하는 일은 **"메모리 꽉 찰 때까지 읽어서(Read 1) → 그 안에서 정렬하고 → 런(Run)이라는 이름으로 디스크에 뱉어내는(Write 1) 일"**을 무한 반복하는 것입니다.

이후에 이 '런'들을 다 같이 불러모아 하나로 합치는 과정이 우리가 방금 얘기한 **Phase 2(병합 단계)**가 됩니다!

 

 

 

 

왜 메모리에서 정렬을 해야 하나요?

**2단계인 '병합(Merge)'**을 하기 위해서입니다.
'병합'이라는 기술의 전제 조건은 **"합칠 대상들이 이미 각각 정렬되어 있어야 한다"**는 것입니다.

• 만약 1단계에서 정렬을 안 하고 그냥 뱉으면, 2단계에서 데이터를 합칠 때 어디가 작은 값인지 알 수 없어 전체 데이터를 다 뒤져야 합니다.

 

 

 

 

 

[1부] 외부 정렬(External Sort) 성능 개선 전략

외부 정렬은 디스크 I/O 비용이 매우 크기 때문에(1GB 정렬에 약 4시간 소요), 이를 줄이기 위한 4가지 전략을 배웠습니다.

1. 더블 버퍼링 (Double Buffering)
   • 개념: 메모리가 충분히 클 때, 현재 병합(Merge) 중인 블록 외에 다음에 읽어올 블록을 미리 메모리에 가져다 놓는 방식입니다.
   • 효과: CPU가 메모리에서 병합 작업을 하는 동안 디스크는 다음 데이터를 읽는 I/O 작업을 수행하므로, CPU 작업과 I/O 작업을 동시에 진행하여 대기 시간을 줄입니다.
2. 멀티플 디스크 (RAID) 활용
   • 개념: 데이터를 여러 개의 독립적인 디스크에 나누어 저장(데이터 중복/분산)하는 방식입니다.
   • 효과: 여러 디스크에서 동시에 데이터를 읽어오므로(Parallel I/O), 순차적으로 읽을 때보다 속도가 훨씬 빨라집니다.
3. 런 생성(Run Generation) 알고리즘 
   • 개념: 기본적으로 런(Run)의 크기는 메모리 크기에 제한되지만, '대체 선택(Replacement Selection)' 기법을 쓰면 메모리 크기보다 더 큰 런을 만들 수 있습니다.
   • 동작: 메모리에 데이터를 채우고 가장 작은 값을 출력하되, 새로 들어온 값이 방금 출력한 값보다 작으면 다음 런을 위해 '마킹'하고 메모리에 유지합니다.
   • 효과: 런의 개수가 줄어들어 병합 단계가 단순해지고 빨라집니다.
4. 최적 병합 순서 (Huffman Tree 활용)
   • 개념: 생성된 런들의 크기가 제각각일 때, 어떤 순서로 병합하느냐에 따라 비용이 달라집니다.
   • 전략: 크기가 작은 런들부터 먼저 병합하여 덩치가 큰 데이터가 여러 번 병합에 참여하는 것을 방지합니다.
   • 결과: 이 과정을 통해 만들어진 최적의 병합 트리를 **허프만 트리(Huffman Tree)**라고 합니다.

---

[2부] 검색 구조 (Search Structures) - 심볼 테이블

2장의 주제는 특정 키(Key)를 주면 값(Value)을 알려주는 **심볼 테이블(Symbol Table)**입니다.

1. 개념 및 API

• 정의: 키-값 쌍의 모임 (Java의 Map, Python의 Dictionary).
• 활용 예: 영한사전(단어-뜻), 색인(단어-페이지), DNS(도메인-IP), 은행(계좌번호-정보).
• 핵심 연산 (CRUD):
  • Put: 새로운 쌍 추가 또는 기존 키의 값 업데이트. (Value는 null이 될 수 없음)
  • Get: 키에 해당하는 값 검색. (없으면 null 반환)
  • Delete: 키 삭제. (구현의 편의를 위해 put(key, null)로 대체하기도 함)
  • Contains, Size, IsEmpty, Keys(반복자).
• 제약 조건: 키는 크기 비교가 가능해야 하므로 Comparable 인터페이스를 구현해야 합니다.

2. 성능 테스트 프로그램

• TestClient: 기본 동작(Put, Get) 확인용.
• FrequencyCounter: 대용량 파일에서 단어 빈도수를 계산하여 자료구조의 실제 성능을 측정함.

 

 

 

 

 

 

 

 

 

⚠️ 구현 시 주의사항 (메모리 단편화와 GC)

• ArrayList처럼 동적 배열을 쓸 때 초기 크기를 지정하지 않으면, 배열이 꽉 찰 때마다 2배로 키우고 복사하는 과정이 반복됩니다.
• 이는 메모리 단편화를 유발하고, 자바의 가비지 컬렉션(GC) 부하를 높여 시스템이 순간적으로 멈추는 현상을 초래할 수 있습니다. 따라서 데이터 개수를 안다면 초기 용량을 지정하는 것이 백엔드 프로그래밍에서 매우 중요합니다.

 

 

 

 

 

 

1. 연결 리스트 심볼 테이블 (SequentialSearchST)

① put 연산의 특징 (삽입)

• 중복 체크 후 삽입: 먼저 리스트 전체를 돌며 동일한 키가 있는지 확인합니다. 있으면 값을 업데이트하고 끝냅니다.
• 노드 추가 위치: 동일한 키가 없다면 **리스트의 맨 앞(front)**에 추가합니다.
  • 코드: first = new Node<K,V>(key, value, first);
  • 이 방식은 새로운 노드의 next가 기존의 first를 가리키게 하고, first를 새 노드로 갱신하는 한 줄의 코드로 구현됩니다.

② delete 연산 (단방향 연결 리스트의 한계)

• 이전 노드를 알아야 함: 단방향 리스트(next만 있음)에서 특정 노드를 지우려면, 그 직전 노드를 찾아야 합니다.
  • Case 1 (첫 번째 노드 삭제): first를 first.next로 바로 옮깁니다.
  • Case 2 (그 외): 현재 노드 x에서 x.next.key를 확인합니다. 즉, "내 다음 놈이 지울 놈인가?"를 계속 묻습니다. 맞다면 x.next = x.next.next를 통해 다음 노드를 건너뛰어 연결합니다.

③ keys()와 백엔드 최적화 (중요)

• ArrayList 초기 용량 설정: new ArrayList<K>(N)와 같이 현재 데이터 개수 N을 생성자에 전달하는 것을 매우 강조하셨습니다.
  • 이유: ArrayList는 내부적으로 배열을 사용하는데, 크기를 지정하지 않으면 기본값(12~15개)으로 생성됩니다. 데이터가 계속 추가되어 배열이 꽉 차면 2배 크기의 새 배열을 만들고 기존 내용을 복사하는 과정을 반복합니다.
  • 문제점: 이 과정은 **메모리 단편화(Fragmentation)**를 유발하고, 자바의 가비지 컬렉션(GC) 부하를 높입니다.
  • 결과: 실무(백엔드)에서는 GC가 도는 순간 서버가 일시 정지("Stop-the-world")되어 서비스 품질이 급격히 떨어집니다. 따라서 데이터 개수를 안다면 반드시 초기 크기를 지정해야 합니다.

---

2. 정렬 배열 심볼 테이블 (BinarySearchST)

① search(Key key) 메소드의 리턴값 (핵심 아이디어)

• 이진 검색 결과, 키를 찾으면 해당 인덱스(mid)를 리턴합니다.
• 중요: 키를 못 찾았을 경우 -1이 아니라 lo를 리턴합니다.
  • 이유: 이 lo 값은 현재 찾는 키가 없더라도, 만약 이 키를 삽입한다면 정렬 순서상 들어가야 할 바로 그 위치이기 때문입니다.

(못찾았을때 lo는 hi보다 크거나 같은 상태이겟지만, 왜 lo-1이 아닌지 t)

 

 

② get 연산의 경계 검사

• search가 리턴한 인덱스 i를 바로 사용하기 전에 두 가지를 체크합니다.
  1. i < N: 찾고자 하는 키가 배열의 모든 값보다 커서 i가 N까지 증가했을 경우를 대비합니다. (에러 방지)
  2. keys[i].compareTo(key) == 0: search는 키가 없어도 인덱스(lo)를 리턴하므로, 실제 그 자리에 있는 값이 내가 찾는 값인지 다시 확인해야 합니다.

③ put 연산의 데이터 이동 (Shifting)

• 새로운 키를 삽입할 때, search로 찾은 위치 i 뒤에 있는 데이터들을 한 칸씩 뒤로 밀어야 합니다.
• 코드 로직: for (int j = N; j > i; j--)와 같이 뒤에서부터 앞으로 오면서 데이터를 복사해야 값이 덮어씌워지지 않습니다.
• 성능 팁: 교수님은 for문 대신 System.arraycopy()를 쓰는 것이 훨씬 빠르다고 언급하셨습니다.

 

 

 

put(key, null)을 이용한 삭제(Lazy Deletion, 게으른 삭제) 방식은 구현은 일시적으로 편할지 몰라도, size() 연산 복잡해짐

 

 

 

 

 

<K extends Comparable<K>, V> 해석하기

1 <K,V>

 

2<K extends ___>

제약을 주겠다 (인터페이스이건, 클래스이건 상관없이 모두 extends씀)

 

 

3

• 상한선 (T extends 클래스/인터페이스):
  • "아무리 못해도(최소한) 이 클래스이거나, 혹은 이 클래스의 자식이어야 한다"는 뜻입니다.
  • 즉, 그 위로는 못 올라간다는 의미의 **천장(상한선)**을 설정하는 것입니다.
  • 예: <K extends Comparable>이라고 하면, K는 Comparable 인터페이스를 구현한 놈이어야 하지, 그보다 '비교도 못 하는' 더 상위의 일반 Object는 올 수 없다는 뜻입니다.
• 하한선 (T super 클래스):
  • 반대로 super는 하한선입니다. "이 클래스이거나, 이 클래스의 **조상(부모)**이어야 한다"는 뜻입니다. (이건 보통 나중에 배우는 더 심화된 내용입니다.)

 

 

 

Comparable<K>의 뜻

Comparable은 자바에서 제공하는 **"비교를 위한 인터페이스"**입니다. 뒤에 붙은 <K>는 **"비교할 대상의 타입"**을 정해주는 것입니다.

• Comparable: "나는 크고 작음을 비교할 줄 아는 객체야"라는 선언입니다.
• <K>: "누구랑 비교할 건데? 바로 K 타입인 상대방과 비교할 거야"라는 뜻입니다.

따라서 Comparable<K>를 구현한 클래스는 반드시 내부적으로 **compareTo(K other)**라는 메소드를 가지고 있어야 합니다. 이 메소드는 나(this)와 상대방(other)을 비교해서 다음과 같은 값을 리턴합니다:

• 내가 더 크면: 양수
• 상대방과 같으면: 0
• 내가 더 작으면: 음수

(걍 외워도 될것같기도/이렇게 그냥 약속한거니깐..)