1. 알고리즘 & 자료구조

1.1 이분 탐색 (Binary Search)

정렬된 배열에서 탐색 범위를 절반씩 줄여가며 값을 찾는 알고리즘임.

• 시간복잡도: O(log N)
• 전제 조건: 반드시 정렬된 상태

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1

---

1.2 분할 정복 (Divide and Conquer)

문제를 쪼개고 → 해결하고 → 합치는 방식

• Divide: 문제를 작은 단위로 분할
• Conquer: 각각 해결
• Combine: 결과 합침

대표 예시:

• Merge Sort
• Quick Sort
• Binary Search

---

1.3 정렬 알고리즘

버블 정렬 (Bubble Sort)

• 인접 요소 비교 후 swap

• 가장 단순, 성능 최악

• 시간복잡도: O(N²)

---

머지 정렬 (Merge Sort)

• 분할 → 정렬 → 병합

• 안정 정렬

• 시간복잡도: O(N log N)

---

퀵 정렬 (Quick Sort)

퀵 정렬의 핵심은 partition(분할 방식)임
대표적으로 2가지가 있음

---

1) Lomuto Partition (단순하지만 비효율 가능)

• pivot: 보통 마지막 요소
• i 포인터: 작은 값 영역 끝
• j 포인터: 순회

def lomuto_partition(arr, low, high):
    pivot = arr[high]
    i = low
    
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    
    arr[i], arr[high] = arr[high], arr[i]
    return i

특징:

• 구현 쉬움
• swap 많음 → 성능 손해 가능

---

2) Hoare Partition (더 효율적)

• pivot: 보통 첫 번째 요소
• 양쪽에서 중앙으로 이동

def hoare_partition(arr, low, high):
    pivot = arr[low]
    left = low - 1
    right = high + 1
    
    while True:
        left += 1
        while arr[left] < pivot:
            left += 1
            
        right -= 1
        while arr[right] > pivot:
            right -= 1
        
        if left >= right:
            return right
        
        arr[left], arr[right] = arr[right], arr[left]

특징:

• swap 횟수 적음
• 실제로 더 빠름
• 구현 난이도 약간 높음

---

정리:

방식	장점	단점
Lomuto	구현 쉬움	swap 많음
Hoare	성능 좋음	구현 어려움

---

1.4 자료구조

(생략 없이 그대로 유지 가능 — 핵심은 뒤 Redis 파트라 간결 유지)

---

2. 미니 레디스 구현

2.1 캐시 개념

• 메모리에 데이터를 저장해서 빠르게 접근
• DB 부하 감소 목적

핵심:

• Temporal Locality (최근 데이터 재사용)
• Spatial Locality (근접 데이터 활용)

---

2.2 실무 활용

Redis 사용 사례:

• 세션 저장
• API 응답 캐싱
• 랭킹 시스템 (ZSET)
• 메시지 큐

---

2.3 RESP vs HTTP

RESP (Redis Serialization Protocol)

*2
$3
GET
$3
key

---

HTTP와 차이점

항목	RESP	HTTP
목적	DB 통신	웹 통신
구조	매우 단순	헤더 + 바디
파싱 비용	낮음	높음
상태 코드	없음	있음
텍스트 크기	작음	큼

---

RESP의 강점

1. 파싱이 매우 빠름
   → 단순한 구조 (*, $, CRLF)

2. 네트워크 비용 절감
   → HTTP보다 데이터 크기 작음

3. 상태 없음 (stateless)
   → 빠른 요청/응답 가능

4. 구현이 쉬움
   → 직접 Redis 서버 만들 때 유리

핵심 요약:

RESP는 "속도를 위해 극단적으로 단순화된 프로토콜"

---

2.4 TTL (Time To Live)

TTL이 필요한 이유

1. 캐시 데이터는 영원히 유지되면 안됨
2. 오래된 데이터 → 데이터 불일치 발생
3. 메모리 누수 방지

예:

• 로그인 세션 만료
• API 캐시 갱신
• 토큰 유효시간

---

TTL 동작 방식

SET key value EX 60

→ 60초 뒤 자동 삭제

---

TTL 구현 방식 (핵심)

Redis 내부에서는 크게 2가지 방식 사용

---

1) Lazy Expiration (접근 시 삭제)

• 키를 조회할 때 TTL 확인
• 만료되었으면 삭제

def get(key):
    if key in store:
        if expired(key):
            delete(key)
            return None
        return store[key]

장점:

• 구현 간단
• CPU 사용 적음

단점:

• 접근 안 하면 계속 남아있음

---

2) Active Expiration (주기적 삭제)

• 일정 시간마다 랜덤 샘플 검사
• 만료된 키 제거

def cleanup():
    for key in random_keys():
        if expired(key):
            delete(key)

장점:

• 메모리 효율 좋음

단점:

• CPU 사용 증가

---

실제 Redis 전략

→ 두 가지 혼합

• Lazy + Active 같이 사용
• 성능 + 메모리 둘 다 잡음

---

3. 프로젝트 준비

(구조 유지, 핵심만 정리)

3.1 기획 및 설계

• 요구사항 정의
• 아키텍처 설계
• 데이터 모델링

---

3.2 개발 준비

• API 명세 작성
• 협업 규칙 정의

---

3.3 구현

• 작은 단위부터 개발
• 테스트 병행
• 반복적 개선

---