배열(Array)과 리스트(List)

Data Structures/Python

배열(Array)과 리스트(List)

newclass 2025. 3. 26. 04:26

배열(Array)과 리스트(List)

개념 소개

배열과 리스트는 프로그래밍에서 가장 기본적인 자료구조로, 여러 데이터를 순차적으로 저장하는 컨테이너입니다. 파이썬에서는 리스트가 기본 자료구조로 제공되며, 이는 다른 언어의 동적 배열과 유사한 특성을 가집니다.

1. 배열(Array)

배열은 메모리에서 연속적인 공간에 동일한 타입의 데이터를 순차적으로 저장하는 자료구조입니다. 배열의 크기는 보통 선언 시점에 고정되며, 인덱스를 통해 빠르게 요소에 접근할 수 있습니다.

2. 파이썬의 리스트(List)

파이썬의 리스트는 다른 언어의 배열보다 더 유연한 특성을 가집니다:

다양한 타입의 요소를 함께 저장할 수 있습니다.
크기가 동적으로 변할 수 있습니다(동적 배열로 구현됨).
다양한 내장 메서드를 제공합니다.

3. 시간 복잡도

연산 평균 시간 복잡도 최악 시간 복잡도

접근 (Access)	O(1)	O(1)
검색 (Search)	O(n)	O(n)
삽입 (Insertion)	O(n)	O(n)
삭제 (Deletion)	O(n)	O(n)

주의: 파이썬 리스트의 append() 연산은 대부분의 경우 O(1)이지만, 내부 배열 크기 조정이 필요할 때는 O(n)이 될 수 있습니다.

파이썬에서의 구현과 활용

1. 리스트 생성

# 빈 리스트 생성
empty_list = []
empty_list = list()

# 초기값이 있는 리스트 생성
numbers = [1, 2, 3, 4, 5]
mixed = [1, "hello", 3.14, True]

# 리스트 컴프리헨션으로 생성
squares = [x**2 for x in range(10)]  # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

# 특정 값으로 초기화된 리스트 생성
zeros = [0] * 5  # [0, 0, 0, 0, 0]

2. 리스트 접근 및 슬라이싱

numbers = [10, 20, 30, 40, 50]

# 인덱스로 접근 (0부터 시작)
first = numbers[0]  # 10
last = numbers[-1]  # 50

# 슬라이싱: numbers[start:end:step]
sub_list = numbers[1:4]  # [20, 30, 40]
reversed_list = numbers[::-1]  # [50, 40, 30, 20, 10]

3. 리스트 조작

numbers = [1, 2, 3]

# 요소 추가
numbers.append(4)  # [1, 2, 3, 4]
numbers.insert(1, 1.5)  # [1, 1.5, 2, 3, 4]
numbers.extend([5, 6])  # [1, 1.5, 2, 3, 4, 5, 6]

# 요소 제거
numbers.remove(1.5)  # 값으로 제거: [1, 2, 3, 4, 5, 6]
popped = numbers.pop()  # 마지막 요소 제거 후 반환: 6, numbers = [1, 2, 3, 4, 5]
popped_index = numbers.pop(1)  # 특정 인덱스 제거 후 반환: 2, numbers = [1, 3, 4, 5]
numbers.clear()  # 모든 요소 제거: []

# 리스트 연산
list1 = [1, 2, 3]
list2 = [4, 5, 6]
combined = list1 + list2  # [1, 2, 3, 4, 5, 6]
repeated = list1 * 3  # [1, 2, 3, 1, 2, 3, 1, 2, 3]

4. 리스트 탐색 및 정보 확인

numbers = [10, 20, 30, 20, 40, 50]

# 요소 검색
position = numbers.index(20)  # 첫 번째 20의 인덱스: 1
count = numbers.count(20)  # 20의 개수: 2
exists = 30 in numbers  # 30이 리스트에 있는지 확인: True

# 리스트 정보
length = len(numbers)  # 리스트 길이: 6
minimum = min(numbers)  # 최소값: 10
maximum = max(numbers)  # 최대값: 50
total = sum(numbers)  # 합계: 170

5. 리스트 정렬

numbers = [3, 1, 4, 1, 5, 9, 2]

# 원본 리스트 정렬
numbers.sort()  # [1, 1, 2, 3, 4, 5, 9]
numbers.sort(reverse=True)  # [9, 5, 4, 3, 2, 1, 1]

# 정렬된 새 리스트 반환 (원본 유지)
numbers = [3, 1, 4, 1, 5, 9, 2]
sorted_asc = sorted(numbers)  # [1, 1, 2, 3, 4, 5, 9]
sorted_desc = sorted(numbers, reverse=True)  # [9, 5, 4, 3, 2, 1, 1]

# 사용자 정의 기준으로 정렬
words = ["banana", "apple", "cherry"]
sorted_by_length = sorted(words, key=len)  # ["apple", "banana", "cherry"]

6. 리스트의 메모리와 깊은 복사

# 얕은 복사 (같은 객체를 참조)
original = [1, 2, [3, 4]]
shallow = original  # 같은 객체를 가리킴
shallow[0] = 99  # original도 변경됨: [99, 2, [3, 4]]

# 리스트의 얕은 복사 (새 리스트이지만 내부 객체는 같은 참조)
original = [1, 2, [3, 4]]
shallow_copy = original.copy()  # or list(original) 또는 original[:]
shallow_copy[0] = 99  # original은 변경되지 않음: [1, 2, [3, 4]]
shallow_copy[2][0] = 99  # original의 내부 리스트도 변경됨: [1, 2, [99, 4]]

# 깊은 복사 (내부 객체까지 모두 새로 복사)
import copy
original = [1, 2, [3, 4]]
deep_copy = copy.deepcopy(original)
deep_copy[2][0] = 99  # original은 변경되지 않음: [1, 2, [3, 4]]

NumPy 배열

파이썬에서 효율적인 수치 계산을 위해 NumPy 라이브러리의 배열(ndarray)을 사용할 수 있습니다.

import numpy as np

# 배열 생성
arr = np.array([1, 2, 3, 4, 5])
zeros = np.zeros(5)  # [0. 0. 0. 0. 0.]
ones = np.ones(5)  # [1. 1. 1. 1. 1.]
range_arr = np.arange(0, 10, 2)  # [0 2 4 6 8]

# 배열 연산 (벡터화된 연산으로 빠름)
arr = np.array([1, 2, 3, 4, 5])
arr + 5  # [6 7 8 9 10]
arr * 2  # [2 4 6 8 10]
arr ** 2  # [1 4 9 16 25]

# 다차원 배열
matrix = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
matrix.shape  # (3, 3)
matrix[1, 1]  # 5

실전 활용 예제

예제 1: 이차원 리스트로 행렬 표현하기

def create_matrix(rows, cols, default=0):
    """지정된 크기와 기본값으로 행렬(이차원 리스트) 생성"""
    return [[default for _ in range(cols)] for _ in range(rows)]

def print_matrix(matrix):
    """행렬을 보기 좋게 출력"""
    for row in matrix:
        print(row)

# 3x3 행렬 생성
matrix = create_matrix(3, 3)
matrix[0][0] = 1
matrix[1][1] = 5
matrix[2][2] = 9

print_matrix(matrix)
# [1, 0, 0]
# [0, 5, 0]
# [0, 0, 9]

예제 2: 리스트를 이용한 동적 배열 구현

class DynamicArray:
    def __init__(self):
        self.size = 0  # 실제 요소의 개수
        self.capacity = 1  # 할당된 메모리 크기
        self.array = [None] * self.capacity
    
    def append(self, element):
        # 용량이 가득 찼을 경우 크기를 두 배로 확장
        if self.size == self.capacity:
            self._resize(2 * self.capacity)
        
        # 요소 추가
        self.array[self.size] = element
        self.size += 1
    
    def _resize(self, new_capacity):
        # 새로운 크기의 배열 생성
        new_array = [None] * new_capacity
        
        # 기존 요소 복사
        for i in range(self.size):
            new_array[i] = self.array[i]
        
        # 새 배열로 교체
        self.array = new_array
        self.capacity = new_capacity
    
    def __len__(self):
        return self.size
    
    def __getitem__(self, index):
        if not 0 <= index < self.size:
            raise IndexError('Index out of range')
        return self.array[index]
    
    def __str__(self):
        return str([self.array[i] for i in range(self.size)])

# 사용 예
dynamic_array = DynamicArray()
for i in range(10):
    dynamic_array.append(i)

print(dynamic_array)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(f"Size: {len(dynamic_array)}, Capacity: {dynamic_array.capacity}")

리스트와 관련된 알고리즘 문제

두 수의 합: 리스트에서 두 수의 합이 특정 값이 되는 인덱스 찾기
배열 회전: 리스트를 왼쪽 또는 오른쪽으로 회전하기
최대 부분 배열 합: 연속된 부분 배열 중 합이 최대인 것 찾기 (Kadane's 알고리즘)
중복 제거: 정렬된/정렬되지 않은 배열에서 중복 요소 제거하기
리스트 병합: 두 개의 정렬된 리스트를 병합하기

파이썬 리스트의 내부 구현 이해하기

파이썬의 리스트는 내부적으로 동적 배열로 구현되어 있습니다. 이는 다음과 같은 특성을 가집니다:

오버할당(Over-allocation): 리스트에 공간이 더 필요할 때, 현재 크기보다 더 큰 메모리를 할당하여 미래의 추가 작업에 대비합니다.
재할당(Reallocation): 리스트 크기가 현재 용량을 초과하면 새로운 메모리 블록을 할당하고 기존 데이터를 복사합니다.
포인터 배열: 리스트는 실제로 객체에 대한 포인터(참조)의 배열입니다. 따라서 하나의 리스트에 여러 타입의 객체를 저장할 수 있습니다.

이해하기 쉽게 생각하면, 리스트는 자동으로 크기가 조절되는 주차장과 같습니다. 처음에는 작은 주차장으로 시작하지만, 차가 많아지면 더 큰 주차장으로 모든 차를 옮기는 방식으로 작동합니다.

마무리

파이썬의 리스트는 매우 유연하고 강력한 자료구조로, 많은 알고리즘과 프로그래밍 문제에 사용됩니다. 리스트의 기본 연산과 다양한 메서드를 익히는 것은 파이썬으로 알고리즘을 구현하는 데 있어 가장 기초적이면서도 중요한 단계입니다. 배열과 리스트의 특성과 시간 복잡도에 대한 이해는 효율적인 알고리즘을 설계하는 데 필수적입니다.