JavaScript 시니어 코딩·알고리즘 면접
새 면접Q. 대규모 로그 분석 시스템에서 특정 패턴을 찾아야 하는 상황입니다. 문자열 검색 알고리즘 중 Naive 방식, KMP(Knuth-Morris-Pratt), Boyer-Moore 알고리즘의 시간 복잡도와 동작 원리를 비교하고, JavaScript로 실무에서 대용량 텍스트 검색을 구현할 때 어떤 알고리즘을 선택해야 하는지 그 이유와 함께 설명해주세요. 또한 정규표현식 엔진의 백트래킹 문제와 이를 방지하는 방법도 함께 제시해주세요.
각 알고리즘이 불일치 발생 시 어떻게 패턴을 이동시키는지, 그리고 전처리 과정의 유무와 그 비용을 생각해보세요.
Naive 방식은 O(nm) 시간 복잡도로 모든 위치에서 패턴을 비교합니다. KMP는 O(n+m)으로 실패 함수를 전처리하여 불일치 시 패턴 내 반복 구조를 활용해 건너뜁니다. Boyer-Moore는 평균 O(n/m)으로 뒤에서부터 비교하며 bad character와 good suffix 규칙으로 큰 폭으로 이동합니다. 실무에서는 패턴 길이가 길고 알파벳이 다양할 때 Boyer-Moore가 유리하며, 짧은 패턴은 String.prototype.indexOf(네이티브 구현)가 최적화되어 있습니다. 정규표현식의 catastrophic backtracking은 중첩된 quantifier((a+)+)에서 발생하므로 atomic group이나 possessive quantifier를 사용하거나, 패턴을 단순화하고 타임아웃을 설정해야 합니다.
- • KMP는 실패 함수로 O(n+m) 보장, Boyer-Moore는 평균적으로 가장 빠름
- • 패턴 길이와 문자 집합 크기에 따라 알고리즘 선택
- • 정규표현식 백트래킹은 중첩 quantifier에서 지수적 시간 발생
- • 실무에서는 네이티브 메서드 활용과 패턴 최적화 병행
로그 분석, 전문 검색 엔진, 코드 에디터의 Find 기능 등에서 효율적인 문자열 매칭이 필수적입니다.
다국어 텍스트(유니코드)를 다룰 때 문자열 검색 알고리즘 구현 시 주의할 점과, JavaScript의 String.prototype.normalize를 활용한 정규화 전략을 설명해주세요.
Q. 소셜 네트워크에서 사용자 간 최단 연결 경로를 찾는 기능을 구현해야 합니다. BFS, DFS, Dijkstra, A* 알고리즘의 차이점과 각각의 시간/공간 복잡도를 설명하고, 가중치가 있는 그래프와 없는 그래프에서 각각 어떤 알고리즘을 선택해야 하는지 설명해주세요. 또한 JavaScript로 대규모 그래프(수백만 노드)를 메모리 효율적으로 표현하고 탐색하는 방법과, 양방향 탐색(Bidirectional Search)을 통한 최적화 전략도 제시해주세요.
가중치 유무, 최단 경로 보장 여부, 휴리스틱 사용 가능 여부를 기준으로 알고리즘 특성을 분류해보세요.
BFS는 O(V+E) 시간, O(V) 공간으로 무가중 그래프의 최단 경로를 보장하며 큐를 사용합니다. DFS는 같은 복잡도지만 스택을 사용하고 최단 경로를 보장하지 않습니다. Dijkstra는 O((V+E)logV) 시간으로 음수 가중치가 없는 그래프에서 최단 경로를 찾으며 우선순위 큐가 필요합니다. A*는 휴리스틱 함수로 탐색 방향을 유도해 평균적으로 더 빠릅니다. 대규모 그래프는 인접 리스트로 표현하고, Map과 Set을 활용하며, 필요 시 그래프 DB나 외부 저장소를 사용합니다. 양방향 탐색은 시작과 끝에서 동시에 탐색해 탐색 공간을 O(b^(d/2))로 줄입니다.
- • 무가중 그래프는 BFS, 가중 그래프는 Dijkstra 선택
- • A*는 휴리스틱으로 탐색 효율 향상, 최단 경로 보장은 admissible heuristic 필요
- • 대규모 그래프는 인접 리스트와 Map/Set으로 메모리 효율화
- • 양방향 탐색으로 탐색 깊이를 절반으로 줄여 성능 개선
소셜 네트워크 친구 추천, 지도 경로 탐색, 네트워크 라우팅, 의존성 그래프 분석에서 활용됩니다.
음수 가중치가 있는 그래프에서 Bellman-Ford 알고리즘이 필요한 이유와, 음수 사이클 탐지 방법을 설명해주세요.
Q. JavaScript의 Array.prototype.sort()는 V8 엔진에서 Timsort를 사용합니다. Timsort의 동작 원리와 왜 Merge Sort와 Insertion Sort의 하이브리드 방식인지 설명하고, 최선/평균/최악의 시간 복잡도를 제시해주세요. 또한 대용량 데이터 정렬 시 Quick Sort, Merge Sort, Heap Sort의 공간 복잡도 차이와 안정 정렬(stable sort) 여부가 실무에서 중요한 이유를 설명해주세요. 추가로 JavaScript에서 커스텀 비교 함수 작성 시 주의할 점도 제시해주세요.
실제 데이터는 부분적으로 정렬된 경우가 많다는 점과, 작은 배열에서는 단순한 알고리즘이 더 빠를 수 있다는 점을 고려하세요.
Timsort는 실제 데이터의 부분 정렬(run)을 감지하고 Insertion Sort로 작은 run을 정렬한 뒤 Merge Sort로 병합합니다. 최선 O(n), 평균/최악 O(nlogn)이며 안정 정렬입니다. Quick Sort는 O(logn) 공간이지만 최악 O(n^2)이고 불안정하며, Merge Sort는 O(n) 추가 공간이 필요하지만 항상 O(nlogn)이고 안정합니다. Heap Sort는 O(1) 공간이지만 불안정합니다. 안정 정렬은 동일 키를 가진 객체의 원래 순서를 유지해야 할 때 중요합니다. 커스텀 비교 함수는 반드시 일관된 전순서 관계를 만족해야 하며, 부호만 반환하고 부수효과를 피해야 합니다.
- • Timsort는 부분 정렬 활용과 하이브리드 방식으로 실제 데이터에 최적화
- • 안정 정렬은 다중 키 정렬이나 객체 정렬 시 순서 보존에 필수
- • 공간 복잡도는 in-place 여부로 결정되며 대용량 데이터에서 중요
- • 비교 함수는 transitivity, antisymmetry 만족 필요
대시보드 테이블 정렬, 검색 결과 랭킹, 데이터 집계 및 리포팅에서 정렬 알고리즘 선택이 성능에 직접 영향을 줍니다.
JavaScript에서 수백만 개의 객체를 여러 필드 기준으로 정렬해야 할 때, 성능을 최적화하기 위한 Schwartzian Transform 패턴을 설명해주세요.
Q. 계층형 조직도나 파일 시스템을 표현하는 트리 구조에서 DFS와 BFS를 각각 전위/중위/후위 순회로 구현할 때의 차이점과 사용 사례를 설명해주세요. 또한 JavaScript로 깊은 트리를 순회할 때 콜스택 오버플로우를 방지하기 위한 반복적(iterative) 구현 방법과, Generator 함수를 활용한 지연 평가(lazy evaluation) 전략을 제시해주세요. 추가로 대규모 트리에서 특정 노드 검색 시 경로 추적과 메모이제이션을 통한 최적화 방법도 설명해주세요.
재귀를 스택 자료구조로 명시적으로 변환하는 방법과, Generator의 yield를 활용한 중단 가능한 순회를 생각해보세요.
전위 순회는 부모-자식 순서로 복사/직렬화에 적합하고, 중위는 BST에서 정렬 순서를 얻으며, 후위는 자식 처리 후 부모 처리로 삭제/계산에 적합합니다. 반복적 DFS는 명시적 스택을 사용하고, BFS는 큐를 사용해 콜스택 제한을 피합니다. Generator 함수는 yield로 값을 하나씩 반환해 메모리를 절약하고 필요한 만큼만 순회합니다. 경로 추적은 부모 참조나 경로 배열을 유지하고, 자주 검색되는 노드는 Map에 캐싱하며, 불변 트리라면 경로를 메모이제이션합니다. 대규모 트리는 가상 스크롤링과 지연 로딩을 병행합니다.
- • 순회 방식은 처리 순서에 따라 용도가 다름(복사/검색/계산)
- • 반복적 구현은 명시적 스택/큐로 콜스택 한계 극복
- • Generator는 지연 평가로 메모리 효율과 조기 종료 가능
- • 경로 추적과 캐싱으로 반복 검색 최적화
파일 탐색기, 조직도 렌더링, AST 파싱, DOM 조작 등에서 트리 순회 알고리즘이 핵심입니다.
React의 가상 DOM을 Fiber 트리로 표현할 때, 어떤 순회 방식을 사용하고 작업 우선순위를 어떻게 관리하는지 설명해주세요.
Q. JavaScript의 Map과 Object의 내부 구현 차이를 해시 테이블 관점에서 설명하고, 해시 충돌 해결 방법인 Chaining과 Open Addressing(Linear Probing, Quadratic Probing)의 장단점을 비교해주세요. 또한 대규모 데이터를 다룰 때 로드 팩터(load factor)가 성능에 미치는 영향과 리해싱(rehashing) 시점을 결정하는 기준을 설명하고, WeakMap과 일반 Map의 메모리 관리 차이점도 제시해주세요.
해시 충돌 시 추가 메모리 사용과 캐시 지역성, 그리고 가비지 컬렉션과의 관계를 고려해보세요.
Map은 전용 해시 테이블로 구현되어 키 타입 제약이 없고 순서를 보장하며, Object는 프로토타입 체인과 속성 최적화에 초점을 둡니다. Chaining은 연결 리스트로 충돌을 처리해 삽입이 간단하지만 캐시 지역성이 낮고, Open Addressing은 배열 내에서 다음 빈 슬롯을 찾아 캐시 효율은 높지만 클러스터링이 발생합니다. 로드 팩터가 0.7~0.75를 넘으면 성능이 저하되므로 테이블 크기를 2배로 늘리고 모든 항목을 재배치합니다. WeakMap은 키가 약한 참조로 GC 대상이 되면 자동 삭제되어 메모리 누수를 방지하지만, 열거와 크기 확인이 불가능합니다.
- • Map은 순서 보장과 모든 타입 키 지원, Object는 문자열/심볼 키만 가능
- • Chaining은 구현 단순, Open Addressing은 캐시 효율 우수
- • 로드 팩터 임계값 초과 시 리해싱으로 성능 유지
- • WeakMap은 메모리 누수 방지, 캐시 구현에 적합
캐싱 시스템, 중복 제거, 빠른 조회가 필요한 인덱싱, 메모리 민감한 메타데이터 관리에 활용됩니다.
일관된 해싱(Consistent Hashing)의 원리와 분산 캐시 시스템에서 노드 추가/제거 시 재배치를 최소화하는 방법을 설명해주세요.
Q. 권한 관리 시스템에서 비트마스크를 활용해 사용자 권한(읽기, 쓰기, 삭제, 실행 등)을 효율적으로 저장하고 검사하는 방법을 설명하고, JavaScript의 비트 연산자(&, |, ^, ~, <<, >>)를 활용한 구현 전략을 제시해주세요. 또한 비트 연산을 사용한 알고리즘 최적화 사례(짝수/홀수 판별, 2의 거듭제곱 확인, 두 수 교환 등)와, JavaScript에서 32비트 정수 제한과 BigInt 사용 시 주의점도 설명해주세요.
각 비트를 플래그로 사용하면 공간 효율성과 연산 속도를 동시에 얻을 수 있습니다.
비트마스크는 각 비트를 boolean 플래그로 사용해 하나의 정수에 여러 권한을 저장합니다. OR(|)로 권한 추가, AND(&)로 권한 확인, XOR(^)로 토글, AND NOT(&~)로 제거합니다. 짝수 판별은 n&1===0, 2의 거듭제곱은 n&(n-1)===0, XOR 교환은 a^=b; b^=a; a^=b로 구현합니다. JavaScript는 비트 연산 시 32비트 signed integer로 변환하므로 큰 수는 >>> 0로 unsigned 처리하거나 BigInt를 사용하되, BigInt는 비트 연산이 느리고 JSON 직렬화가 안 됩니다. 실무에서는 가독성과 성능을 균형있게 고려해야 합니다.
- • 비트마스크는 공간 효율적이고 O(1) 연산 가능
- • OR/AND/XOR/NOT 조합으로 플래그 조작
- • JavaScript는 32비트 제한, BigInt는 성능 트레이드오프 존재
- • 실무에서는 가독성 위해 상수와 주석 필수
권한 시스템, 기능 플래그, 압축 알고리즘, 네트워크 프로토콜, 그래픽 처리에서 비트 연산이 필수적입니다.
Bloom Filter의 동작 원리와 여러 해시 함수를 비트 배열에 매핑해 membership test를 수행하는 방법을 설명해주세요.
Q. 대용량 배열에서 K번째로 큰 요소를 찾는 문제를 해결하기 위한 여러 접근법(정렬, Heap, Quick Select)의 시간 복잡도를 비교하고, Quick Select 알고리즘의 동작 원리와 평균/최악의 경우 성능을 설명해주세요. 또한 분할 정복 기법을 활용한 병렬 처리 전략과, JavaScript에서 대용량 데이터를 청크 단위로 나누어 처리할 때 Worker Thread를 활용한 병렬화 방안을 제시해주세요. 추가로 Median of Medians 알고리즘으로 최악의 경우를 O(n)으로 보장하는 방법도 설명해주세요.
Quick Select는 Quick Sort의 파티션 아이디어를 사용하지만 한쪽만 재귀하는 차이가 있습니다.
정렬은 O(nlogn), Min Heap은 O(nlogK), Quick Select는 평균 O(n)입니다. Quick Select는 pivot으로 파티션 후 K가 있는 쪽만 재귀하여 평균적으로 절반씩 줄어듭니다. 최악의 경우 O(n^2)이지만 랜덤 pivot이나 Median of Medians로 O(n)을 보장합니다. Median of Medians는 5개씩 그룹화해 각 중앙값의 중앙값을 pivot으로 선택합니다. 분할 정복은 데이터를 독립적인 청크로 나누어 Worker Thread에서 병렬 처리 후 결과를 병합합니다. SharedArrayBuffer로 메모리 공유하고 Atomics로 동기화하거나, 메시지 패싱으로 결과를 수집합니다. 실무에서는 오버헤드를 고려해 충분히 큰 데이터에만 병렬화를 적용합니다.
- • Quick Select는 평균 O(n)으로 K번째 요소 탐색 최적화
- • Median of Medians로 최악의 경우 O(n) 보장
- • 분할 정복은 독립적 부분 문제로 나누어 병렬 처리 가능
- • Worker Thread 병렬화는 오버헤드 고려 필요
대용량 로그 분석, 통계 계산, 추천 시스템의 Top-K 아이템 선정, 실시간 순위 집계에 활용됩니다.
MapReduce 패러다임을 JavaScript로 구현할 때 Map 단계와 Reduce 단계의 데이터 흐름과 중간 결과 집계 전략을 설명해주세요.
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!