Vue.js 미드레벨 코딩·알고리즘 면접

두 개의 스택(backStack, forwardStack)을 사용하여 구현합니다. 새 페이지 방문 시 현재 페이지를 backStack에 push하고 forwardStack을 비웁니다. 뒤로가기 시 backStack에서 pop하여 현재 페이지로 설정하고, 이전 현재 페이지는 forwardStack에 push합니다. 앞으로가기는 반대로 forwardStack에서 pop하여 현재 페이지로 설정하고, 이전 현재 페이지는 backStack에 push합니다. 모든 연산은 스택의 push/pop만 사용하므로 O(1) 시간 복잡도를 가집니다. Vue의 반응성 시스템과 함께 사용할 때는 배열 대신 ref로 감싼 배열을 사용하여 UI가 자동으로 업데이트되도록 합니다.

Min Heap을 사용하여 크기 K로 제한하는 방식이 효율적입니다. 배열을 순회하면서 힙의 크기가 K 미만이면 요소를 추가하고, K에 도달한 후에는 현재 요소가 힙의 최소값보다 크면 최소값을 제거하고 현재 요소를 추가합니다. 전체 정렬은 O(N log N) 시간 복잡도를 가지지만, Min Heap 방식은 O(N log K) 시간 복잡도를 가집니다. K가 N보다 훨씬 작을 때 큰 성능 이점이 있습니다. 공간 복잡도는 O(K)로 전체 배열을 복사하지 않아도 됩니다. JavaScript에서는 힙을 직접 구현하거나 우선순위 큐 라이브러리를 사용할 수 있으며, Vue의 computed 속성으로 감싸 반응형으로 만들 수 있습니다.

Levenshtein Distance는 두 문자열을 같게 만들기 위해 필요한 최소 편집 연산(삽입, 삭제, 치환) 횟수를 계산합니다. 동적 프로그래밍을 사용하여 O(m*n) 시간 복잡도로 계산할 수 있으며, 공간 복잡도는 O(min(m,n))로 최적화 가능합니다. 대량 데이터에 적용 시 성능 개선 방법으로는 첫째, 문자열 길이 차이가 임계값을 초과하면 조기 종료, 둘째, N-gram 인덱싱으로 후보군을 먼저 필터링, 셋째, BK-Tree 같은 메트릭 트리 구조 활용, 넷째, Web Worker로 병렬 처리 등이 있습니다. Vue 컴포넌트에서는 debounce를 적용하여 입력마다 계산하지 않고, computed 속성으로 캐싱하여 불필요한 재계산을 방지할 수 있습니다.

DFS는 스택(또는 재귀)을 사용하여 한 경로를 끝까지 탐색한 후 백트래킹하며, 메모리 효율적이고 경로 추적이 쉽습니다. BFS는 큐를 사용하여 레벨 단위로 탐색하며, 최단 경로를 보장합니다. 하위 직원 찾기는 DFS가 적합하며 O(V+E) 시간 복잡도로 모든 노드를 방문합니다. 두 직원 간 최단 경로는 BFS를 사용하여 첫 번째로 도달한 경로가 최단 경로임을 보장합니다. 순환 참조 처리를 위해 Set이나 Map으로 방문한 노드를 추적하고, 방문 전 체크하여 무한 루프를 방지합니다. Vue에서 구현 시 reactive Set을 사용하여 방문 상태를 UI에 반영할 수 있고, 대규모 조직도는 가상 스크롤과 지연 로딩을 결합하여 성능을 최적화합니다.

완전 탐색(Brute Force)은 모든 조합을 확인하여 O(2^n) 시간 복잡도를 가지며 상품 수가 20개만 넘어도 비현실적입니다. 동적 프로그래밍은 하위 문제의 최적해를 저장하여 O(n*W) 시간 복잡도로 개선하며, 여기서 W는 목표 금액입니다. 2차원 배열로 dp[i][w]를 '첫 i개 상품으로 금액 w를 만드는 최적해'로 정의합니다. 실무 최적화 전략으로는 첫째, 금액을 100원 단위로 정규화하여 W를 줄이기, 둘째, 상품 수가 많으면 가격 대비 가치가 높은 상위 N개만 선택하는 그리디 근사, 셋째, Web Worker로 계산을 백그라운드 처리, 넷째, 결과를 캐싱하여 동일 조건 재요청 시 즉시 반환 등이 있습니다. Vue에서는 computed와 useMemo 패턴으로 불필요한 재계산을 방지합니다.