주니어 개발자 CS 기술 면접 예상 질문 - 자료구조

Q. Array와 LinkedList의 장점과 단점에 대해 시간 복잡도를 가지고 설명해주세요.

Array의 장점은 순차적으로 데이터를 저장할 수 있다는 것입니다. 데이터에 순서가 있으므로 index를 갖게 되며, index를 이용하여 자료의 탐색을 O(1)의 시간복잡도로 할 수 있습니다. 

반면 데이터가 순차적으로 존재하기 때문에 새로운 데이터를 삽입하거나 삭제하는 경우 그 뒤의 모든 데이터들을 한칸씩 움직여주어야 한다는 단점이 있습니다. 이 경우 O(N) 의 시간 복잡도를 가집니다. 

LinkedList의 경우 삽입과 삭제 연산에 O(1)의 시간복잡도를 가집니다. 반면, 탐색을 하는 경우 array 처럼 index를 이용하여 바로 접근할 수 없으며 선형 탐색을 해야 하므로 O(N)의 시간복잡도를 가집니다. 

Q. Stack 과 Queue를 실제 사용하는 예시와 동작방식에 대해 설명해주세요. 

Stack 

메모리에서 함수가 호출될 때 스택 영역에 호출된 함수의 수행을 마치고 복귀할 주소와 데이터를 저장한다. 예를 들어서 main()함수가 실행되고나서 main()함수 내에 func1 () 함수가 호출된다면, main()함수의 스택 프레임 위에 func1()함수의 스택 프레임이 쌓이게 된다. 그후 func1() 함수가 실행 후 종료되어 pop() 이 일어나고, main()함수가 실행된 후 종료되어 pop()이 일어난다. 

문서 작업에서 ctrl+z 를 쓰는 경우에도, 가장 나중에 수정한 내역부터 되돌린다. 

인터넷 웹 브라우저에서 뒤로 가기를 하는 경우에도 가장 나중에 방문했던 페이지로 되돌린다. 

Queue

컴퓨터 운영체제에서 프로세스를 스케줄링하기 위해서 사용된다. 가장 단순한 형태인 FCFS (First Come First Served) 의 경우 queue 가 작업을 처리하는 방식인 FIFO 방식으로 먼저 들어온 task 가 먼저 처리된다.  

Q. Heap 자료구조에 대해 설명해주세요. 

완전 이진 트리의 종류에 속하며, 최댓값 또는 최솟값을 빠르게 탐색할 수 있도록 만들어진 자료구조이다. 

반 정렬 상태로, 이진 트리와의 차이점은 힙은 중복된 값을 허용한다.  

Q. Heap 의 종류인 최대 힙과 최소 힙에 대해서 설명해주세요 

최대 힙은 부모 노드의 값이 자식 노드의 값보다 크거나 같은 이진 트리이며, 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작거나 같은 이진트리이다. 

Q. Binary Tree와 BST(이진탐색 트리)의 차이점에 대해 설명해주세요. 

이진 트리는 자식 노드가 최대 2개인 노드들로 구성된 트리이다.

반면에, 이진 탐색 트리 이진탐색과 연결리스트를 합하여 장점을 얻는 자료구조이다. 이진탐색트리의 경우 각 노드의 왼쪽 서브트리의 노드들은 부모노드보다 작고, 오른쪽 서브트리의 노드들은 부모노드보다 크다. 또한 중복된 노드가 없어야 한다. 

이진탐색은 탐색에 소요되는 시간 복잡도가 O(logN)

연결리스트는 삽입, 삭제의 시간 복잡도는 O(1)이며 탐색의 경우 O(N) 가 걸린다. 

Q. BST 에서 데이터(노드)를 검색할 때, 시간 복잡도가 최선인 경우와 최악의 경우에 각각 어떤지 설명해주세요. 

최선의 경우에 O(logN) 이 소요되며, 최악의 경우에는 편향된 트리로 노드 개수가 N 이라고 할 때 O(N) 이 소요된다. 

-> 삽입, 검색, 삭제 연산을 실행할 때 시간 복잡도는 트리의 Depth 에 비례한다. 

Q. Binary Tree에서 leaf node 까지 탐색하기 위해서 어떻게 하나요 ?

1. DFS, 깊이 우선 탐색 

루트 노드에서 시작하여 각 분기를 깊게 탐색하는 방법이다. 

전위 순회, 중위 순회, 후위 순회가 있다. 

전위 순회는 (Pre-order) 현재 노드를 방문하고 왼쪽 하위 트리를 방문한 후, 오른쪽 하위 트리를 방문한다. 

중위 순회 (In-order) 는 왼쪽 하위트리를 방문(중위 순회 한)후, 현재 노드를 방문하고, 오른쪽 하위 트리를 방문한다. 

후위 순회 (Post-order) 는 왼쪽 하위 트리를 순회하고, 오른쪽 하위트리를 순회한 후, 현재 노드를 방문한다. 

2. BFS, 너비 우선 탐색 

각 트리의 레벨을 순서대로 왼쪽에서 오른쪽으로 탐색하는 방법이다. 주로 queue를 사용하여 구현한다. 

루트 노드를 queue에 삽입하고, queue가 비어있지 않는 동안 계속 다음 작업을 반복한다. 
a. queue에서 노드를 하나 꺼내서 처리한다. 
b. 해당 노드의 왼쪽 자식 노드가 있으면 queue에 삽입한다. 
c. 해당 노드의 오른쪽 자식 노드가 있으면 queue에 삽입한다. 

Q. 이진 탐색 트리의 최악의 시간 복잡도인 경우에 대해 설명하고, 이를 해결하기 위한 자료구조에 대해 설명해주세요

이진 탐색 트리는 선형적으로 구성되는 경우 노드 개수가 N 개 일 때, 시간 복잡도가 O(N)이다. 

이를 해결하기 위한 방법으로 AVL 트리가 있다. AVL 트리는 스스로 균형을 잡는 이진 탐색 트리로, 삽입 삭제 연산이 일어날 때 균형을 맞추기 위해 트리를 왼쪽 또는 오른쪽으로 회전시킨다. AVL 트리는 삽입, 삭제, 탐색 연산의 시간 복잡도가 모두 O(logN)이다. 

Q. Hash Table 의 장점은 무엇인가요 ? 

적은 자원으로 많은 데이터를 효율적으로 관리하기 위해 사용합니다. 

무한한 데이터들을 유한한 개수의 해시 값으로 메핑하게 되면, 작은 메모리로 프로세스 관리를 할 수 있습니다. 

Q. Hash Table collision 을 해결하는 방법에 대해 설명해주세요. 

체이닝방식 : 연결리스트를 사용해서 collision 이 일어난 동일 값에 대해 연결리스트로 노드를 계속 추가해 나가는 방식이다. 

Open Addressing : 해시 함수로 얻은 주소가 아닌 다음주소에 저장하는 것을 허용하는 방식이다. 

Q. 그래프와 트리의 차이점에 대해 설명해주세요. 

그래프란, 정점(vertex)과 간선(edge)으로 이루어진 자료구조이다. 

트리는 그래프 자료구조의 유형 중 하나로, 정점과 간선으로 이루어져 있으며 계층적인 자료구조를 가지고 있다. 트리는 cycle을 이루지 않는다는 특징이 있다. 또한 노드의 수가 N개 이면, 간선은 N-1개를 가진다. 트리에서 루트에서 하나의 노드로 가는 경로는 유일한 한 경로뿐이다. 

Q. B Tree 자료구조의 특징에 대해 설명해주세요. 

이진트리를 확장해서, 하나의 노드가 더 많은 자식 노드를 가질 수 있게 하여 검색에 유리하도록 만든 자료구조이다. 

루트 노드는 적어도 2개 이상의 자식 노드를 가진다. 

데이터는 중복될 수 없다. 

루트 노드를 제외한 모든 노드는 적어도 M/2개 이상의 데이터를 가지고 있어야 한다. 

Q. B+Tree 와 B Tree 자료구조의 차이점에 대해 설명해주세요. 

B Tree는 탐색을 위해 모든 노드를 찾아서 이동해야 한다는 단점이 있었는데, B+Tree는 동일한 레벨의 노드들이 정렬되어 있고, 노드들이 연결리스트 형태로 이어져 있다. 

B+Tree는 각 노드에서 key 만 들어가고 data는 모두 leaf 노드에만 저장되어 있다. 따라서 삽입, 삭제 연산이 leaf 노드에서만 일어나게 된다. 따라서 탐색에 있어서 유리하다. 

leaf node 가 아닌 자료는 인덱스 노드, leaf node 자료는 데이터 노드라고 한다. 

 

 

주니어 개발자 CS 기술 면접 예상 질문 - 운영체제 (1)

주니어 개발자 CS 기술 면접 예상 질문 - 운영체제 (2)

주니어 개발자 CS 기술 면접 예상 질문 - 운영체제 (2)

주니어 개발자 CS 기술 면접 예상 질문 - 운영체제 (2)