Java 시니어 코딩·알고리즘 면접
새 면접Q. 소셜 네트워크에서 두 사용자 간의 최단 친구 관계 경로를 찾아야 합니다. 수천만 명의 사용자와 수억 개의 친구 관계가 있는 환경에서 BFS, Bidirectional BFS, A* 알고리즘의 시간복잡도와 공간복잡도를 비교하고, 각 알고리즘이 유리한 상황을 설명해주세요. 또한 그래프가 메모리에 모두 적재되지 않는 경우 어떤 최적화 전략을 사용하시겠습니까?
양방향 탐색이 탐색 공간을 어떻게 줄이는지, 그리고 휴리스틱 함수의 역할을 생각해보세요.
BFS는 O(V+E) 시간복잡도로 최단 경로를 보장하지만, 탐색 공간이 지수적으로 증가합니다. Bidirectional BFS는 시작점과 도착점에서 동시에 탐색하여 탐색 공간을 O(b^(d/2))로 절반으로 줄여 실질적으로 큰 성능 향상을 제공합니다. A* 알고리즘은 휴리스틱 함수를 사용해 탐색 방향을 유도하지만, 소셜 그래프에서는 적절한 휴리스틱을 정의하기 어렵습니다. 메모리 제약 상황에서는 Iterative Deepening, 그래프 파티셔닝, 또는 외부 저장소(Redis, 그래프 DB)를 활용한 청크 단위 탐색을 고려해야 하며, Bloom Filter로 방문 노드를 근사적으로 관리하거나, 핫 데이터를 캐싱하는 전략이 유효합니다.
- • Bidirectional BFS가 탐색 공간을 제곱근 수준으로 감소시키는 원리
- • 소셜 그래프에서 A* 휴리스틱 함수 설계의 어려움
- • 메모리 제약 시 그래프 파티셔닝과 외부 저장소 활용 전략
- • Bloom Filter를 활용한 방문 노드 관리 최적화
LinkedIn의 '몇 단계 떨어진 연결' 기능이나 Facebook의 친구 추천 시스템에서 사용됩니다.
Six Degrees of Separation 특성을 활용하여 탐색 깊이를 제한하는 전략과, 유명인(high-degree node)을 경유하는 경로를 우선 탐색하는 최적화 방법을 설명해주세요.
Q. 주식 거래 시스템에서 최대 K번의 매수/매도를 통해 얻을 수 있는 최대 수익을 계산해야 합니다. K가 매우 크거나(예: K >= n/2, n은 일수), K가 작을 때의 접근법을 각각 설명하고, 시간복잡도와 공간복잡도를 분석해주세요. 또한 거래 수수료가 있는 경우와 쿨다운 기간(매도 후 하루 휴식)이 있는 경우 알고리즘을 어떻게 변형해야 하는지 설명해주세요.
K가 충분히 크면 제약이 없는 것과 같고, 작으면 상태 공간을 효율적으로 관리해야 합니다.
K가 n/2 이상이면 거래 횟수 제약이 실질적으로 없으므로 O(n) 시간에 그리디하게 모든 상승 구간에서 매매하면 됩니다. K가 작을 때는 3차원 DP(날짜, 거래 횟수, 보유 상태)로 O(nK) 시간, O(K) 공간에 해결할 수 있습니다. dp[i][k][0]은 i일에 k번 거래 완료하고 미보유 상태, dp[i][k][1]은 보유 상태를 의미하며, 상태 전이는 매수/매도/유지로 구성됩니다. 거래 수수료는 매도 시 수익에서 차감하고, 쿨다운은 상태에 '쿨다운 중' 상태를 추가하여 dp[i][k][cooldown]으로 확장하면 됩니다. 공간 최적화는 슬라이딩 윈도우로 O(K)까지 줄일 수 있습니다.
- • K >= n/2일 때 그리디 접근법으로 O(n) 해결
- • K가 작을 때 3차원 DP로 O(nK) 시간, O(K) 공간 최적화
- • 거래 수수료와 쿨다운 제약을 상태 전이에 반영하는 방법
- • 슬라이딩 윈도우를 통한 공간복잡도 최적화
알고리즘 트레이딩 시스템에서 포트폴리오 최적화와 거래 전략 백테스팅에 사용됩니다.
여러 종목의 주식을 동시에 거래할 수 있고, 각 종목마다 독립적인 거래 횟수 제한이 있는 경우 알고리즘을 어떻게 확장하시겠습니까?
Q. 대용량 로그 파일에서 정규표현식 패턴 매칭을 수행해야 합니다. NFA(Non-deterministic Finite Automaton)와 DFA(Deterministic Finite Automaton) 기반 정규표현식 엔진의 차이점을 설명하고, 백트래킹이 발생하는 원인과 ReDoS(Regular Expression Denial of Service) 공격의 원리를 설명해주세요. 또한 Java의 Pattern 클래스가 어떤 방식을 사용하는지, 그리고 대용량 텍스트에서 여러 정규표현식을 동시에 검사할 때 Aho-Corasick 알고리즘과의 성능 비교를 설명해주세요.
NFA는 백트래킹이 발생할 수 있고, DFA는 상태 폭발 문제가 있습니다. 각각의 트레이드오프를 고려하세요.
NFA 기반 엔진은 정규표현식을 직접 상태 머신으로 변환하여 O(mn) 시간복잡도를 가지며 백트래킹이 발생할 수 있습니다. 특히 (a+)+b 같은 중첩된 수량자에서 입력이 매칭되지 않으면 지수 시간복잡도로 악화되어 ReDoS 공격에 취약합니다. DFA 기반 엔진은 O(n) 시간에 매칭하지만 정규표현식을 DFA로 변환할 때 상태 수가 지수적으로 증가할 수 있습니다. Java의 Pattern은 NFA 기반이며 백트래킹을 사용하므로 복잡한 패턴에서 성능 문제가 발생할 수 있습니다. 여러 패턴을 동시에 검사할 때 Aho-Corasick은 O(n + m + z) (n: 텍스트 길이, m: 패턴 총 길이, z: 매칭 수)로 효율적이지만 고정 문자열 패턴만 지원하므로, 정규표현식이 필요하면 RE2나 Hyperscan 같은 DFA 기반 라이브러리를 고려해야 합니다.
- • NFA 백트래킹으로 인한 지수 시간복잡도와 ReDoS 공격 위험
- • DFA의 O(n) 매칭 보장과 상태 폭발 문제
- • Java Pattern의 NFA 기반 구현 특성
- • 다중 패턴 매칭 시 Aho-Corasick과 DFA 기반 엔진의 선택 기준
웹 방화벽(WAF)의 패턴 매칭, 로그 분석 시스템, 침입 탐지 시스템(IDS)에서 핵심 성능 요소입니다.
정규표현식 패턴을 컴파일 타임에 검증하여 ReDoS 취약점을 미리 탐지하는 방법과, Possessive Quantifier나 Atomic Group을 사용한 백트래킹 방지 기법을 설명해주세요.
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!