배열에 대해 배운 내용: NeetCode 150 학습 요약

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 분석

대상자

- 초급~중급 개발자: 배열의 기본 개념과 Python에서의 구현 방식을 학습하고자 하는 사람들

- DSA(자료구조 및 알고리즘) 준비자: NeetCode 150 문제를 풀며 배열 관련 패턴을 정리하고자 하는 사람들

- 난이도: 중간 (시간 복잡도와 구현 예시 포함)

핵심 요약

• 정적 배열(static array)은 크기가 고정되어 있으며, 동적 배열(dynamic array)은 Python과 JavaScript에서 리스트(list) 형태로 자동 확장이 가능하다.
• 삽입/삭제 연산의 시간 복잡도:

- 중간 요소 삽입/삭제: O(n) (요소 이동 필요)

- 끝 요소 삽입/삭제: O(1) (동적 배열의 경우 평균 시간 복잡도)

• Python의 리스트는 append(), insert(), pop() 등 다양한 메서드를 제공하며, 리스트 컴프리헨션을 통해 간결하게 배열 생성 가능.

섹션별 세부 요약

1. 정적 배열과 동적 배열의 차이

• 정적 배열: 크기 고정, Java/C++/C#에서 사용.
• 동적 배열: Python/JavaScript에서 사용, 2배 확장을 통해 시간 복잡도 O(1)을 유지.
• 예시: push_back() 함수에서 기존 배열을 2배 크기로 재할당 후 요소 복사.

2. 배열의 주요 연산과 시간 복잡도

• 인덱스 접근: O(1) (메모리 주소 직접 매핑)
• 중간 요소 삽입/삭제: O(n) (요소 이동 필요)
• 끝 요소 삽입/삭제: O(1) (동적 배열의 경우 평균 시간 복잡도)
• 예시: array.insert(0, 4)는 O(n) 복잡도.

3. Python 리스트의 주요 메서드

• append(x): 끝에 요소 추가.
• pop(): 마지막 요소 제거.
• insert(i, x): 특정 인덱스에 삽입.
• sort(): 리스트 정렬.
• reverse(): 리스트 역순 정렬.

4. 배열 관련 패턴 및 예시

• 리스트 컴프리헨션: squares = [x**2 for x in range(10) if x % 2 == 0]
• 슬라이싱: a[1:4], a[::2], a[::-1]
• 이진 탐색 패턴: bisect_left()를 사용한 요소 삽입 위치 찾기.
• 최대 부분합 계산: max_subarray_sum() 함수로 O(n) 복잡도 구현.

결론

• 배열의 시간 복잡도를 이해하고, 동적 배열의 확장 메커니즘을 활용해 효율적으로 데이터를 처리해야 한다.
• Python의 list 메서드(append, insert, pop)와 리스트 컴프리헨션을 적절히 사용해 코드를 간결하게 작성하라.
• 인터뷰 문제 풀이 시, 이진 탐색(bisect)과 슬라이싱 패턴을 자주 활용하는 것이 중요하다.