카테고리: CS 기초 > 자료구조 ← 면접 질문 목록으로 돌아가기
스택 2개로 큐 만들기
큐 2개로 스택 만들기
Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산/하는 방법에 대해 설명해 주세요.
Deque의 Random Access 시간복잡도는 O(1) 입니다. 이게 어떻게 가능한걸까요?
해시 자료구조에 대해 설명해 주세요.
값이 주어졌을 때, 어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요?
해시값이 충돌했을 때, 어떤 방식으로 처리할 수 있을까요?
Java, Python, JavaScript 등 주요 언어에서 어떤 방식으로 해시 충돌을 처리하나요?
Double Hashing 의 장점과 단점에 대해서 설명하고, 단점을 어떻게 해결할 수 있을지 설명해 주세요.
Load Factor에 대해 설명해 주세요. 주요 프로그래밍 언어(Java, Python 등)의 해시 자료구조는 Load Factor에 관련한 정책이 어떻게 구성되어 있나요?
다른 자료구조와 비교하여, 해시 테이블은 멀티스레드 환경에서 심각한 수준의 Race Condition 문제에 빠질 위험이 있습니다. 성능 감소를 최소화 한 채로 해당 문제를 해결할 수 있는 방법을 설계해 보세요.
트리와 이진트리, 이진탐색트리에 대해 설명해 주세요.
이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?
이진탐색트리의 주요 연산에 대한 시간복잡도를 설명하고, 왜 그런 시간복잡도가 도출되는지 설명해 주세요.
이진탐색트리의 한계점에 대해 설명해주세요.
이진탐색트리의 값 삽입, 삭제 방법에 대해 설명하고, 어떤식으로 값을 삽입하면 편향이 발생할까요?
이진탐색트리와 동일한 로직을 사용하면, 삼진탐색트리도 정의할 수 있을까요? 안 된다면, 그 이유에 대해 설명해 주세요.
힙에 대해 설명해 주세요.
힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?
힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.
힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?
BBST (Balanced Binary Search Tree) 와, 그 종류에 대해 설명해 주세요.
Red Black Tree는 어떻게 균형을 유지할 수 있을까요?
Red Black Tree의 주요 성질 4가지에 대해 설명해 주세요.
2-3-4 Tree, AVL Tree 등의 다른 BBST 가 있음에도, 왜 Red Black Tree가 많이 사용될까요?
정렬 알고리즘에 대해 설명해 주세요.
Quick Sort와 Merge Sort를 비교해 주세요.
Quick Sort에서 O(N^2)이 걸리는 예시를 들고, 이를 개선할 수 있는 방법에 대해 설명해 주세요.
Stable Sort가 무엇이고, 어떤 정렬 알고리즘이 Stable 한지 설명해 주세요.
Merge Sort를 재귀를 사용하지 않고 구현할 수 있을까요?
Radix Sort에 대해 설명해 주세요.
Bubble, Selection, Insertion Sort의 속도를 비교해 주세요.
값이 거의 정렬되어 있거나, 아예 정렬되어 있다면, 위 세 알고리즘의 성능 비교 결과는 달라질까요?
주요 언어(Java, Python, JavaScript 등)에서는 어떤 정렬 알고리즘을 사용하여 정렬 함수를 제공하고 있을까요?
정렬해야 하는 데이터는 50G 인데, 메모리가 4G라면, 어떤 방식으로 정렬을 진행할 수 있을까요?
그래프 자료구조에 대해 설명하고, 이를 구현할 수 있는 두 방법에 대해 설명해 주세요.
각 방법에 대해, "두 정점이 연결되었는지" 확인하는 시간복잡도와 "한 정점에 연결된 모든 정점을 찾는" 시간복잡도, 그리고 공간복잡도를 비교해 주세요.
정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 방식으로 구현하는 것이 효율적일까요?
사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.
그래프에서, 최단거리를 구하는 방법에 대해 설명해 주세요.
트리에서는 어떤 방식으로 최단거리를 구할 수 있을까요? (위 방법을 사용하지 않고)
다익스트라 알고리즘에서, 힙을 사용하지 않고 구현한다면 시간복잡도가 어떻게 변화할까요?
정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 알고리즘이 효율적일까요?
A* 알고리즘에 대해 설명해 주세요. 이 알고리즘은 다익스트라와 비교해서 어떤 성능을 낼까요?
음수 간선이 있을 때와, 음수 사이클이 있을 때 각각 어떤 최단거리 알고리즘을 사용해야 하는지 설명해 주세요.
재귀함수에 대해 설명해 주세요.
재귀 함수의 동작 과정을 Call Stack을 활용해서 설명해 주세요.
언어의 스펙에 따라, 재귀함수의 최적화를 진행해주는 경우가 있습니다. 어떤 경우에 재귀함수의 최적화가 가능하며, 이를 어떻게 최적화 할 수 있을지 설명해 주세요.
MST가 무엇이고, 어떻게 구할 수 있을지 설명해 주세요.
Kruskal 알고리즘에서 사용하는 Union-Find 자료구조에 대해 설명해 주세요.
Kruskal 과 Prim 중, 어떤 것이 더 빠를까요?
Kruskal 과 Prim 알고리즘을 통해 얻어진 결과물은 무조건 트리인가요? 만약 그렇다면 증명해 주세요. 그렇지 않다면, 반례를 설명해 주세요.
Thread Safe 한 자료구조가 있을까요? 없다면, 어떻게 Thread Safe 하게 구성할 수 있을까요?
배열의 길이를 알고 있다면, 조금 더 빠른 Thread Safe 한 연산을 만들 순 없을까요?
주요 프로그래밍 언어의 자료구조는 Thread Safe 한가요? 그렇지 않다면, Thread Safe 한 Wrapped Data Structure 를 제공하고 있나요?
문자열을 저장하고, 처리하는 주요 자료구조 및 알고리즘 (Trie, KMP, Rabin Karp 등) 에 대해 설명해 주세요.
이진탐색이 무엇인지 설명하고, 시간복잡도를 증명해 보세요.
Lower Bound, Upper Bound 는 무엇이고, 이를 어떻게 구현할 수 있을까요?
이진탐색의 논리를 적용하여 삼진탐색을 작성한다고 가정한다면, 시간복잡도는 어떻게 변화할까요? (실제 존재하는 삼진탐색 알고리즘은 무시하세요!)
기존 이진탐색 로직에서 부등호의 범위가 바뀐다면, 어떤 영향이 있을까요?
그리디 알고리즘과 동적 계획법을 비교해 주세요.
그렇다면, 어떤 경우에 각각의 기법을 사용할 수 있을까요?
동적 계획법으로 풀 수 있는 모든 문제는 재귀로 변환하여 풀 수 있나요?
B-Tree와 B+ Tree의 차이점과 각각의 사용 사례를 설명해주세요.
데이터베이스에서 B+ Tree를 인덱스 구조로 사용하는 이유는 무엇인가요?
LRU 캐시를 O(1) 시간복잡도로 구현하는 방법을 설명해주세요.
LRU와 LFU 캐시 교체 정책의 차이점과 구현 방법을 설명해주세요.
블룸 필터(Bloom Filter)의 원리와 사용 사례를 설명해주세요.
블룸 필터의 False Positive와 False Negative 중 어떤 것이 발생할 수 있고, 그 이유는 무엇인가요?
Skip List의 구조와 탐색 원리를 설명해주세요.