1. 배열, 동적 배열, 연결 리스트

Q1. 배열, 동적 배열, 연결 리스트 각각의 특징과 장단점을 말해보세요.

 

A1.

배열:  

array

특징: 방의 개수 고정, 연속된 방

단점: 방을 추가/축소 불가

 

동적 배열: 

vector

특징: 사용할 방의 개수 유동적 계약, 연속된 방

장점: 유동적인 계약

단점: 이사 비용, 중간 삽입/삭제 느림

할당 정책: 이사할 때 사용할 방보다 많이 여유분을 두고 1.5~2배 예약해서 이사 횟수를 최소화

 

연결 리스트: 

list
특징: 연속되지 않은 방을 사용

장점: 중간 삽입/삭제

단점: N번째 방을 바로 찾을 수가 없음(임의 접근 Random Access 불가)

 

 

Q2. 선형과 비선형 자료구조의 차이에 대해 말해 보세요 

 

A2. 선형 vs 비선형

선형: 배열, 연결 리스트, 스택/큐 (자료를 순차적으로 나열한 형태)

비선형: 트리, 그래프 (하나의 자료 뒤에 다수의 자료가 올 수 있는 형태) 

 

 

Q3. 배열, 동적 배열, 연결 리스트의 표준 라이브러리 클래스가 C#, C++가 다른데 어떻게 다르나요? 

 

A3. 

각 언어별로 배열, 동적 배열, 연결 리스트에 해당하는 표준 라이브러리나 클래스를 아래와 같이 정리하겠습니다.

C#

C++