[면접준비] 자료구조 면접대비!! 1탄

안녕하세요

 

제가 요즘 면접 준비하고 있어서 

자료구조 관련 면접 질문 대비를 해보려구 합니다!

 

 

1. 시간 복잡도 란?

시간복잡도는 이 알고리즘이 결과를 도출하는데 얼마나의 시간이 걸리는 지에 대한 값

 

2. 공간 복잡도 란?

공간복잡도는 이 알고리즘이 결과를 도출하는데 얼마나의 공간이 필요한 지에 대한 값

 

3. 연결리스트에 대해서 설명하기

{

연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조 입니다.

삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸립니다

 

연결 리스트에는 3종류가 있는대

1. 싱글 연결 리스트 : 다음 노드의 주소만 가지고 있다

2. 이중 연결 리스트 : 다음 노드와 이전 노드의 주소를 가지고 있고 가장 첫번째 노드의 이전 주소값은 null  마지막 노드의 다음 주소값은 null 로 표시한다

3. 원형 이중 연결 리스트  : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말합니다

 

}

 

 

4. 배열에 대해 설명하시오!

{

 

배열(array)은 같은 타입의 변수들로 이루어져 있고 크기가 정해져 있으며 , 인접한 메모리 위치에 있는 데이터를 모아놓은 집합 

중복을 허용하고 순서가 있다

 

 배열은 인덱스를 알고 있다면 탐색 시간복잡도가 O(1)이다 그리고 삽입 삭제는 O(n) 이 소요됩니다                             

 그래서 추가와 삭제를 많이 하는 것은 연결 리스트 , 탐색을 많이 하는 것은 배열로 하는것이 훨씬 효율적이다.              

 

벡터란 무엇인가?

벡터(vector)는 동적으로 요소를 할당할 수 있는 동적 배열 입니다 컴파일 시점에 개수를 모른다면 벡터를 써야합니다 또한 중복을 허용하고 순서가 있고 랜덤 접근이 가능합니다 탐색과 맨뒤의 요소를 삭제하거나 삽입하는데 O(1)이 걸리고 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n)의 시간이 걸린다

}

 

 

5. 스택에 대해 설명하시오

 

스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(Last In First Out)을 가진 자료 구조 입니다

재귀적인 함수 , 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰입니다 . 삽입 및 삭제에 O(1) , 탐색에 O(n)이 걸립니다

 

 

6 큐에 대해 설명하시오

 

큐는 먼저 집어넣은 데이터가 먼저 나오는 성질(First In First Out)을 지닌 자료구조 입니다

삽입 삭제는 O(1) 탐색은 O(n)이 걸립니다

큐는 CPU 작업을 기다리는 프로세스 , 스레드 행렬 또는 네트워크 접속을 기다리는 행렬 , 너비 우선 탐색 , 캐시 등에 사용됩니다!

 

7. 그래프에 대해서 설명하시오

그래프는 정점과 간선으로 이루어진 자료 구조입니다

 

간선에는 두 종류가 있는대 

단방향 간선과 양방향 간선이 있습니다

단방향 간선 그래프 , 양방향 간선 그래프에 따라서 그래프를 이용한 자료 구조 구현 하는 방법이 달라지게 됩니다!

단방향 그래프

양방향 그래프

가중치 : 가중치는 간선과 정점 사이에 드는 비용을 뜻합니다

 

 

8. 트리에 대해서 설명하시오

 

트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고 , 트리 구조로 배열된 일종의 계층적 데이터의 집합입니다.

루트 노드 , 내부 노드 , 리프 노드 등으로 구성됩니다

 

간선의 수는 V-1=E 즉 전체 노드갯수 -1 입니다 

 

이진트리 

이진 트리는 자식의 노드 수가 두 개 이하인 트리를 의미합니다

 

정이진 트리(full binary tree)

자식의 노드가 0 또는 2개인 이진 트리를 의미합니다

 

---

 

완전 이진 트리(complete binary tree)

왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며. , 마지막 레벨의 경우 왼쪽부터 채워져있습니다

 

---

변질 이진트리(dagenerate binarty tree) 

자식 노드가 하나밖에 없는 이진 트리를 의미합니다

---

포화 이진 트리(perfect binary tree)

모든 노드가 꽉 차 있는 이진 트리를 의미합니다

---

균형 이진 트리(balanced binary tree)

왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미합니다 map,set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나 입니다

 

 

---

이진 탐색 트리

이진 탐색 트리는 노드의 오른쪽 하위 트리에는 노드 값 보다 큰 값이 있는 노드만 포함되고 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말합니다

보통 O(logn)의 탐색 시간 복잡도가 걸리지만 최악의 경우 O(n)이 걸립니다

 

시간복잡도가 O(logn) ~O(n) 이 걸리는 이유는 

이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 때문입니다

최악의 경우 이진 탐색 트리의 모습입니다

 

 

위의 완전 이진 탐색 트리 처럼 삽입 순서에 따라 선형적인 모습을 띄울 수 있습니다 이런 경우 O(n)이 걸립니다

---