14번 질문: Array과 LinkedList를 비교설명해주세요.
답변
Array와 LinkedList는 모두 선형 자료구조이지만, 메모리 할당 방식, 데이터 접근/수정 속도, 삽입/삭제 효율성에서 차이가 있습니다.
메모리 할당
Array: 연속된 메모리 공간에 데이터 저장 (크기 고정).
LinkedList: 불연속적 메모리 공간에 노드가 포인터로 연결 (동적 크기 조절 가능).
접근 속도
Array: 인덱스를 통한 랜덤 접근이 가능해 O(1) 시간 복잡도.
LinkedList: 헤드부터 순차 탐색해야 하므로 O(n) 시간 복잡도.
삽입/삭제
Array: 중간에 삽입/삭제 시 요소 이동이 필요해 O(n) 시간 복잡도.
LinkedList: 포인터만 변경하면 되므로 O(1) (단, 위치 탐색 시간은 별도).
사용 사례
Array: 빠른 접근이 필요할 때 (예: 이미지 픽셀 처리).
LinkedList: 빈번한 삽입/삭제가 필요할 때 (예: 실시간 채팅 데이터).
Q1. LinkedList에서 삽입/삭제가 항상 O(1)인가요?
"위치를 이미 알고 있는 경우 O(1)이지만, 위치 탐색이 필요한 경우 O(n)입니다. 예를 들어 ‘중간에 삽입’하려면 탐색 시간이 추가됩니다."
Q3. Array의 크기를 동적으로 확장하는 방법은?
→ "Dynamic Array(예: JavaScript의 Array, Python의 List)는 초기 크기를 넘어서면 더 큰 메모리 공간을 할당하고 기존 데이터를 복사합니다. 이때 평균적으로 O(1)의 분할 상환 시간 복잡도를 가집니다."
2. Stack과 Queue 비교 설명
Stack과 Queue는 모두 데이터를 일시적으로 저장하는 선형 자료구조이지만, 데이터 처리 순서가 근본적으로 다릅니다.
동작 원리
Stack: LIFO (Last-In-First-Out). 마지막에 추가된 요소가 먼저 제거됩니다.
주요 연산: push() (추가), pop() (제거).
사용 예시: 함수 호출 스택, 브라우저 뒤로 가기.
Queue: FIFO (First-In-First-Out). 먼저 추가된 요소가 먼저 제거됩니다.
주요 연산: enqueue() (추가), dequeue() (제거).
사용 예시: 프린터 작업 대기열, BFS 알고리즘.
구현 방법
Stack: Array 또는 LinkedList로 간단히 구현 가능.
Queue: LinkedList 기반 구현이 효율적 (Array 사용 시 순환 큐로 최적화 필요).
Q3. Stack을 사용해 Queue를 구현할 수 있나요?
→ "두 개의 Stack을 사용해 가능합니다. 한 Stack은 입력 전용, 다른 Stack은 출력 전용으로 활용하며, 출력 Stack이 비었을 때 입력 Stack의 요소를 역순으로 이동시킵니다."
Q4. Priority Queue는 어떤 자료구조로 구현하나요?
→ "Heap(힙)을 주로 사용합니다. 힙은 우선순위에 따라 빠르게 최솟값/최댓값을 추출할 수 있는 구조입니다."