배열(Array)

Jeonghwan Yoon·2025년 3월 30일

배열이란?

동일한 자료형의 요소들을 연속적인 메모리 공간에 저장하는 자료구조
데이터는 인덱스(index)로 구분되며, 0부터 시작
같은 자료형(예: 정수, 문자열 등)의 값을 순서대로 저장하는 방식
파이썬에서는 내부적으로 동적 배열(Dynamic Array)을 사용하는 list를 통해 구현.
C 언어에서는 배열을 선언 시 크기가 고정되고, 한 번 정하면 수정이 불가능.

예시

파이썬: arr = [1, 2, 3]

C: int arr[5] = {1,2,3,4,5};

배열의 주요 특징

인덱스(Index)를 통한 직접 접근 가능
- arr[i] 형태로 O(1)에 접근 가능
  (파이썬도 내부적으로 동적 배열이지만 평균적으로 O(1)).
연속된 메모리
- 논리적으로나 물리적으로 연속적이며,
  중간 삽입·삭제 시 요소의 이동이 필요해 시간 복잡도가 O(N)이 됨.
탐색
- 정렬되지 않은 배열에서는 선형 탐색이 보통, O(N).
- 정렬된 배열이라면 이진 탐색으로 O(log N)에 검색 가능.

특징	설명
인덱스(index)	배열의 각 요소를 식별하는 번호. 0부터 시작
연속된 메모리	배열은 메모리상에 연속적으로 저장됨
빠른 접근	인덱스를 이용해 O(1) 시간에 원소에 접근 가능
삽입/삭제 비용	중간에 데이터를 추가하거나 삭제하면 뒤의 값을 전부 옮겨야 해서 O(N) 시간이 걸림

메모리 구조

배열은 인접한 메모리 번지를 차례로 할당받음.
예를 들어, arr[0]은 메모리 주소 1000부터 4바이트 차지,
arr[1]은 1004부터 4바이트

배열의 주요 연산

인덱스 접근 (Access)

arr[i] # 평균 O(1)
탐색 (Search)
- 선형 탐색: 배열 전체를 순회하며 비교 (O(N))
- 이진 탐색: 정렬 상태라면 중간값부터 비교 (O(log N))
삽입 (Insert)
- 중간에 삽입 시, 뒤쪽 원소들을 한 칸씩 밀어야 함 → O(N)
- 파이썬 list의 insert() 메서드도 내부적으로 동일 원리
삭제 (Delete)
- 특정 위치에서 원소 삭제 후, 뒤쪽 원소들을 한 칸씩 땡겨야 함 → O(N)

시간 복잡도 요약(BIG O)

연산	평균 시간 복잡도	설명
인덱스 접근	O(1)	배열의 장점 중 하나
탐색	O(N)	정렬 상태면 이진 탐색으로 O(log N) 가능
삽입	O(N)	중간 삽입 시 요소 이동 필요
삭제	O(N)	중간 삭제 시 요소 이동 필요

배열의 기본 연산

인덱스 접근

arr = [10, 20, 30]
print(arr[0]) # 출력: 10

arr[0] → 배열의 첫 번째 요소
arr[1] → 두 번째 요소

길이 구하기(len())

print(len(arr)) # 출력: 3

값 변경

arr[1] = 50
print(arr) # 출력: [10, 50, 30]

배열 직접 구현

특정 위치값 삽입

def insert_at(arr, index, value):
    """index 위치에 value를 삽입"""
    new_arr = []
    for i in range(len(arr)):      # ✅ 내장함수 사용: len()
        if i == index:
            new_arr.append(value)  # ✅ 내장함수 사용: append()
        new_arr.append(arr[i])     # ✅ 내장함수 사용: append()
    return new_arr
arr = [10, 20, 30]
arr = insert_at(arr, 1, 15)
print(arr)  # 출력: [10, 15, 20, 30]

C언어에서는

len() 배열 길이는 직접 변수로 관리하거나 문자열의 경우 \0 만날 때까지 순회
append() 배열의 크기를 관리하면서 직접 인덱스 위치에 삽입해야 함

특정 위치값 삭제

def delete_at(arr, index):
    """index 위치의 요소를 삭제"""
    new_arr = []
    for i in range(len(arr)):       # ✅ 내장함수 사용: len()
        if i != index:
            new_arr.append(arr[i])  # ✅ 내장함수 사용: append()
    return new_arr
arr = [10, 15, 20, 30]
arr = delete_at(arr, 2)
print(arr)  # 출력: [10, 15, 30]

C언어에서는

len() 직접 배열 길이를 세거나, 고정 길이로 선언
append() 없이 i번째 값을 i-1에 복사하는 방식으로 직접 이동시켜야 함

값 검색

def find_value(arr, target):
    """target 값이 배열에 있는지 확인하고 위치 반환"""
    for i in range(len(arr)):       # ✅ 내장함수 사용: len()
        if arr[i] == target:
            return i
    return -1
arr = [10, 20, 30]
print(find_value(arr, 30))  # 출력: 2

C언어에서도 동일하게 for문으로 순회하며 구현 가능

핵심 요약

배열은 인덱스를 통한 빠른 접근(O(1))이 가장 큰 장점.
중간 삽입/삭제가 잦을 경우 연결 리스트 같은 다른 자료구조도 고려.
정렬, 탐색 알고리즘을 구현할 때 배열을 많이 사용함.

배열 관련 주요 파이썬 내장함수 정리

함수	설명	예시
`len(arr)`	배열의 길이(요소 개수)를 반환	`len([1,2,3]) → 3`
`append(x)`	배열 맨 뒤에 x를 추가	`arr.append(10)`
`insert(i, x)`	i번 인덱스에 x 삽입	`arr.insert(2, 99)`
`pop(i)`	i번 인덱스 요소 제거 및 반환 (없으면 맨 뒤 제거)	`arr.pop(1)`
`remove(x)`	x값을 가진 첫 번째 요소 제거	`arr.remove(10)`
`index(x)`	x의 위치(인덱스) 반환	`arr.index(20)`
`sort()`	배열을 오름차순 정렬 (원본 수정)	`arr.sort()`
`reverse()`	배열을 뒤집음	`arr.reverse()`

자주 쓰이는 알고리즘 문제 유형

문제 유형	설명
최댓값/최솟값 찾기	배열 전체를 순회하며 비교
누적합 (Prefix Sum)	부분 합을 미리 계산해 빠르게 처리
정렬	배열 정렬 후 탐색 또는 조건 비교
슬라이딩 윈도우	연속된 부분 배열 처리에 유용