배열

배열

가장 기본적인 자료구조 입니다.

여러 개의 변수를 담는 공간으로 이해 할 수 있다.

배열은 인덱스가 존재하며, 인덱스는 0부터 시작한다.

특정한 인덱스에 직접적으로 접근 가능 > 수행 시간: O(1)

 

배열의 특징

컴퓨터의 메인 메모리에서 배열의 공간은 연속적으로 할당된다.

캐시 히트 가능성이 높으며, 조회가 빠르다.

배열의 크기를 미리 지정해야 하는 것이 일반적이므로,  데이터의 추가 및 삭제의 한계가 있다.

 

연결 리스트(Linked List)

컴퓨터의 메인 메모리상에서 주소가 연속적이지 않다.

배열과 다르게 크기가 정해져 있지 않고, 리스트의 크기는 동적으로 변경 가능하다.

장점 : 포인터(pointer)를 통해 다음 데이터의 위치를 가리킨다는 점에서 삽입과 삭제가 간편하다.

단점 : 원소를 검색할 때는 앞에서부터 원소를 찾아야 하므로, 데이터 검색 속도가 느리다.

 

파이썬의 리스트(List) 자료형

• 파이썬의 리스트 자료형은 동적 배열이다.
• 배열의 용량이 가득 차면, 자동으로 크기를 증가시킨다.
• 내부적으로 포인터(pointer)를 사용하여, 연결 리스트의 장점도 가지고 있다.
• 배열(array) 혹은 스택(stack)의 기능이 필요할 때 리스트 자료형을 그대로 사용할 수 있다.
• 큐(queue)의 기능을 제공하지 못한다.(비효율적)

리스트 컴프리헨션(List Comprehension)

파이썬에서 임의의 크기를 가지는 배열을 만들 수 있다.

일반적으로 리스트 컴프리헨션을 사용한다.

크기가 N인 1차 배열을 만드는 방법은 다음과 같다.

N = 10  # 배열의 크기
array = [0] * N
print(array)
#[0,0,0,0,0,0,0,0,0,0,]

N = 10  # 배열의 크기
array = [i for i in range(N)]
print(array)
# [0,1,2,3,4,5,6,7,8,9]

 

배열을 초기화할 때 유의할 점
리스트는 기본적으로 메모리 주소를 반환하므로, 배열을 초기화할 때 주의해야 합니다.

특히, [[0] * m] * n 형태로 배열을 초기화하면 문제가 발생할 수 있습니다.

 

잘못된 초기화 방식
[[0] * m] * n 형태로 배열을 초기화하면, n개의 [0] * m 리스트는 모두 같은 객체로 인식됩니다.

다시 말해, 동일한 메모리를 가리키는 n개의 원소를 담는 리스트가 됩니다.

이렇게 초기화하면 한 원소를 변경할 때 다른 원소들도 같이 변경되는 문제가 발생합니다.

# 잘못된 초기화 예시
n, m = 3, 4
array = [[0] * m] * n
array[0][0] = 1
print(array)  # 출력: [[1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]

 

 

올바른 초기화 방식
각각의 서브 리스트가 독립적인 객체가 되도록 리스트 컴프리헨션을 사용하여 초기화해야 합니다.

각 서브 리스트가 독립된 객체로 생성되므로, 하나의 리스트를 수정해도 다른 리스트에는 영향을 미치지 않습니다.

# 올바른 초기화 예시
n, m = 3, 4
array = [[0] * m for _ in range(n)]
array[0][0] = 1
print(array)  # 출력: [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]