자료구조/알고리즘 신입 기술면접
새 면접Q. 스택(Stack)과 큐(Queue)의 차이점을 설명하고, 각각 어떤 실무 상황에서 사용되는지 예를 들어주세요.
데이터가 삽입되고 제거되는 순서에 주목해보세요.
스택은 LIFO(Last In First Out) 구조로 마지막에 들어간 데이터가 먼저 나오며, 큐는 FIFO(First In First Out) 구조로 먼저 들어간 데이터가 먼저 나옵니다. 스택은 함수 호출 스택, 브라우저의 뒤로가기 기능, 실행 취소(Undo) 기능에 사용됩니다. 큐는 프린터 작업 대기열, 메시지 큐, BFS 알고리즘 구현에 활용됩니다. 스택은 push/pop 연산을, 큐는 enqueue/dequeue 연산을 기본으로 합니다.
- • 스택은 LIFO, 큐는 FIFO 구조
- • 스택은 함수 호출/뒤로가기에 사용
- • 큐는 작업 대기열/메시지 처리에 사용
웹 서버에서 비동기 작업을 순서대로 처리하기 위해 메시지 큐를 사용합니다.
우선순위 큐(Priority Queue)는 일반 큐와 어떻게 다르며, 어떤 자료구조로 구현하나요?
Q. 이진 탐색 트리(Binary Search Tree)의 특징과 장점을 설명하고, 최악의 경우 성능이 저하되는 상황과 그 해결 방법을 설명해주세요.
트리가 한쪽으로 치우쳐진 형태가 되면 어떤 일이 발생할까요?
이진 탐색 트리는 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 값을 가지는 구조로, 평균적으로 O(log n)의 탐색, 삽입, 삭제 성능을 제공합니다. 하지만 데이터가 정렬된 순서로 삽입되면 트리가 한쪽으로 치우쳐져 연결 리스트처럼 되어 O(n)의 성능으로 저하됩니다. 이를 해결하기 위해 AVL 트리나 Red-Black 트리 같은 자가 균형 이진 탐색 트리를 사용하여 트리의 높이를 자동으로 균형있게 유지합니다. 실무에서는 데이터베이스 인덱스 구현에 B-Tree 계열의 균형 트리가 널리 사용됩니다.
- • 왼쪽 자식 < 부모 < 오른쪽 자식 규칙
- • 평균 O(log n), 최악 O(n) 성능
- • 자가 균형 트리로 최악의 경우 방지
데이터베이스 인덱스는 B-Tree 구조를 사용하여 빠른 데이터 검색을 제공합니다.
B-Tree가 이진 탐색 트리 대신 데이터베이스 인덱스에 사용되는 이유는 무엇인가요?
Q. 재귀 함수의 동작 원리를 설명하고, 재귀 대신 반복문을 사용해야 하는 경우와 그 이유를 설명해주세요.
함수 호출이 많아지면 메모리 측면에서 어떤 문제가 발생할 수 있을까요?
재귀 함수는 함수가 자기 자신을 호출하는 방식으로, 반드시 종료 조건(base case)과 재귀 호출 부분으로 구성됩니다. 재귀 호출마다 콜 스택에 함수 실행 컨텍스트가 쌓이므로, 재귀 깊이가 깊어지면 스택 오버플로우가 발생할 수 있습니다. 깊이가 매우 깊거나 성능이 중요한 경우에는 반복문으로 변환하여 스택 메모리 사용을 줄여야 합니다. 피보나치 수열처럼 중복 계산이 많은 경우 메모이제이션이나 동적 프로그래밍으로 최적화할 수 있습니다. 재귀는 트리 순회나 분할 정복 알고리즘처럼 문제를 자연스럽게 표현할 수 있을 때 유용합니다.
- • 재귀는 자기 자신을 호출하며 종료 조건 필수
- • 재귀 깊이가 깊으면 스택 오버플로우 위험
- • 성능 중요 시 반복문으로 변환 고려
파일 시스템의 디렉토리 구조를 탐색할 때 재귀 함수를 사용하여 모든 하위 폴더를 순회합니다.
꼬리 재귀 최적화(Tail Call Optimization)란 무엇이며, JavaScript에서는 어떻게 지원되나요?
아직 댓글이 없습니다. 첫 번째 댓글을 남겨보세요!