기쁘달

배열 (Array)

7 min read

개념

같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조

인덱스를 통해 각 요소에 직접 접근(Random Access) 가능

시간복잡도

연산시간복잡도설명
접근O(1)인덱스로 바로 접근 가능
탐색O(n)처음부터 끝까지 순회 필요
삽입O(n)중간 삽입 시 뒤 요소들 이동
삭제O(n)중간 삭제 시 뒤 요소들 이동

특징

장점

  • 인덱스를 통한 빠른 접근 O(1)
  • 메모리 공간이 연속적으로 할당되어 캐시 효율이 좋음
  • 구현이 간단하고 직관적

단점

  • 크기가 고정됨 (단, Python의 list는 동적 배열)
  • 중간 삽입/삭제 시 O(n) 시간 소요
  • 메모리 낭비 가능성 (미리 할당해야 함)

Python 구현

1. 기본 배열 생성 및 접근

# 배열 생성
arr = [1, 2, 3, 4, 5]
 
# 인덱스로 접근
print(arr[0])   # 1
print(arr[-1])  # 5 (음수 인덱스: 뒤에서부터)
 
# 슬라이싱
print(arr[1:4])  # [2, 3, 4]
print(arr[:3])   # [1, 2, 3]
print(arr[2:])   # [3, 4, 5]

2. 배열 수정

arr = [1, 2, 3, 4, 5]
 
# 요소 변경
arr[0] = 10
print(arr)  # [10, 2, 3, 4, 5]
 
# 요소 추가
arr.append(6)      # 끝에 추가 → [10, 2, 3, 4, 5, 6]
arr.insert(1, 15)  # 특정 위치에 추가 → [10, 15, 2, 3, 4, 5, 6]
 
# 요소 삭제
arr.pop()       # 마지막 요소 제거
arr.pop(0)      # 특정 인덱스 요소 제거
arr.remove(15)  # 특정 값 제거 (첫 번째 매칭)

3. 배열 순회

arr = [1, 2, 3, 4, 5]
 
# 값만 순회
for num in arr:
    print(num)
 
# 인덱스와 값 함께 순회
for idx, num in enumerate(arr):
    print(f"인덱스 {idx}: {num}")

4. 유용한 배열 메서드

arr = [3, 1, 4, 1, 5, 9, 2, 6]
 
# 정렬
arr.sort()                # 오름차순 정렬 (원본 변경) O(n log n)
sorted_arr = sorted(arr)  # 새로운 정렬된 배열 반환
 
# 역순
arr.reverse()             # 역순으로 변경 (원본 변경)
reversed_arr = arr[::-1]  # 새로운 역순 배열
 
# 길이, 합계, 최댓값, 최솟값
length = len(arr)
total = sum(arr)
max_val = max(arr)
min_val = min(arr)
 
# 특정 값의 개수 / 인덱스
count = arr.count(1)  # 값 1의 개수
index = arr.index(4)  # 값 4의 첫 번째 인덱스

자주 나오는 문제 유형

1. 두 수의 합 (Two Sum)

문제: 배열에서 합이 target이 되는 두 수의 인덱스를 반환

def two_sum(nums, target):
    # 방법 1: 브루트포스 - O(n²)
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
 
    # 방법 2: 해시맵 사용 - O(n) ⭐ 추천
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
 
    return []
 
# 테스트
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

핵심: 해시맵으로 시간복잡도를 O(n²) → O(n)으로 개선

2. 배열 회전

문제: 배열을 오른쪽으로 k번 회전

def rotate_array(arr, k):
    n = len(arr)
    k = k % n  # k가 배열 길이보다 클 경우 대비
 
    # 슬라이싱 활용 - O(n)
    return arr[-k:] + arr[:-k]
 
# 테스트
print(rotate_array([1, 2, 3, 4, 5], 2))  # [4, 5, 1, 2, 3]

핵심: Python 슬라이싱 문법을 활용한 간결한 구현

3. 최대 부분 배열 합 (Kadane’s Algorithm)

문제: 연속된 부분 배열의 최대 합을 구함

def max_subarray_sum(nums):
    max_sum = current_sum = nums[0]
 
    for num in nums[1:]:
        # 현재 값부터 새로 시작 vs 이전 합에 추가
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
 
    return max_sum
 
# 테스트
print(max_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
# 부분배열: [4, -1, 2, 1]

핵심: O(n) 시간에 해결하는 동적 프로그래밍 기법

4. 배열에서 중복 제거 (투 포인터)

문제: 정렬된 배열에서 중복을 제거하고 고유한 요소의 개수 반환

def remove_duplicates(nums):
    if not nums:
        return 0
 
    # 투 포인터: slow는 고유 값 위치, fast는 탐색
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
 
    return slow + 1
 
# 테스트
arr = [1, 1, 2, 2, 3, 4, 4, 5]
length = remove_duplicates(arr)
print(arr[:length])  # [1, 2, 3, 4, 5]

핵심: 투 포인터로 O(1) 공간복잡도로 제자리 수정

추천 연습 문제

기초

중급

핵심 요약

개념설명
접근 시간인덱스로 O(1) 접근 가능
동적 배열Python의 list는 크기 조정 가능
유용한 기법슬라이싱, enumerate, 투 포인터
최적화해시맵으로 탐색 시간 단축

배열 vs 연결 리스트

특성배열연결 리스트
메모리연속적불연속적
접근O(1)O(n)
삽입/삭제O(n)O(1) (위치 알 때)
크기고정 (Python은 동적)동적
캐시효율적비효율적

주의사항

1. 인덱스 범위 체크

# IndexError 방지
if 0 <= index < len(arr):
    value = arr[index]

2. 슬라이싱 시 복사본 생성

# 새로운 배열 생성 (메모리 사용)
arr2 = arr[:]
arr3 = arr.copy()

3. 정렬 후 원본 변경

arr.sort()        # 원본 변경
sorted_arr = sorted(arr)  # 원본 유지

그래프 뷰

백링크