C# 미드레벨 코딩·알고리즘 기술면접
새 면접Q. 대용량 로그 파일(10GB)에서 특정 키워드가 포함된 라인을 찾아 반환해야 합니다. 메모리 제약(2GB)이 있는 상황에서 어떤 접근법을 사용하시겠습니까? 시간 복잡도와 공간 복잡도를 함께 설명해주세요.
파일 전체를 메모리에 올리지 않고 처리하는 방법을 고려해보세요.
StreamReader를 사용해 파일을 청크 단위로 읽으면서 각 라인을 순차적으로 검사하는 스트리밍 방식을 사용합니다. ReadLine()으로 한 줄씩 읽어 키워드 검사 후 매칭되는 라인만 결과 컬렉션에 추가합니다. 시간 복잡도는 O(n)이며 n은 전체 라인 수입니다. 공간 복잡도는 O(m)으로 m은 매칭된 라인 수이며, 한 번에 메모리에 로드되는 것은 현재 라인 하나뿐입니다. 필요시 병렬 처리를 위해 파일을 여러 세그먼트로 나누어 Parallel.ForEach로 처리할 수 있습니다.
- • StreamReader를 활용한 스트리밍 처리
- • 시간 복잡도 O(n), 공간 복잡도 O(m) 분석
- • 병렬 처리 가능성 언급
로그 분석 시스템에서 대용량 로그 파일을 실시간으로 검색할 때 사용됩니다.
만약 같은 파일을 여러 번 검색해야 한다면 성능을 어떻게 개선하시겠습니까?
Q. 사용자 세션 정보를 저장하는데, 최근 접속한 1000명의 사용자만 유지하고 나머지는 자동으로 제거되어야 합니다. 어떤 자료구조를 선택하고 어떻게 구현하시겠습니까? 각 연산의 시간 복잡도도 설명해주세요.
삽입 순서를 추적하면서 빠른 조회와 삭제가 가능한 자료구조를 생각해보세요.
LinkedList와 Dictionary를 조합한 LRU(Least Recently Used) 캐시 구조를 사용합니다. Dictionary는 사용자 ID를 키로 LinkedListNode를 값으로 저장하여 O(1) 조회를 제공하고, LinkedList는 접속 순서를 유지합니다. 새 사용자 접속 시 LinkedList의 끝에 추가하고 Dictionary에 매핑하며, 1000명 초과 시 LinkedList의 첫 노드(가장 오래된)를 제거합니다. 모든 주요 연산(조회, 삽입, 삭제)이 O(1) 시간 복잡도를 가집니다. .NET의 OrderedDictionary나 직접 구현한 LRUCache 클래스를 활용할 수 있습니다.
- • LinkedList와 Dictionary 조합으로 LRU 캐시 구현
- • 모든 주요 연산 O(1) 시간 복잡도 달성
- • 삽입 순서 유지와 빠른 조회 동시 해결
웹 애플리케이션에서 활성 사용자 세션 관리나 캐싱 시스템 구현에 사용됩니다.
동시성 환경에서 여러 스레드가 이 자료구조에 접근한다면 어떻게 처리하시겠습니까?
Q. 거의 정렬된 상태의 배열(각 요소가 최종 위치에서 최대 k칸 떨어진 상태)을 정렬해야 합니다. 일반적인 QuickSort 대신 더 효율적인 알고리즘이 있다면 무엇이며, 그 이유와 시간 복잡도를 설명해주세요.
k개의 요소만 고려하면 되는 상황에서 효과적인 자료구조를 생각해보세요.
최소 힙(Min Heap)을 사용한 삽입 정렬 변형이 효율적입니다. 크기 k+1인 힙을 유지하면서 배열을 순회합니다. 처음 k+1개 요소로 힙을 구성한 후, 힙에서 최소값을 추출해 결과 배열에 넣고 다음 요소를 힙에 추가하는 과정을 반복합니다. 시간 복잡도는 O(n log k)로, 일반 정렬의 O(n log n)보다 k가 n보다 충분히 작을 때 효율적입니다. C#에서는 PriorityQueue 클래스나 SortedSet을 활용할 수 있습니다. 이 방법은 각 요소가 최대 k칸 떨어져 있다는 제약을 활용합니다.
- • 최소 힙을 활용한 O(n log k) 알고리즘
- • 거의 정렬된 상태의 특성 활용
- • 일반 정렬보다 효율적인 시간 복잡도
실시간 데이터 스트림에서 타임스탬프 기준으로 거의 정렬된 이벤트를 정렬할 때 사용됩니다.
k값을 모르는 상황이라면 어떻게 접근하시겠습니까?
Q. 문자열 배열에서 공통 접두사(prefix)가 가장 긴 그룹을 찾아야 합니다. 예를 들어 [apple, application, apply, banana, band]에서 [apple, application, apply] 그룹을 찾는 것입니다. 효율적인 알고리즘 접근법과 시간/공간 복잡도를 설명해주세요.
문자열을 계층적으로 구조화할 수 있는 자료구조를 고려해보세요.
Trie(접두사 트리) 자료구조를 사용하는 것이 가장 효율적입니다. 모든 문자열을 Trie에 삽입하면서 각 노드에 해당 접두사를 공유하는 문자열 개수를 기록합니다. Trie를 DFS로 순회하면서 각 노드의 카운트를 확인해 최대 그룹을 찾습니다. 시간 복잡도는 O(n*m)이며 n은 문자열 개수, m은 평균 문자열 길이입니다. 공간 복잡도는 O(n*m)으로 Trie 노드 저장에 사용됩니다. 대안으로 문자열을 정렬 후 인접한 문자열끼리 비교하는 방법도 있으나 O(n*m log n)으로 더 느립니다.
- • Trie 자료구조를 활용한 접두사 그룹화
- • 시간 복잡도 O(n*m), 공간 복잡도 O(n*m)
- • DFS 순회로 최대 그룹 탐색
자동완성 기능이나 URL 라우팅 시스템에서 유사 패턴 그룹화에 사용됩니다.
메모리 제약이 심한 환경이라면 Trie 대신 어떤 접근법을 사용하시겠습니까?
Q. 계단을 오르는데 한 번에 1칸, 2칸, 또는 3칸을 오를 수 있습니다. n칸 계단을 오르는 방법의 수를 구하는 함수를 설계할 때, 재귀 방식과 동적계획법 방식의 시간/공간 복잡도를 비교하고 어떤 방식을 선택할지 설명해주세요.
중복 계산이 발생하는지, 그것을 어떻게 제거할 수 있는지 생각해보세요.
순수 재귀 방식은 f(n) = f(n-1) + f(n-2) + f(n-3)로 구현되며 시간 복잡도가 O(3^n)으로 지수적으로 증가합니다. 메모이제이션을 적용한 Top-down DP는 Dictionary로 계산 결과를 캐싱하여 O(n) 시간, O(n) 공간 복잡도를 가집니다. Bottom-up DP는 배열로 f(1)부터 f(n)까지 순차 계산하며 O(n) 시간, O(n) 공간입니다. 최적화된 Bottom-up은 최근 3개 값만 유지하여 O(n) 시간, O(1) 공간으로 개선 가능합니다. 실무에서는 가독성과 성능을 고려해 메모이제이션 방식을 주로 선택합니다.
- • 순수 재귀 O(3^n) vs DP O(n) 시간 복잡도 비교
- • 메모이제이션으로 중복 계산 제거
- • 공간 최적화로 O(1) 공간 복잡도 달성 가능
게임에서 경로 탐색 경우의 수 계산이나 조합 최적화 문제에 사용됩니다.
n이 매우 큰 경우(예: 10^9) 어떻게 처리하시겠습니까?
Q. 정렬된 배열에서 특정 값이 처음 나타나는 인덱스와 마지막 나타나는 인덱스를 찾아야 합니다. 배열에 중복 값이 많은 상황에서 가장 효율적인 알고리즘과 시간 복잡도를 설명해주세요.
정렬된 배열의 특성을 활용할 수 있는 검색 알고리즘을 고려해보세요.
이진 탐색(Binary Search)을 두 번 수행하는 방식이 가장 효율적입니다. 첫 번째 이진 탐색은 목표 값을 찾았을 때 왼쪽으로 계속 탐색하여 첫 번째 인덱스를 찾고, 두 번째 이진 탐색은 오른쪽으로 탐색하여 마지막 인덱스를 찾습니다. 각 이진 탐색의 시간 복잡도는 O(log n)이므로 전체 시간 복잡도는 O(log n)입니다. 선형 탐색은 O(n)이므로 중복이 많을수록 이진 탐색이 훨씬 효율적입니다. C#에서는 Array.BinarySearch를 활용하거나 직접 구현할 수 있습니다.
- • 이진 탐색을 두 번 수행하여 범위 탐색
- • 시간 복잡도 O(log n) 달성
- • 정렬된 배열의 특성 활용
데이터베이스 인덱스 범위 쿼리나 시계열 데이터에서 특정 기간 검색에 사용됩니다.
배열이 정렬되어 있지 않다면 어떻게 접근하시겠습니까?
Q. List에서 중복을 제거하는 작업을 수행할 때, Distinct() 메서드 대신 더 효율적인 방법이 있다면 무엇이며, 각 방법의 시간/공간 복잡도를 비교 설명해주세요.
해시 기반 자료구조의 특성을 생각해보세요.
HashSet을 사용하는 방법이 가장 효율적입니다. new HashSet<T>(list)로 변환하면 O(n) 시간에 중복이 제거되며, HashSet의 내부 해시 테이블 특성상 각 요소 추가가 평균 O(1)입니다. Distinct()는 내부적으로 Set을 사용하지만 IEnumerable을 반환하므로 ToList() 호출이 추가로 필요합니다. 공간 복잡도는 둘 다 O(n)이지만 HashSet이 직접 변환하면 중간 컬렉션 생성을 피할 수 있습니다. 순서 유지가 필요하면 LinkedHashSet 패턴이나 인덱스를 함께 저장하는 방식을 고려해야 합니다.
- • HashSet을 활용한 O(n) 중복 제거
- • Distinct()와 HashSet 변환의 성능 비교
- • 순서 유지 필요성에 따른 선택
사용자 입력 데이터 정제나 데이터 파이프라인에서 중복 레코드 제거에 사용됩니다.
대용량 데이터에서 메모리가 부족한 상황이라면 어떻게 처리하시겠습니까?
Q. 조직도에서 두 직원 간의 최단 보고 경로를 찾아야 합니다. 조직 구조가 트리가 아닌 일반 그래프 형태일 때(매트릭스 조직 등) 어떤 알고리즘을 사용하고 시간 복잡도는 어떻게 되는지 설명해주세요.
가중치가 없는 그래프에서 최단 경로를 찾는 기본 알고리즘을 생각해보세요.
BFS(너비 우선 탐색) 알고리즘이 가장 적합합니다. 시작 직원을 큐에 넣고 레벨별로 탐색하면서 목표 직원을 찾으면 최단 경로가 보장됩니다. 시간 복잡도는 O(V+E)이며 V는 직원 수, E는 보고 관계 수입니다. 공간 복잡도는 O(V)로 방문 체크와 큐에 사용됩니다. 경로를 역추적하기 위해 각 노드의 부모를 Dictionary에 저장합니다. DFS는 최단 경로를 보장하지 않으므로 부적합하며, Dijkstra는 가중치가 없는 경우 BFS와 동일하므로 불필요한 오버헤드입니다.
- • BFS를 활용한 최단 경로 탐색
- • 시간 복잡도 O(V+E), 공간 복잡도 O(V)
- • DFS와 Dijkstra 대비 BFS 선택 이유
소셜 네트워크에서 연결 관계 찾기나 조직 내 커뮤니케이션 경로 분석에 사용됩니다.
보고 관계에 가중치(예: 협업 빈도)가 있다면 어떤 알고리즘을 사용하시겠습니까?
Q. LINQ 쿼리를 작성할 때 Where().Select()와 Select().Where()의 성능 차이가 있습니까? 있다면 어떤 경우에 어떤 순서를 선택해야 하며, 그 이유를 설명해주세요.
각 단계에서 처리되는 데이터의 양을 생각해보세요.
Where().Select() 순서가 대부분의 경우 더 효율적입니다. Where()로 먼저 필터링하면 Select()에서 처리할 데이터 양이 줄어들어 불필요한 변환 작업을 피할 수 있습니다. 예를 들어 1000개 중 10개만 필터링된다면 Select()는 10번만 실행됩니다. 반대로 Select().Where()는 1000번의 변환 후 필터링하므로 비효율적입니다. 단, Select()가 매우 가벼운 프로젝션이고 Where() 조건이 변환된 데이터에 의존한다면 Select().Where()가 필요합니다. LINQ는 지연 실행되므로 최종적으로 ToList()나 Count() 등이 호출될 때 실행됩니다.
- • Where()를 먼저 수행하여 처리 데이터 양 감소
- • Select() 변환 비용과 필터링 비율 고려
- • LINQ 지연 실행 특성 이해
대용량 데이터 처리 파이프라인에서 쿼리 최적화로 처리 시간을 단축할 때 사용됩니다.
데이터베이스 쿼리로 변환되는 LINQ to SQL에서는 순서가 차이가 있습니까?
Q. 실시간 스트리밍 데이터에서 최근 1분간의 평균값을 계산하는 시스템을 설계해야 합니다. 초당 수천 건의 데이터가 들어오는 상황에서 효율적인 자료구조와 알고리즘을 제안하고 시간/공간 복잡도를 설명해주세요.
시간 윈도우를 관리하면서 빠른 삽입과 삭제가 가능한 구조를 고려해보세요.
슬라이딩 윈도우 방식으로 Queue와 누적 합계를 조합하여 구현합니다. 각 데이터를 (값, 타임스탬프) 쌍으로 Queue에 추가하고 누적 합계를 유지합니다. 평균 계산 시 현재 시간에서 1분 이전 데이터를 Queue에서 제거하면서 합계를 업데이트합니다. 삽입은 O(1), 평균 계산은 O(k)이며 k는 1분간 누적된 데이터 수입니다. 공간 복잡도는 O(k)입니다. 더 최적화하려면 데이터를 초 단위로 버킷팅하여 60개 버킷의 순환 배열로 관리하면 평균 계산이 O(60) = O(1)로 개선됩니다. ConcurrentQueue를 사용하면 멀티스레드 환경에서 안전합니다.
- • 슬라이딩 윈도우와 Queue를 활용한 시계열 데이터 관리
- • 버킷팅으로 O(1) 평균 계산 최적화
- • ConcurrentQueue로 동시성 처리
모니터링 시스템에서 실시간 메트릭 계산이나 IoT 센서 데이터 집계에 사용됩니다.
평균뿐만 아니라 중앙값도 계산해야 한다면 어떻게 설계하시겠습니까?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!