NeetCode 150: Arrays, Python, and Time Complexity Guide
AI Store에서 AI코딩으로 만들어진 앱을 만나보세요!
지금 바로 방문하기

배열과 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) vs arr2 = arr (참조)

결론

- 정적 배열은 고정 크기, 동적 배열은 유연성 제공 (Python의 list 활용)

- 중간 삽입/삭제는 O(n) 시간 복잡도 → 알고리즘 설계 시 주의

- append()는 평균 O(1) (배열 재할당 비용은 amortized)

- 리스트 컴프리헨션 및 슬라이싱은 배열 조작 시 효율적인 패턴으로 활용 권장