동적 배열 이론

1. 선형 vs 비선형 구조

선형 구조

• 정의: 데이터를 순차적으로 나열하는 형태.
• 예시: 배열, 연결 리스트, 스택, 큐.
• 특징:
  • 데이터가 일렬로 정렬되어 있어 다음 데이터에 쉽게 접근 가능.
• 비유: 은행에서 줄을 서서 대기표를 받는 상황.

비선형 구조

• 정의: 하나의 데이터 뒤에 여러 개의 데이터가 연결될 수 있는 형태.
• 예시: 트리, 그래프.
• 특징:
  • 복잡한 관계를 표현하기에 적합하며, 탐색이나 경로 찾기에 유용.
• 비유: 지하철 노선도처럼 데이터 간 연결이 복잡하고 다양한 경로 존재.

---

2. 배열과 동적 배열의 차이

정적 배열

• 특징:
  • 크기가 고정.
  • 연속된 메모리 공간을 미리 할당받음.
  • 크기 변경 불가.
• 장점:
  • 메모리 상에서 연속적으로 배치되어 있어 접근 속도가 빠름.
• 단점:
  • 크기 변경이 불가해 메모리 사용이 비효율적일 수 있음.
• 비유: 호텔 방을 고정적으로 예약 (예: 101호, 102호).

---

동적 배열

• 특징:
  • 배열의 크기를 실행 중에 유동적으로 변경 가능.
  • 크기 변경 시 기존 데이터를 새로운 메모리 공간으로 복사.
• 장점:
  • 필요한 만큼 메모리를 동적으로 할당받아 유연성이 뛰어남.
• 단점:
  • 크기 변경 시 이사 비용(데이터 복사 비용)이 발생.
• 비유: 필요에 따라 방을 추가하거나 줄임 (예: 301호, 302호).

---

3. 동적 배열의 메모리 관리

문제점: 이사 비용

• 기존 메모리 공간이 부족하면 데이터를 새로운 메모리 공간으로 이동해야 함.
• 이동에는 시간이 소요되며, 배열이 클수록 비용 증가.

할당 정책

• 이사 비용을 줄이기 위해 여유 메모리를 미리 확보.
• 일반적으로 필요한 크기의 1.5~2배를 예약.
• 여유 공간 확보로 크기 변경 횟수 감소 → 효율적.

비유

• 필요한 방 외에 305호, 306호처럼 여유분을 미리 예약.
• 이후 추가 방이 필요해도 공간 이동 없이 사용 가능.

---