데이터 구조 정리 - Array

💾 배열 (Array)

배열은 동일한 타입의 데이터들을 연속된 메모리 공간에 순서대로 저장하는 가장 기본적인 자료구조입니다. 각 데이터는 고유한 인덱스(Index) 를 가지며, 이 인덱스를 통해 해당 데이터에 직접 접근할 수 있습니다. 파이썬에서는 리스트(list)가 동적 배열의 역할을 수행합니다.

특징

1. 동적 크기 (Dynamic Size): 파이썬의 list는 필요에 따라 크기가 자동으로 조절됩니다. 내부적으로는 크기가 부족할 때 더 큰 메모리 공간을 할당하고 기존 데이터를 복사하는 방식으로 동작합니다.
2. 인덱스 기반 접근 (Index-based Access): 각 요소는 0부터 시작하는 고유한 정수 인덱스를 가집니다. 이 인덱스를 사용하면 원하는 요소에 매우 빠르게 ([O(1)]) 접근할 수 있습니다.
3. 연속적인 메모리 할당 (Contiguous Memory Allocation): list의 요소들은 메모리 상에 (일반적으로) 연속하여 위치합니다. 이는 캐시 효율성 측면에서 이점을 가질 수 있습니다.
4. 다양한 데이터 타입 저장 가능 (Heterogeneous Data Type): 파이썬 list는 서로 다른 타입의 데이터(정수, 문자열, 객체 등)를 함께 저장할 수 있습니다. 내부적으로는 각 요소에 대한 참조(메모리 주소)를 저장합니다.

기본 연산 및 시간 복잡도

연산	설명	시간 복잡도 (최악)	비고
접근 (Access)	인덱스를 사용하여 특정 위치의 요소 읽기/쓰기	[O(1)]	메모리 주소를 바로 계산 가능
탐색 (Search)	특정 값을 가진 요소를 찾기 (선형 탐색)	[O(N)]	in 연산자 또는 index() 메소드 사용 시
삽입 (Insertion)	맨 끝에 추가 (append)	[O(1)] (분할 상환)	공간 재할당이 필요 없는 경우. 재할당 시 [O(N)]
	중간에 삽입 (insert)	[O(N)]	삽입 위치 뒤의 모든 요소를 한 칸씩 뒤로 밀어야 함
삭제 (Deletion)	맨 끝 요소 삭제 (pop)	[O(1)]
	중간 요소 삭제 (pop(index), del)	[O(N)]	삭제 위치 뒤의 모든 요소를 한 칸씩 앞으로 당겨야 함

• N은 리스트에 저장된 요소의 개수를 의미합니다.
• append의 시간 복잡도는 분할 상환 분석(Amortized Analysis) 을 통해 평균적으로 [O(1)]로 간주합니다.

장점

• 빠른 접근 속도: 인덱스를 알고 있다면 [O(1)] 시간 복잡도로 요소에 즉시 접근할 수 있습니다.
• 유연한 크기 조절: 동적으로 크기가 조절되어 사용하기 편리합니다.
• 다양한 내장 함수: 파이썬 list는 슬라이싱, 정렬, 탐색 등 유용한 내장 함수/메소드를 풍부하게 제공합니다.

단점

• 삽입 및 삭제 비효율성: 리스트의 중간에 데이터를 삽입하거나 삭제할 경우, 해당 위치 뒤의 요소들을 이동시켜야 하므로 [O(N)]의 시간이 소요됩니다.
• 메모리 오버헤드 (재할당 시): 크기 재할당 시 기존 요소들을 복사하는 과정에서 일시적으로 추가 메모리 사용 및 시간 소요가 발생할 수 있습니다.
• 다양한 타입 저장 시 잠재적 비효율: 모든 요소를 객체 참조로 관리하므로, 타입이 고정된 배열에 비해 약간의 메모리 오버헤드가 있을 수 있습니다.

활용 사례

• 간단한 데이터 목록 저장 및 관리
• 다른 복잡한 자료구조(스택, 큐 등)를 구현하는 기본 요소 (파이썬 list로 스택/큐 구현 가능)
• 다차원 리스트를 이용한 행렬(Matrix) 표현 및 연산
• 데이터 처리 및 분석 작업
• 웹 개발에서의 데이터 전달 등

Python 예시 (list)

# 리스트 생성
my_list = [10, 20, 30, 40, 50]
empty_list = []
another_list = [0] * 5 #=> [0, 0, 0, 0, 0]
mixed_list = [1, "hello", 3.14, True] # 다양한 타입 저장 가능

# 요소 접근 (O(1))
print(my_list[0])  #=> 10
print(my_list[2])  #=> 30
my_list[1] = 25  # 요소 수정
print(my_list)     #=> [10, 25, 30, 40, 50]

# 맨 끝에 요소 추가 (Amortized O(1))
my_list.append(60)
print(my_list)     #=> [10, 25, 30, 40, 50, 60]

# 맨 끝 요소 삭제 (O(1))
last_element = my_list.pop()
print(last_element) #=> 60
print(my_list)     #=> [10, 25, 30, 40, 50]

# 중간에 요소 삽입 (O(N))
my_list.insert(2, 99) # 인덱스 2 위치에 99 삽입
print(my_list)     #=> [10, 25, 99, 30, 40, 50]

# 중간 요소 삭제 (O(N))
deleted_element = my_list.pop(3) # 인덱스 3의 요소 삭제 및 반환
print(deleted_element) #=> 30
print(my_list)     #=> [10, 25, 99, 40, 50]

# 특정 인덱스 요소 삭제 (O(N))
del my_list[1] # 인덱스 1의 요소 삭제
print(my_list)     #=> [10, 99, 40, 50]

# 요소 탐색 (O(N))
print(40 in my_list) #=> True
try:
    print(my_list.index(99))   #=> 1 (값이 99인 요소의 첫 인덱스 반환)
    print(my_list.index(100)) # 없는 요소 찾으면 ValueError 발생
except ValueError:
    print("100 not found in the list")

# 리스트 크기
print(len(my_list)) #=> 4

---

📌 기억해두면 좋은 영어 표현

• List (Python): 리스트 (파이썬의 동적 배열 구현체)
• Array: 배열 (일반적인 개념)
• Index (plural: Indices): 인덱스
• Element / Item: 요소, 항목
• Dynamic Array: 동적 배열
• Contiguous Memory Allocation: 연속적인 메모리 할당
• Access (Operation): 접근 (연산)
• Search (Operation): 탐색 (연산)
• Insertion (Operation): 삽입 (연산)
  • Append: (맨 끝에) 추가하다
• Deletion (Operation): 삭제 (연산)
  • Pop: (주로 맨 끝 또는 특정 인덱스에서) 꺼내다/삭제하다
• Time Complexity: 시간 복잡도 ([O(1)], [O(N)])
• Amortized Analysis: 분할 상환 분석

---

❓ 영어로 질문하기

• 한글: 파이썬 리스트에서 특정 인덱스의 요소에 접근하는 것이 [O(1)]인 이유는 무엇인가요?
• 영어: "Why is accessing an element at a specific index in a Python list an [O(1)] operation?"
• 한글: 파이썬 리스트 중간에 요소를 삽입하거나 삭제하는 것이 [O(N)] 시간 복잡도를 갖는 이유는 무엇인가요?
• 영어: "Why do insertion and deletion operations in the middle of a Python list have an [O(N)] time complexity?"
• 한글: 파이썬 리스트의 append 연산이 분할 상환 [O(1)] 시간 복잡도를 갖는다는 것은 무엇을 의미하나요?
• 영어: "What does it mean for the append operation in a Python list to have an amortized [O(1)] time complexity?"

---

🚀 도움되는 정보

• 기본 중의 기본: 배열(파이썬에서는 list)은 모든 프로그래밍 언어에서 가장 기본이 되는 자료구조입니다. 리스트의 동작 방식과 시간 복잡도에 대한 이해는 개발자로서 필수적인 소양입니다.
• 코딩 테스트 단골: 많은 코딩 테스트 문제에서 리스트를 직접 사용하거나, 다른 자료구조의 기반으로 활용하는 경우가 많습니다. 리스트의 기본 연산(삽입, 삭제, 탐색) 및 슬라이싱 등을 효율적으로 다루는 능력은 중요합니다.
• 성능 고려: 리스트의 [O(1)] 접근 속도와 [O(N)] 삽입/삭제 비용의 트레이드오프를 이해하는 것은 실제 애플리케이션 개발 시 성능 최적화에 중요합니다. 예를 들어, 데이터 접근이 빈번하고 삽입/삭제가 적다면 리스트가 좋은 선택일 수 있습니다. 면접에서 이러한 상황 판단 능력을 보여주는 것이 좋습니다.
• 다른 자료구조와의 비교: 면접에서는 리스트와 튜플(tuple), 딕셔너리(dict), 세트(set) 등 다른 파이썬 내장 자료구조와의 차이점, 그리고 일반적인 배열과 연결 리스트(Linked List)를 비교하며 각각의 장단점과 사용 사례를 묻는 질문이 자주 나옵니다. 각 자료구조의 특징을 명확히 이해하고 설명할 수 있어야 합니다.