What I've learned:

Array vs Linked List

Array와 Linked List는 대표적인 선형 데이터 구조이다. 두 구조는 각각 장단점이 뚜렷하며, 사용 목적에 따라 선택해야 한다.

---

Array (배열)

장점

1. 빠른 임의 접근 (Random Access)

   • 배열은 인덱스를 통해 원하는 요소를 O(1)에 접근할 수 있음
   • 메모리 상에 연속적으로 배치되어 있어 빠름

   let element = array[2] // O(1)

2. 캐시 친화적 (Cache-friendly)

   • 배열은 연속된 메모리 위치를 사용하므로, CPU 캐시 효율이 높음

3. 간단한 구조

   • 구현이 간단하고 대부분의 프로그래밍 언어에서 기본 제공됨

---

단점

1. 크기 제한

   • 배열은 고정 크기(static array)일 경우, 크기를 사전에 결정해야 함
   • 동적 배열(dynamic array)은 크기 변경이 가능하지만, resize에 O(n)의 비용 발생

2. 삽입 및 삭제 비용

   • 중간에 요소를 삽입/삭제하려면 나머지 요소를 이동해야 하므로, 최악의 경우 O(n)

   array.insert(3, at: 1) // O(n)
   array.remove(at: 1)    // O(n)

3. 메모리 낭비

   • 동적 배열은 종종 여유 공간을 남겨두어야 하므로 메모리 낭비 발생

---

Linked List (연결 리스트)

장점

1. 동적 크기 조절

   • 요소를 추가할 때 필요한 만큼 메모리를 할당하므로 크기 제한이 없음

2. 빠른 삽입 및 삭제

   • 특정 위치에서 요소를 추가/삭제하는 작업이 O(1)에 가능 (해당 노드에 접근한 경우)

   // 삽입
   newNode.next = current.next
   current.next = newNode
   
   // 삭제
   current.next = current.next?.next

3. 메모리 효율 (특정 상황)

   • 크기를 미리 예측할 수 없거나 빈번한 삽입/삭제가 필요한 경우 메모리 효율적

---

단점

1. 느린 임의 접근

   • Linked List는 순차적으로 탐색해야 하므로 특정 요소에 접근하는 데 O(n)의 시간이 소요됨

   var current = head
   while index > 0 {
       current = current?.next
       index -= 1
   }

2. 추가적인 메모리 사용

   • 각 노드가 데이터를 저장하는 외에도 포인터(참조)를 저장해야 하므로 추가 메모리 필요

3. 비효율적인 캐싱

   • 메모리가 비연속적으로 분산되어 있어 CPU 캐시 효율이 낮음

4. 복잡한 구현

   • 배열보다 구현이 상대적으로 복잡하며 디버깅도 어려움

---

Array vs Linked List 비교

특징	Array	Linked List
임의 접근 속도	O(1)	O(n)
삽입/삭제 속도	O(n) (중간 요소)	O(1) (노드 접근 시)
크기 조절	제한적 / 동적 배열은 O(n)	동적 크기 (O(1))
메모리 사용	효율적 (연속적 메모리)	비효율적 (포인터 저장 필요)
캐시 효율	높음	낮음
구현 난이도	간단	복잡

---

언제 무엇을 선택할까?

1. Array를 선택할 때

   • 요소의 개수를 사전에 알 수 있고, 임의 접근이 자주 필요한 경우.
   • 읽기 작업이 많고 삽입/삭제가 적은 경우.
   • CPU 캐시 효율이 중요한 경우.

2. Linked List를 선택할 때

   • 삽입/삭제 작업이 빈번한 경우.
   • 데이터 크기가 가변적이고, 초기 크기를 알 수 없는 경우.
   • 순차적으로 탐색하는 작업이 대부분인 경우.

---

결론:

• Array는 빠른 접근과 단순한 구조로, 일반적인 경우에 더 적합
• Linked List는 삽입/삭제가 많은 경우나 크기가 자주 변하는 상황에서 더 유용
• '순차적'인 것과 '연결적'인 것은 다름을 대표적으로 나타내는 비교임

Amortized Analysis

Amortized Analysis란?

• Amortized Analysis(분할 상환 분석)는 알고리즘의 특정 작업이 가끔씩 높은 비용(O(n))을 발생시키더라도, 다른 대부분의 경우에는 낮은 비용(O(1))으로 동작할 때 전체적인 평균 실행 시간을 평가하는 방법이다.
• 즉, 비용을 분산해서 분석한다고 보면 된다.

---

예시

1. Dynamic Array(동적 배열)

   • 배열 기반 Queue의 resize()와 같은 사례
   • 배열 크기를 두 배로 늘릴 때마다 복사 비용은 O(n)이지만, enqueue 연산은 대다수의 경우 O(1)이므로 평균적으로 Amortized O(1)

2. Stack의 Push-Pop과 Multi-Pop

   • 스택에서 pop 연산이 여러 번 호출될 때, 최악의 경우 전체 스택을 비우게 될 수도 있음. 하지만 그 과정에서 각 요소는 한 번만 pop 되므로 Amortized O(1)

3. 분리 연결 리스트의 Union-Find

   • Disjoint-set(서로소 집합)에서 경로 압축(path compression)과 같은 최적화를 적용하면, 여러 연산이 합쳐져도 Amortized O(α(n)) (α는 역아커만 함수)로 줄어듦

---

Amortized Analysis의 주요 기법

1. Aggregate Analysis

   • 모든 연산의 총 비용을 계산한 뒤, 연산 수로 나눠서 평균 비용을 계산
   • 예: 동적 배열에서 resize()의 비용 합산 후 평균 계산

2. Accounting Method (회계 방식)

   • 각 연산마다 "가상 비용(credit)"을 설정해 비용을 미리 분배.
   • 예: enqueue 때마다 약간의 비용을 미리 적립해 두고, 나중에 resize 비용으로 사용

3. Potential Method (잠재적 에너지 방식)

   • 데이터 구조에 에너지 또는 잠재 비용(potential)을 정의해 연산이 발생할 때마다 변화를 측정
   • 예: 현재 배열에 남은 빈 공간을 "잠재 에너지"로 간주

---

비슷한 개념과의 비교

• Worst-case Analysis: 최악의 경우에 초점을 맞춘 분석
• Average-case Analysis: 모든 입력의 평균 실행 시간을 계산
• Amortized Analysis: 최악의 경우를 포함하지만, 모든 연산의 평균적인 실행 시간을 계산

private(set)

private(set)은 변수나 프로퍼티의 읽기 접근은 공개적으로 허용하지만, 쓰기 접근은 선언된 파일 내에서만 가능하도록 설정하는 접근 제어자이다. 주로 외부에서는 값을 수정하지 못하도록 하면서 내부적으로만 값을 관리하고 싶을 때 사용된다.

예제:

struct Counter {
    private(set) var count = 0

    mutating func increment() {
        count += 1
    }
}

var myCounter = Counter()
print(myCounter.count) // 0 (읽기는 가능)
myCounter.increment()
print(myCounter.count) // 1
// myCounter.count = 10 // 오류! 외부에서는 수정 불가

레퍼런스 타입 비교 연산자 (=== & !==)

===와 !==는 두 레퍼런스 타입(주로 클래스 인스턴스)이 같은 메모리 주소를 가리키고 있는지 비교할 때 사용한다. 두 ViewController 인스턴스가 같은지 확인할 때도 자주 사용되곤 한다.

차이점:

• ==: 값이 같은지 비교 (Equatable 프로토콜 준수)
• ===: 메모리 주소가 같은지 비교 (동일한 객체인지 확인)

예제:

class MyClass {
    var value: Int
    init(value: Int) {
        self.value = value
    }
}

let obj1 = MyClass(value: 10)
let obj2 = obj1
let obj3 = MyClass(value: 10)

print(obj1 === obj2) // true (obj1과 obj2는 같은 객체를 참조)
print(obj1 === obj3) // false (obj1과 obj3은 다른 객체)
print(obj1 !== obj3) // true (obj1과 obj3은 다른 객체)