1.
Array는 어떤 자료구조인가요?
•
Array는 동일한 타입의 데이터를 연속된 메모리 공간에 순차적으로 저장하는 자료구조입니다. 인덱스를 통해 특정 요소에 빠르게 접근할 수 있어 검색 속도가 O(1)로 매우 빠릅니다. 하지만 배열의 크기가 고정되어 있어, 데이터의 삽입이나 삭제가 비효율적일 수 있습니다. 예를 들어, 배열 중간에 데이터를 삽입하려면 기존 데이터를 모두 이동시켜야 하기 때문에 시간 복잡도가 O(n)이 됩니다.
2.
Dynamic Array는 어떤 자료구조인가요?
•
Dynamic Array는 크기가 동적으로 변하는 배열입니다. 기존 배열의 크기를 초과하면 더 큰 배열을 새로 할당하고 데이터를 복사합니다. 이 과정에서 일시적인 오버헤드가 발생할 수 있지만, 일반적으로는 효율적으로 동작합니다. Python의 리스트가 대표적인 예시입니다.
3.
Linked List에 대해서 설명해 주세요.
•
Linked List는 노드로 구성된 자료구조로, 각 노드는 데이터와 다음 노드를 가리키는 포인터를 포함합니다. 메모리가 연속적으로 할당되지 않기 때문에 데이터의 삽입과 삭제가 O(1)로 매우 효율적입니다. 하지만 특정 요소에 접근하려면 처음부터 순차적으로 탐색해야 하기 때문에 검색 속도가 O(n)으로 느립니다.
4.
Array vs Linked list를 비교해서 설명해주세요.
•
Array:
◦
장점: 빠른 접근(O(1)), 메모리 효율적.
◦
단점: 크기가 고정되어 있어 삽입/삭제가 비효율적(O(n)).
•
Linked List:
◦
장점: 동적 크기, 삽입/삭제가 효율적(O(1)).
◦
단점: 검색 속도가 느림(O(n)), 포인터로 인한 메모리 오버헤드.