**자료구조(Data Structure)**란 대용량의 데이터를 효율적으로 저장, 조직, 관리하기 위한 컴퓨터 과학의 핵심 기법입니다. 적절한 자료구조 선택은 알고리즘의 실행 속도와 메모리 사용량을 획기적으로 개선합니다.
1. 추상 자료형 (ADT, Abstract Data Type)
추상 자료형(ADT)은 자료구조의 **구현 세부사항을 숨기고, 어떠한 데이터와 연산을 제공하는지 명세(Specification)**만 정의한 수학적 모델입니다.
- 데이터 명세: 자료구조가 다루는 대상 데이터 집합.
- 연산 명세: 데이터에 대해 수행할 수 있는 동작(입력, 반환값, 효과).
- 캡슐화 및 정보 은닉: 사용자는 ADT 인터페이스만 이용하며, 내부 구현(배열, 연결 리스트 등)이 변경되어도 외부 코드에 영향을 주지 않습니다.
2. 파이썬 클래스와 객체지향 자료구조 설계
파이썬은 모든 것이 객체(Object)인 다중 패러다임 언어입니다. class 키워드를 통해 수식어와 연산을 묶는 사용자 정의 자료구조를 만들 수 있습니다.
class Student:
def __init__(self, name, student_id):
self.name = name
self.student_id = student_id
def get_info(self):
return f"[{self.student_id}] {self.name}"
# 객체 생성 및 활용
s = Student("이인상", 20260001)
print(s.get_info())
3. 파이썬 리스트의 연산과 시간 복잡도
파이썬의 list는 **동적 배열(Dynamic Array)**로 구현되어 있어, 인덱스 접근은 매우 빠르지만 요소 삽입/삭제 위치에 따라 시간 복잡도가 크게 달라집니다.
| 연산 | 파이썬 코드 | 시간 복잡도 | 설명 |
|---|---|---|---|
| 인덱싱 / 슬라이싱 | arr[i] |
$O(1)$ | 메모리 주소 즉시 계산 |
| 맨 뒤 추가 | arr.append(x) |
$O(1)$ (Amortized) | 여유 공간 있을 때 오버헤드 없음 |
| 맨 뒤 삭제 | arr.pop() |
$O(1)$ | 맨 끝 요소 제거 |
| 중간/맨 앞 삽입 | arr.insert(0, x) |
$O(N)$ | 뒤쪽의 모든 원소를 1칸씩 이동(Shift) |
| 중간/맨 앞 삭제 | arr.pop(0) |
$O(N)$ | 앞쪽 원소 제거 후 전체 Shift |
4. 파이썬 고차 함수 (Filter, Map, Lambda)
자료구조 내의 데이터를 일괄 가공하거나 조건 탐색 시, 함수형 프로그래밍 스타일 기법을 적용할 수 있습니다.
# 짝수 제곱 구하기 예시
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# filter: 짝수만 추출
evens = list(filter(lambda x: x % 2 == 0, numbers))
# map: 각 요소를 제곱
squared_evens = list(map(lambda x: x ** 2, evens))
print(squared_evens) # [4, 16, 36, 64, 100]
5. 자주 묻는 질문 (Q&A)
Q. 파이썬 리스트의 append() 연산이 분할 상쇄 $O(1)$ (Amortized O(1))인 이유는 무엇인가요? A. 리스트 용량이 꽉 차면 기존 용량의 약 1.125배~1.5배로 더 큰 새 메모리를 할당받아 기존 원소를 복사합니다. 이 재할당 $O(N)$ 연산은 가끔 일어나므로, N번의 append 연산 전체 비용을 평균 내면 1회당 $O(1)$이 됩니다.