혹시 코딩테스트를 원한다면... 이쪽은 어떠신가요? 제껍니다...
- Big-O, Big-Theta, Big-Omega 에 대해 설명해 주세요.
- 다른 것을 사용하지 않고, Big-O를 사용하는 이유가 있을까요?
- O(1)은 O(N^2) 보다 무조건적으로 빠른가요?
- 스택 2개로 큐를, 큐 2개로 스택을 만드는 방법과, 그 시간복잡도에 대해 설명해 주세요.
- 시간복잡도를 유지하면서, 배열로 스택과 큐를 구현할 수 있을까요?
- Prefix, Infix, Postfix 에 대해 설명하고, 이를 스택을 활용해서 계산/하는 방법에 대해 설명해 주세요.
- Deque는 어떻게 구현할 수 있을까요?
- (C++ 한정) Deque의 Random Access 시간복잡도는 O(1) 입니다. 이게 어떻게 가능한걸까요?
- 값이 주어졌을 때, 어떻게 하면 충돌이 최대한 적은 해시 함수를 설계할 수 있을까요?
- 해시값이 충돌했을 때, 어떤 방식으로 처리할 수 있을까요?
- 본인이 사용하는 언어에서는, 어떤 방식으로 해시 충돌을 처리하나요?
- Double Hashing 의 장점과 단점에 대해서 설명하고, 단점을 어떻게 해결할 수 있을지 설명해 주세요.
- Load Factor에 대해 설명해 주세요. 본인이 사용하는 언어에서의 해시 자료구조는 Load Factor에 관련한 정책이 어떻게 구성되어 있나요?
- 다른 자료구조와 비교하여, 해시 테이블은 멀티스레드 환경에서 심각한 수준의 Race Condition 문제에 빠질 위험이 있습니다. 성능 감소를 최소화 한 채로 해당 문제를 해결할 수 있는 방법을 설계해 보세요.
- 그래프와 트리의 차이가 무엇인가요?
- 이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?
- 이진탐색트리의 주요 연산에 대한 시간복잡도를 설명하고, 왜 그런 시간복잡도가 도출되는지 설명해 주세요.
- 이진탐색트리의 한계점에 대해 설명해주세요.
- 이진탐색트리의 값 삽입, 삭제 방법에 대해 설명하고, 어떤식으로 값을 삽입하면 편향이 발생할까요?
- 이진탐색트리와 동일한 로직을 사용하면, 삼진탐색트리도 정의할 수 있을까요? 안 된다면, 그 이유에 대해 설명해 주세요.
- 힙을 배열로 구현한다고 가정하면, 어떻게 값을 저장할 수 있을까요?
- 힙의 삽입, 삭제 방식에 대해 설명하고, 왜 이진탐색트리와 달리 편향이 발생하지 않는지 설명해 주세요.
- 힙 정렬의 시간복잡도는 어떻게 되나요? Stable 한가요?
- 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의 속도를 비교해 주세요.
- 값이 거의 정렬되어 있거나, 아예 정렬되어 있다면, 위 세 알고리즘의 성능 비교 결과는 달라질까요?
- 본인이 사용하고 있는 언어에선, 어떤 정렬 알고리즘을 사용하여 정렬 함수를 제공하고 있을까요?
- 정렬해야 하는 데이터는 50G 인데, 메모리가 4G라면, 어떤 방식으로 정렬을 진행할 수 있을까요?
- 각 방법에 대해, "두 정점이 연결되었는지" 확인하는 시간복잡도와 "한 정점에 연결된 모든 정점을 찾는" 시간복잡도, 그리고 공간복잡도를 비교해 주세요.
- 정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 방식으로 구현하는 것이 효율적일까요?
- 사이클이 없는 그래프는 모두 트리인가요? 그렇지 않다면, 예시를 들어주세요.
- 트리에서는 어떤 방식으로 최단거리를 구할 수 있을까요? (위 방법을 사용하지 않고)
- 다익스트라 알고리즘에서, 힙을 사용하지 않고 구현한다면 시간복잡도가 어떻게 변화할까요?
- 정점의 개수가 N개, 간선의 개수가 N^3 개라면, 어떤 알고리즘이 효율적일까요?
- A* 알고리즘에 대해 설명해 주세요. 이 알고리즘은 다익스트라와 비교해서 어떤 성능을 낼까요?
- 음수 간선이 있을 때와, 음수 사이클이 있을 때 각각 어떤 최단거리 알고리즘을 사용해야 하는지 설명해 주세요.
- 재귀 함수의 동작 과정을 Call Stack을 활용해서 설명해 주세요.
- 언어의 스펙에 따라, 재귀함수의 최적화를 진행해주는 경우가 있습니다. 어떤 경우에 재귀함수의 최적화가 가능하며, 이를 어떻게 최적화 할 수 있을지 설명해 주세요.
- Kruskal 알고리즘에서 사용하는 Union-Find 자료구조에 대해 설명해 주세요.
- Kruskal 과 Prim 중, 어떤 것이 더 빠를까요?
- Kruskal 과 Prim 알고리즘을 통해 얻어진 결과물은 무조건 트리인가요? 만약 그렇다면 증명해 주세요. 그렇지 않다면, 반례를 설명해 주세요.
- 배열의 길이를 알고 있다면, 조금 더 빠른 Thread Safe 한 연산을 만들 순 없을까요?
- 사용하고 있는 언어의 자료구조는 Thread Safe 한가요? 그렇지 않다면, Thread Safe 한 Wrapped Data Structure 를 제공하고 있나요?
- Lower Bound, Upper Bound 는 무엇이고, 이를 어떻게 구현할 수 있을까요?
- 이진탐색의 논리를 적용하여 삼진탐색을 작성한다고 가정한다면, 시간복잡도는 어떻게 변화할까요? (실제 존재하는 삼진탐색 알고리즘은 무시하세요!)
- 기존 이진탐색 로직에서 부등호의 범위가 바뀐다면, (ex. <= 라면 <로, <이라면 <= 로) 결과가 달라질까요?