10/17 면접 준비

---

CS 관련 지식

자료구조/알고리즘

1. 배열과 링크드 리스트의 차이

• 배열은 메모리상에 순서대로 데이터를 저장합니다. 반면 링크드 리스트는 다음 데이터의 위치에 대한 포인터를 가지고 있는 구조입니다.
• 배열은 데이터를 인덱스로 조회할 수 있기 때문에 인덱스 조회성능이 높고, 데이터가 메모리에 순서대로 저장되어 있기 때문에,
• 캐시의 지역성으로 인하여 비교적 빠르게 탐색을 수행할 수 있습니다.
• 링크드 리스트는 중간에 데이터를 삽입하거나 삭제하는 것이 용이하다는 장점이 있습니다.

2. List와 Set의 차이

• List는 중복된 데이터를 저장하고 순서를 유지하는 선형 자료구조이고,
• Set은 중복되지 않은 데이터를 저장할 수 있고, 일반적으로 순서를 유지하지 않는 선형 자료구조입니다.
• 단, Set에도 TreeSet과 같이 순서를 유지하는 Set이 있습니다.

3. Hash Function, HashTable에 대해

• 해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.
• 해시 함수에 의해 얻어지는 값을 해시 값 혹은 해시 코드라고 합니다.
• 보통 자료구조에 사용되며 매우 빠른 데이터 검색을 위해 사용합니다.
• 해시 테이블은 키와 밸류로 데이터를 저장하는 자료구조입니다.
• 해시 테이블은 데이터를 빠르게 검색할 수 있는 자료 구조입니다.
• 각각의 키에 해시함수를 적용하여 배열의 고유한 인덱스를 생성하고, 이 인덱스를 활용해 값을 저장하거나 검색하게 됩니다.

4. Stack, Queue에 대해

• 스택은 선형 자료구조의 일종으로 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)방식의 자료구조 입니다.
• 스택의 사용 예시로는 웹 브라우저의 방문기록(뒤로가기), 실행 취소(undo) 등이 있습니다.
• 큐는 선형 자료구조의 일종으로 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)방식의 자료구조 입니다.
• 큐의 사용 예시로는 프린터의 인쇄 대기, 콜센터 고객 대기 시간 등이 있습니다.

5. Heap, Priority Queue에 대해

• 힙은 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조입니다.
• 여러 값들 중에서 최대값이나 최소값을 빠르게 찾아낼 수 있도록 만들어졌습니다.
• 힙은 중복된 값을 허용하고, 반정렬 상태를 유지합니다.
• 우선순위 큐는 데이터가 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 처리됩니다.
• 이 우선 순위 큐는 앞서 말한 힙을 이용하여 구현됩니다.
• 특징으로는 모든 항목에는 우선 순위가 있고,
• 우선 순위가 높은 요소는 우선 순위가 낮은 요소보다 먼저 처리되며
• 두 우선 순위가 같으면 큐의 순서에 따라 처리됩니다.

6. Tree, Binary Tree, BST, AVL Tree에 대해

• 트리는 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다.
• 트리는 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있고,
• 트리 내에 또 다른 트리가 있는 재귀적 자료구조입니다.
• 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며, 모든 자식 노드는 하나의 부모 노드만 갖습니다.
• 이진 트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리입니다.
• 이진 탐색 트리는 이진 트리가 정렬되어 있는 형태를 의미합니다.
• 왼쪽 노드는 부모 노드보다 작아야하며, 오른쪽 노드는 부모 노드보다 커야합니다.
• AVL 트리는 스스로 균형을 잡는 이진 탐색 트리입니다.
• 이진 탐색 트리의 속성을 가지며
• 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1입니다.
• 만약 높이 차이가 1보다 커지게 되면 회전을 통해 균형을 잡아 높이 차이를 줄입니다.

7. BST의 최악의 경우의 예와 시간복잡도

• 이진 탐색 트리의 최악의 경우는 일렬로 연결된 노드들로 구성된 트리를 탐색하는 경우 입니다.
• 이런 경우에는 이진 탐색 트리의 장점을 활용할 수 없으며
• 탐색, 삽입, 삭제 등의 연산에서 선형 시간 복잡도를 가지게 됩니다.
• 따라서 최악의 경우, 시간 복잡도는 O(n)으로 선형적으로 증가하게 됩니다.
• 이러한 상황은 이진 탐색 트리를 사용하는 주요 목적인 O(logN) 보다 효율적이지 않습니다.
• 따라서 일관된 O(logN)을 보장하는 AVL 트리와 같은 알고리즘을 사용하는 것이 좋습니다.

8. 피보나치 수열을 코드로 구현하는 방법

• 피보나치 수열은 보통 재귀정도로 구현할 수 있지만, 중복된 연산이 계속해서 발생하게 됩니다.
• 이런 중복된 연산을 메모리 등에 저장해두고 해당 결과가 존재하지 않을 때만 연산을 수행하도록 하면 보다 빠른 동작을 구현할 수 있게됩니다.

9. DFS, BFS에 대해

• DFS는 깊이 우선 탐색으로 루트 노드에서 시작하여 최대한 깊게 내려간 다음 더 이상 탐색할 것이 없을 때 옆 노드의 시작으로 넘어가는 것을 의미합니다.
• DFS는 보통 스택 또는 재귀합수로 구현합니다.
• 모든 노드를방문하고자 하는 경우 이 방법을 사용할 수 있고,
• BFS에 비해 탐색 속도가 느립니다.
• BFS는 너비 우선 탐색으로 루트 노드에서 가장 가까운 점들부터 순차적으로 탐색합니다.
• 보통 큐를 사용해서 구현합니다.
• 주로 두 노드 사이의 최단 경로를 찾을 때 사용합니다.

10. 정렬, 탐색에 대해

• 정렬은 어떤 리스트를 순서대로 정리하는 것이고
• 탐색은 해당 리스트에서 특정 값을 찾는 것 입니다.
• 정렬 알고리즘으로는 선택 정렬, 삽입 정렬, 버블 정렬, 퀵 정렬 등이 있으며
• 탐색 알고리즘으로는 선형 탐색, 이진 탐색, 해시 탐색 등이 있습니다.