배열과 NeetCode 150 학습 요약
카테고리
프로그래밍/소프트웨어 개발
서브카테고리
데이터 분석
대상자
- 초보 프로그래머 및 알고리즘 인터뷰 준비자
- Python을 사용하는 개발자
- 시간 복잡도와 배열 구조 이해가 필요한 학습자
- 난이도: 중간 수준 (기초 알고리즘 개념 이해 필요)
핵심 요약
- 정적 배열은 크기 고정, 동적 배열은 필요 시 자동 확장 (Python의
list
구현) - 인덱스 기반 접근은
O(1)
이지만, 중간 삽입/삭제는O(n)
(요소 이동 필요) - Python 리스트의
append()
는 평균O(1)
(배열 재할당은O(n)
이지만 드물게 발생)
섹션별 세부 요약
1. 정적 배열 (Static Arrays)
- 특징: 크기 고정,
Java
,C++
등 정적 타입 언어에서 사용 - 시간 복잡도:
- 인덱스 접근: O(1)
- 중간 삽입/삭제: O(n)
(요소 이동 필요)
- 끝 삽입/삭제: O(1)
2. 동적 배열 (Dynamic Arrays)
- 특징: Python의
list
, JavaScript의array
에서 사용 - 동작 원리: 용량 초과 시 2배 크기의 새로운 배열 생성 후 요소 복사
- 시간 복잡도:
- append()
평균 시간: O(1)
(Amortized Time)
- 중간 삽입/삭제: O(n)
(요소 이동 필요)
3. Python 리스트 주요 메서드
append(x)
: 끝에 요소 추가 (O(1)
)insert(i, x)
: 특정 인덱스 삽입 (O(n)
)pop()
: 끝 요소 삭제 (O(1)
)pop(i)
: 특정 인덱스 삭제 (O(n)
)
4. 배열의 시간 복잡도 요약
| 연산 | 시간 복잡도 |
|------|-------------|
| 인덱스 접근/수정 | O(1)
|
| 끝 삽입/삭제 | O(1)
|
| 중간 삽입/삭제 | O(n)
|
| 시작 삽입/삭제 | O(n)
|
5. Python 특징 및 패턴
- 리스트 컴프리헨션: 간결한 리스트 생성 (예:
[x**2 for x in range(10)]
) - 슬라이싱:
a[1:4]
→[2,3,4]
,a[::-1]
→ 역순 배열 - 배열 복제:
arr2 = arr[:]
(shalow copy) vsarr2 = arr
(참조)
결론
- 정적 배열은 고정 크기, 동적 배열은 유연성 제공 (Python의 list
활용)
- 중간 삽입/삭제는 O(n)
시간 복잡도 → 알고리즘 설계 시 주의
- append()
는 평균 O(1)
(배열 재할당 비용은 amortized)
- 리스트 컴프리헨션 및 슬라이싱은 배열 조작 시 효율적인 패턴으로 활용 권장