Laravel 리드·아키텍트 코딩·알고리즘 면접

재귀 쿼리(CTE)는 O(n) 시간복잡도로 조회하지만 MySQL 8.0+ 필요하며 깊이가 깊을수록 성능 저하가 있습니다. Nested Set은 조회 O(1)로 매우 빠르지만 삽입/삭제 시 O(n) 업데이트가 필요해 조직 변경이 잦으면 부적합합니다. Closure Table은 조회 O(d) (d=깊이), 삽입 O(d)로 균형잡혔으나 별도 테이블로 인한 공간복잡도 O(n²) 최악 케이스가 있습니다. Materialized Path는 구현이 단순하고 조회 O(n log n) (LIKE 쿼리), 삽입 O(1)이지만 경로 길이 제한과 인덱스 효율 문제가 있습니다. 조직 변경이 적고 조회가 많으면 Nested Set, 변경이 잦으면 Closure Table, 단순성이 중요하면 Materialized Path를 선택하며, Laravel에서는 각각 baum, franzose/closure-table, Eloquent scope로 구현 가능합니다.

Naive 매칭은 O(nm) (n=문서길이, m=패턴길이)로 느리며 대규모 시스템에 부적합합니다. KMP는 O(n+m)으로 개선되지만 단일 패턴에만 효율적입니다. Boyer-Moore는 실용적으로 O(n/m)에 가까운 성능을 보이나 역시 단일 패턴용입니다. Aho-Corasick은 k개 패턴을 O(n+m+z) (z=매칭 수)로 처리해 다중 키워드 검색에 최적입니다. MySQL Full-Text Search는 inverted index로 O(log n) 수준이지만 한글 형태소 분석이 약하고, Elasticsearch는 Lucene 기반으로 O(log n) 검색에 형태소 분석, 스코어링까지 제공합니다. Laravel에서는 소규모는 Scout + database driver, 중대규모는 Scout + Meilisearch/Algolia, 대규모는 Scout + Elasticsearch 조합이 적합하며, 실시간성이 중요하지 않으면 배치 인덱싱으로 비용을 절감할 수 있습니다.

Quick Sort는 평균 O(n log n), 최악 O(n²)이며 in-place 정렬로 공간복잡도 O(log n)이지만 최악 케이스 위험이 있습니다. Merge Sort는 안정적인 O(n log n)이나 O(n) 추가 메모리가 필요합니다. Heap Sort는 O(n log n) 보장에 O(1) 공간이지만 캐시 지역성이 나빠 실제로는 느립니다. Radix Sort는 정수 키에 대해 O(d*n) (d=자릿수)로 빠르지만 범용성이 낮습니다. 500만 건이 평균 1KB라면 5GB로 메모리 초과이므로 external merge sort가 필요하며, 데이터를 청크로 나눠 각각 정렬 후 k-way merge를 수행합니다. Laravel에서는 chunk(10000)로 분할해 각 청크를 Queue Job으로 정렬하고, Redis Sorted Set이나 임시 파일로 병합하거나, 아예 데이터베이스의 ORDER BY와 인덱스를 활용하는 것이 실용적입니다.

TSP는 NP-hard 문제로 완전탐색 O(n!)은 15개 이상에서 실용 불가능합니다. Held-Karp DP는 O(n²*2ⁿ)로 개선되어 15~20개까지 가능하지만, 100개는 여전히 불가능합니다. 15개 이하는 DP로 정확한 해를 구하고, 100개는 Greedy(nearest neighbor) O(n²), 2-opt O(n²) 개선, Genetic Algorithm, Simulated Annealing 같은 메타휴리스틱으로 준최적해를 빠르게 찾아야 합니다. Laravel에서는 계산 비용이 높으므로 Queue Job으로 비동기 처리하고, Redis에 결과를 캐싱하며, 필요시 Python/Go 같은 언어로 작성한 마이크로서비스를 Laravel에서 호출하는 하이브리드 아키텍처가 효율적입니다. 실시간 응답이 필요하면 미리 계산된 근사해를 제공하고 백그라운드에서 최적화를 진행합니다.

Chaining은 평균 O(1+α) (α=로드팩터)로 α가 커져도 성능 저하가 완만하지만, 추가 메모리(포인터)가 필요하고 캐시 지역성이 나쁩니다. Linear Probing은 캐시 친화적이나 클러스터링으로 α>0.7에서 O(n)에 근접하며, Quadratic Probing은 클러스터링을 완화하지만 secondary clustering이 발생합니다. Double Hashing은 클러스터링이 최소화되나 해시 함수 계산 비용이 두 배입니다. α>0.7이면 rehashing(테이블 크기 2배 확장)이 필요하며, 이는 O(n) 작업이므로 Laravel에서는 점진적 rehashing(일부씩 이동) 또는 읽기 시 lazy migration으로 응답 시간 스파이크를 방지합니다. 세션 드라이버 구현 시 Redis/Memcached 같은 검증된 해시 테이블 구현을 사용하는 것이 실용적이며, 커스텀 구현은 특수한 요구사항(예: 메모리 암호화)이 있을 때만 고려합니다.

모든 순회는 각 노드를 한 번씩 방문하므로 시간복잡도 O(n)입니다. 재귀는 공간복잡도 O(h) (h=높이)이며 구현이 간결하지만, PHP 기본 스택 제한(보통 512~1024)으로 깊은 트리에서 스택 오버플로우 위험이 있습니다. 반복문 구현은 명시적 스택(DFS) 또는 큐(BFS)를 사용해 O(n) 공간이지만 깊이 제한이 없습니다. Laravel에서는 재귀 대신 SplStack을 사용한 반복문으로 구현하거나, Collection의 flatten() 메서드를 활용하며, 매우 깊은 트리는 DB 단계에서 Closure Table로 평탄화해 저장합니다. JSON 직렬화 시 toArray() 재귀 호출 대신 큐 기반 레벨 순회로 구현하면 안전하며, Laravel의 Resource 클래스로 변환 로직을 캡슐화하는 것이 유지보수에 유리합니다.

Binary Heap은 삽입 O(log n), 삭제(최소값) O(log n), peek O(1)로 우선순위 큐에 최적화되어 있습니다. Sorted List는 삽입 O(n), 삭제 O(1)로 삽입이 느리고, Skip List는 삽입/삭제 평균 O(log n)이지만 구현 복잡도가 높습니다. 수백만 작업에서는 Heap이 가장 효율적이며, PHP의 SplPriorityQueue가 이를 구현합니다. 그러나 분산 환경에서는 Redis Sorted Set(ZADD O(log n), ZPOPMIN O(log n))이 원자적 연산과 영속성을 제공해 더 적합합니다. Laravel에서는 커스텀 Queue Connector를 만들어 Redis Sorted Set을 우선순위 큐로 사용하고, priority를 score로 매핑하며, Horizon으로 모니터링합니다. 매우 높은 처리량이 필요하면 RabbitMQ의 Priority Queue 기능을 Laravel Queue 인터페이스로 래핑하는 것도 고려할 수 있습니다.

Bitmap Index는 각 속성 값을 비트 배열로 표현하며, AND/OR/NOT 연산이 비트 연산으로 O(n/w) (w=워드 크기, 보통 64)에 처리됩니다. 1억 사용자는 12.5MB만 필요해 메모리 효율적이며, 여러 조건 조합이 매우 빠릅니다. B-Tree는 단일 조건 검색 O(log n)이지만 다중 조건 조합 시 인덱스 머지가 느립니다. Bitmap은 카디널리티가 낮은 속성(성별, 지역)에 효과적이고, 높으면(사용자ID) 메모리 낭비가 심합니다. Roaring Bitmap은 희소 비트맵을 압축해 공간을 절약합니다. Laravel에서는 Redis SETBIT/BITOP로 간단히 구현 가능하며, 복잡한 쿼리는 PHP-Roaring-Bitmap 라이브러리를 사용합니다. 실시간 타겟팅은 Redis Bitmap으로 계산하고, 결과를 캐싱하며, 배치 작업은 Eloquent로 후처리합니다.

Fixed Window는 시간을 고정 구간으로 나눠 O(1) 카운트하지만, 경계에서 burst traffic을 허용하는 문제가 있습니다. Sliding Log는 모든 요청 타임스탬프를 저장해 정확하지만 O(n) 공간과 O(n) 조회 시간이 필요합니다. Sliding Window Counter는 현재와 이전 윈도우 카운트를 가중 평균내어 O(1) 시간/공간으로 근사하며 실용적입니다. Laravel의 RateLimiter는 기본적으로 Fixed Window를 사용하지만, Redis Sorted Set으로 Sliding Log를 구현할 수 있습니다(ZADD로 타임스탬프 저장, ZREMRANGEBYSCORE로 만료 제거, ZCARD로 카운트). 메모리 효율을 위해서는 Sliding Window Counter를 Redis String 두 개로 구현하거나, Redis Streams의 XLEN과 XTRIM을 활용합니다. 높은 트래픽에서는 Token Bucket이나 Leaky Bucket 알고리즘이 더 효율적일 수 있습니다.

LRU는 Hash Map(키→노드 매핑 O(1))과 Doubly Linked List(사용 순서 유지)를 조합하여 get/put 모두 O(1)을 달성합니다. 조회 시 해시로 노드를 찾고 리스트 앞으로 이동시키며, 삽입 시 용량 초과면 리스트 끝(가장 오래된) 노드를 제거합니다. LFU는 빈도 기반이라 인기 항목을 오래 유지하지만 Min Heap 사용 시 O(log n)이고, 초기 인기 항목이 계속 남는 문제가 있습니다. FIFO는 O(1)이지만 재사용 패턴을 무시하고, Random은 구현이 단순하나 예측 불가능합니다. Laravel에서는 시간적 지역성이 강하면(최근 조회가 다시 조회될 가능성 높음) LRU, 특정 항목이 지속적으로 인기면 LFU, 패턴이 없으면 Random을 선택하며, Redis는 LRU 근사 알고리즘을 기본 제공하므로 Cache::store('redis')로 활용하는 것이 실용적입니다. 커스텀 구현은 SplDoublyLinkedList와 배열을 조합합니다.