알고리즘) 26.4.15

 
리니얼과 세퍼레이팅에서 적재율 [   ]
 
 

 

---

1. 자료구조의 비교: ArrayList vs LinkedList

1) 기본 특징 및 장단점

• ArrayList (배열 기반):
  • 장점: 주소 계산이 빨라 데이터 접근 속도가 매우 빠름.
  • 단점: 중간에 데이터를 삽입(예: 0번 인덱스)하면 기존 데이터들을 뒤로 한 칸씩 밀어야 하므로 이동 시간이 많이 걸림.
• LinkedList (연결 기반):
  • 장점: 중간에 데이터를 추가할 때 노드를 생성하고 링크만 연결하면 되므로 데이터 이동이 필요 없음.
  • 단점: 특정 위치를 찾기 위해 처음부터 노드를 따라가야 하므로탐색 속도가 느림.

2) 실험 결과 (데이터 10만 개 삽입 시)

• ArrayList 0번에 추가: 약 293ms (최악의 시나리오, 매번 모든 데이터 이동).
• ArrayList 랜덤 위치 추가: 약 140ms (평균적으로 중간쯤 삽입하므로 이동량이 절반으로 감소).
• LinkedList 0번에 추가: 매우 빠름 (순식간에 끝남, 링크만 연결하면 됨).
• LinkedList 랜덤 위치 추가: 약 8.5~8.6초 (삽입 지점까지 찾아가는 이동 시간 때문에 매우 느려짐).

---

2. 메모리 관리와 가비지 컬렉션(GC) 관점의 분석

1) ArrayList가 생각보다 빠른 이유

• 배열의 원소 이동(Shift Right) 연산은 시스템적으로 매우 최적화되어 있어 엄청난 속도로 실행됨.

2) 가비지 컬렉터(GC)와 힙(Heap) 메모리

• ArrayList의 문제: 크기가 꽉 차면 더 큰 배열을 만들고 복사한 뒤 기존 배열은 쓰레기(Garbage)가 됨. 초기 크기가 10인데 2000까지 늘어난다면 그 과정에서 많은 쓰레기 객체가 생성되어 GC에 부담을 줌.
• LinkedList의 오해와 진실: 과거에는 메모리를 적게 써서 GC에 유리하다고 생각했으나, 실제로는 각 노드 자체가 관리 대상이 되므로 GC의 부담이 더 큼.
• 캐시 효율성: 배열은 메모리에 순차적으로 붙어 있어 CPU 캐시 적중률이 높지만, LinkedList는 노드들이 메모리 곳곳에 흩어져 있어 효율이 떨어짐.

3) 메모리 단편화와 세대별 GC(Young/Old Generation)

• Young Generation: 금방 생성되고 사라지는 객체 관리 (Minor GC).
• Old Generation: 오래 살아남는 객체 관리 (Major/Full GC).
• LinkedList의 문제: 노드들이 여러 영역에 분산되어 관리하기 어렵고, 중간에 노드가 삭제되면 Old 영역에 구멍(단편화)이 생김. 힙 압축(Compaction) 시에도 이동해야 할 객체가 많아 GC 시간이 길어짐.
• 결론: 특수한 경우(삽입/삭제가 빈번한 경우)가 아니면 ArrayList를 쓰는 것이 성능상 유리하며, 초기 용량을 미리 지정(Initial Capacity)하여 리사이징을 방지하는 것이 가장 좋은 전략임.

---

3. Set 인터페이스 구현체

1) HashSet

• 순서 없고 중복 없는 자료구조.
• 배열 기반이며 기본 크기는 16, 필 레이쇼(Load Factor)는 0.75.
• 0.75라는 높은 수치를 허용하는 이유는 세퍼레이트 체이닝(Separate Chaining) 방식을 사용하여 충돌을 관리하기 때문임.

 
 

• 출력 순서는 해시값에 따라 결정되므로 무작위임.

2) LinkedHashSet

• HashSet과 동일하지만 입력 순서를 유지함.
• 해시 테이블 외에 별도의 연결 리스트를 사용하여 입력된 순서대로 노드를 연결해 둠.

3) TreeSet

• **레드-블랙 트리(Red-Black Tree)**로 구현됨.
• 데이터를 추가할 때 자동으로 정렬됨 (작으면 왼쪽, 크면 오른쪽).
• 내추럴 오더(Natural Order): Comparable 인터페이스의 compareTo 기준으로 정렬.

 
(그래서 힙에서는 natural이니깐 민힙이 기본값) 
 

• 생성자에서 Comparator를 넘겨주면 오름차순/내림차순 등 정렬 기준을 바꿀 수 있음.
• subSet(start, end) 등 구간 검색 기능을 제공함.

4) 집합 연산 -해봐야지 안다고 했던 부분 

• containsAll: 부분 집합 확인.
• addAll: 합집합.
• retainAll: 교집합.
• 주의: 연산 시 원본 셋이 변경되므로, 필요하다면 생성자를 통해 복사본을 만든 후 연산해야 함.

---

4. PriorityQueue (우선순위 큐)

• 힙(Heap) 자료구조를 이용함 (완전 이진 트리).
• 배열로 구현됨 (왼쪽 자식: 2i, 오른쪽 자식: 2i+1, 부모: i/2).
• 기본적으로 **미니 힙(Min-Heap)**으로 작동하여 가장 작은 값이 루트(0번 인덱스)에 위치함.
• 출력(toString)하면 배열 순서대로 나오지만, poll()로 하나씩 꺼내면 정렬된 순서대로 나옴.

 힙은 "완벽한 정렬"이 아니라 "부모가 자식보다 작다"는 규칙만 지키는 자료구조이기 때문입니다.

 

 

---

5. ArrayDeque (디큐)

• 양방향에서 삽입/삭제 가능 (Add/Remove First, Add/Remove Last).
• Stack으로도 활용 가능 (push, pop 사용).
• peek()은 스택이 비어있을 때 예외를 던지는 대신 null을 반환함.

---

6. 반복자 (Iterator vs ListIterator)

• Iterator: 모든 컬렉션에서 사용 가능. hasNext(), next(), remove() 제공. 한 방향(전진)으로만 이동 가능. 포문(for-each)은 내부적으로 이터레이터를 쓰지만 remove는 불가함.
• ListIterator: List 인터페이스(ArrayList, LinkedList)에서만 사용 가능.
  • 역방향 이동 가능 (hasPrevious, previous).
  • 중간에 데이터 수정(set) 및 추가(add) 가능.
  • 현재 인덱스 위치 확인 가능.

 
 

구분	Comparable	Iterable
핵심 메소드	compareTo(T o)	iterator()
의미	"나는 비교 가능한 객체다."	"나는 나열 가능한 객체다."
규격의 역할	정렬 알고리즘이 이 메소드를 호출함	for-each 문이 이 메소드를 호출함
사용 예시	TreeSet, sort()	for (String s : list)

---

7. Map 인터페이스 (Key-Value 쌍)

• 특징: 컬렉션(Collection) 인터페이스를 상속받지 않은 별개의 인터페이스임.
• 구성 요소:
  • Key: 중복 불가 (Set 형태). null 허용됨.
  • Value: 중복 가능 (Collection 형태).
  • Map.Entry: 키와 값의 한 쌍을 나타내는 인터페이스.

1) HashMap

• 해시 테이블 기반. 순서 없음.
• 탐색 성능: O(1). 매우 빠름.

2) LinkedHashMap

• 해시맵의 성능 + 입력 순서 유지.

3) TreeMap

• 레드-블랙 트리 기반. 키(Key)를 기준으로 정렬됨.
• 탐색 성능: O(log N). (100만 개 데이터 기준 뎁스 약 20 수준).
• 정렬된 순서로 데이터를 보거나 구간 검색이 필요할 때만 사용함.

4) HashMap vs TreeMap 성능 실험 (데이터 100만 개)

• 삽입 시간: HashMap(87ms) vs TreeMap(626ms) -> 약 8배 차이.
• 조회 시간: HashMap(38ms) vs TreeMap(480ms) -> 약 12배 차이.
• 결론: 단순 저장과 조회만 한다면 HashMap이 훨씬 유리함.
• 트리는 사잇값 구할때 

 

• 맵(Map)은 이터레이터가 없으므로 반복 처리를 하려면 entrySet()이나 keySet()을 통해 Set을 얻은 후 처리해야 함.

 
 
 
 
 
 
 

---

1. List (리스트)

• ArrayList (어레이 리스트)
  • 구현: 가변 크기 배열(Dynamic Array)
  • 특징: 인덱스로 즉시 접근하여 주소 계산이 빠름(). 하지만 데이터를 중간에 삽입/삭제할 때 기존 데이터들을 뒤로 밀거나 당기는 시프트(Shift) 연산이 필요함.
  • O(1)
• LinkedList (링키드 리스트)
  • 구현: 양방향 연결 리스트(Node 객체 연결)
  • 특징: 중간 삽입/삭제 시 링크만 바꾸면 되어 빠르지만, 특정 위치를 찾으려면 처음부터 쫓아가야 해서 탐색이 매우 느림().
  • O(n)O(n)O(n)

---

2. Set (집합)

• HashSet (해시 셋)
  • 구현: 해시 테이블(Hash Table) - 내부적으로 세퍼레이트 체이닝(Separate Chaining) 사용.
  • 특징: 순서가 전혀 없고 중복을 허용하지 않음. 부하율 0.75 기준에서 성능이 매우 안정적임.
• LinkedHashSet (링크드 해시 셋)
  • 구현: 해시 테이블 + 연결 리스트(Linked List)
  • 특징: 해시 셋과 같으나, 입력 순서를 기억하기 위해 별도의 연결 리스트로 노드들을 이어 놓음.
• TreeSet (트리 셋)
  • 구현: 레드-블랙 트리(Red-Black Tree) - 자가 균형 이진 탐색 트리.
  • 특징: 데이터가 들어올 때마다 자동으로 정렬됨. 구간 검색(subSet)이나 최솟값/최댓값 찾기에 유리함.

---

3. Queue & Deque (큐와 디큐)

• PriorityQueue (우선순위 큐)
  • 구현: 힙(Heap) - 내부적으로는 배열을 사용하여 완전 이진 트리 구조를 만듦.
  • 특징: 들어온 순서와 상관없이 우선순위(기본은 작은 값)가 높은 데이터가 먼저 나옴.
• ArrayDeque (어레이 디큐)
  • 구현: 순환 배열(Circular Array)
  • 특징: 양쪽 끝에서 삽입/삭제 가능. 스택(Stack)으로 사용 시 Stack 클래스보다 성능이 좋아 권장됨.

---

4. Map (맵) - Key-Value 쌍

• HashMap (해시 맵)
  • 구현: 해시 테이블(Hash Table)
  • 특징: 키(Key)를 해시 함수에 돌려 바로 값을 찾음(). 순서가 없음. 키는 중복 불가, 값은 중복 가능.
  • O(1)O(1)O(1)
• LinkedHashMap (링크드 해시 맵)
  • 구현: 해시 테이블 + 연결 리스트(Linked List)
  • 특징: 해시 맵과 같으나, 입력된 순서대로 데이터를 유지함.
• TreeMap (트리 맵)
  • 구현: 레드-블랙 트리(Red-Black Tree)
  • 특징: 키(Key)를 기준으로 자동 정렬됨. 해시 맵보다 느리지만(), 키의 순서가 중요하거나 범위 검색이 필요할 때 사용함.
  • O(log⁡n)O(\log n)O(logn)

---

요약: 무엇이 레드-블랙 트리인가?

질문하신 대로 이름에 **'Tree'**가 들어가는 TreeSet과 TreeMap은 모두 레드-블랙 트리로 구현되어 있습니다.

요약: 무엇이 해시 테이블인가?

이름에 **'Hash'**가 들어가는 HashSet, HashMap, LinkedHashSet, LinkedHashMap은 모두 해시 테이블 기반이며, 자바에서는 충돌 해결을 위해 세퍼레이트 체이닝 방식을 씁니다. (그래서 부하율 0.75를 쓰는 것입니다.)

요약: 무엇이 배열 기반인가?

ArrayList, PriorityQueue, ArrayDeque는 내부적으로 배열을 사용하여 데이터를 관리합니다. (그래서 초기 용량 Capacity 설정이 중요합니다.)
 
 
 
 
 

1. for-each 문에서 list.remove()를 호출하면 무조건 에러가 난다.
2. 일반 for 문으로 인덱스를 이용해 뒤에서부터 삭제하면 에러가 나지 않고 안전하다.
3. 단, LinkedList 같은 자료구조는 인덱스로 접근하는 것 자체가 느리기 때문에, 성능을 위해 **Iterator.remove()**를 쓰는 것이 원칙이다.

 
리스트 삭제하면, 요소들이 앞으로 당겨짐
일반 배열:삭제가 없음
 
 
 
 
그리고 for each에서
for(i in arrList){i=i+2}해도의미없는게
처음에는 단순히 복사본이라서 그런걸줄알았는데, 이게 이터레이터라서, 수정안되는건가

for-each 문은 내부적으로 이렇게 바뀝니다

사용자님이 작성하신 for (Integer i : arrList) { i = i + 2; } 코드를 컴파일러는 다음과 같이 해석합니다.codeJava

Iterator<Integer> it = arrList.iterator(); // 1. 이터레이터를 가져옴
while (it.hasNext()) {
    Integer i = it.next(); // 2. "i"라는 임시 변수에 현재 값을 복사해서 담음
    i = i + 2;             // 3. "i"라는 임시 변수의 값만 변경함
}

 
 

 왜 수정이 안 될까? (두 가지 결정적 이유)

이유 A: 임시 변수(복사본)의 한계

위 코드에서 Integer i = it.next(); 부분을 보세요. 여기서 i는 리스트 그 자체가 아니라, 리스트 안에 들어있는 값을 잠시 빌려와서 담아둔 **'지역 변수(Local Variable)'**일 뿐입니다.

• i = i + 2라고 하면, 지역 변수 i에 담긴 숫자만 바뀔 뿐, 리스트의 내부 배열에 있는 값이 바뀌는 것이 아닙니다.
• 리스트 입장에서는 "누군가 내 값을 빌려가서 자기 혼자 덧셈하고 있네?"라고 생각할 뿐, 자기 몸엔 아무런 변화가 없는 것이죠.

이유 B: 이터레이터의 설계 규칙

교수님 녹취록에서도 나왔듯이, 일반적인 Iterator 인터페이스는 next(), hasNext(), remove() 기능만 가집니다.

• 즉, 이터레이터는 데이터를 "꺼내오거나", "지우는" 기능은 있지만, "새로운 값을 집어넣는(set)" 기능이 아예 없습니다.
• 수정하고 싶다면 녹취록에 나온 **ListIterator**를 써서 litr.set(newValue)라고 명시적으로 명령해야 합니다.

 
 
 
 

만약 객체(Object)라면 어떨까?

이게 재미있는 부분인데, 만약 i가 단순 숫자가 아니라 객체라면 이야기가 달라집니다.codeJava

for (Person p : peopleList) {
    p.setName("홍길동"); // 이건 리스트 내부 데이터가 수정됨!
    p = new Person("임꺽정"); // 이건 수정 안 됨 (임시 변수 p의 주소만 바뀜)
}

 
 
 
**힙(Heap) 메모리와 가비지 컬렉션(GC)**을 언급하며 배열(ArrayList)과 연결 리스트(LinkedList)의 차이점
 

1. 객체의 개수와 가비지 컬렉터(GC)의 부담

• 배열 (ArrayList): 데이터가 100만 개 있어도, 실제 힙 영역에서 관리하는 커다란 객체는 **'배열 덩어리 하나'**입니다. GC 입장에서는 이 커다란 덩어리 하나가 사용 중인지 아닌지만 체크하면 됩니다.
• 연결 리스트 (LinkedList): 데이터 100만 개를 저장하려면, 데이터를 감싸는 '노드(Node) 객체' 100만 개를 각각 만들어야 합니다. 힙 메모리에 100만 개의 개별 객체가 생성되는 것이죠. GC는 이 100만 개 객체를 일일이 쫓아가며 "얘는 아직 쓰고 있나?"를 확인해야 하므로 관리 부담이 엄청나게 커집니다.

2. 세대별 메모리 관리 (Young vs Old Generation)

교수님이 자바 가상 머신(JVM)의 힙 구조를 설명하셨던 부분입니다.

• 구조: 힙은 최근에 만든 객체가 들어가는 **영 제너레이션(Young)**과 오래 살아남은 객체가 옮겨가는 **올드 제너레이션(Old)**으로 나뉩니다.
• 배열의 특징: 배열은 통째로 영 영역에 있거나 통째로 올드 영역에 있을 확률이 높습니다. 관리가 단순하죠.
• 연결 리스트의 문제: 리스트의 노드들은 생성 시점이 다를 수 있습니다. 어떤 노드는 처음부터 있어서 올드 영역에 있고, 중간에 추가된 노드는 영 영역에 있을 수 있습니다. 하나의 리스트가 메모리 여기저기에 **분산(Scattered)**되어 있어 효율이 급격히 떨어집니다.

3. 메모리 단편화(Fragmentation)와 구멍

• 연결 리스트의 삭제: 연결 리스트에서 중간 노드를 삭제하면, 올드 제너레이션 영역 중간중간에 **'빈 구멍'**이 생깁니다. 이를 단편화라고 합니다.
• 힙 압축(Compaction): 가비지 컬렉터는 이 구멍들을 메우기 위해 객체들을 한데 모으는 '압축' 작업을 하는데, 연결 리스트는 객체(노드) 수가 너무 많아서 이 이동 작업이 매우 고됩니다. 반면 배열은 덩어리가 적어 이동이 훨씬 쉽습니다.

4. 캐시 히트(Cache Hit)와 주소값

• 배열: 메모리 주소가 연속적입니다. CPU가 데이터를 읽을 때 옆에 있는 데이터도 같이 읽어오기 때문에 속도가 매우 빠릅니다.
• 연결 리스트: 노드들이 힙 영역 여기저기 맘대로 흩어져 있습니다. 다음 데이터를 읽으려면 메모리의 전혀 다른 주소로 점프해야 하므로 CPU 캐시를 전혀 활용하지 못하고 속도가 느려집니다.

과거에는 링키드 리스트가 메모리를 아껴서 좋다고 했지만, 현대 자바(JVM) 관점에서는 객체가 너무 많이 양산되고 메모리 여기저기에 구멍을 만들기 때문에 가비지 컬렉터에게 엄청난 부담을 준다. 따라서 웬만하면 어레이 리스트를 쓰는 것이 성능과 메모리 관리 측면에서 훨씬 유리하다."