[코딩테스트 합격자 되기 05] 배열

배열 

배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조 이다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있다.

 

배열 선언

일반적인 방법 

arr = [0, 0, 0, 0, 0, 0] 
arr = [0] * 6

 

리스트 생성자 사용

arr = list(range(6)) #[0,1,2,3,4,5]

 

리스트 컴프리헨션을 활용하는 방법

arr = [0 for _ in range(6)]     # [0, 0, 0, 0, 0, 0]

 

 

배열과 차원

배열은 2차원, 3차원 배열과 같이 다차원 배열을 사용할 때도 많다. 하지만 컴퓨터 메모리의 구조는 1차원이므로, 2차원, 3차원 배열도 실제로는 1차원 공간에 저장한다. 다시 말해 배열은 차원과는 무관하게 메모리에 연속 할당된다.

 

1차원 배열

1차원 배열은 가장 간단한 배열 형태를 가진다. 1차원 배열의 모습은 메모리에 할당된 실제 배열의 모습과 같다.

오른쪽 모습이 실제 메모리에 배열이 할당된 모습

 

2차원 배열

2차원 배열은 1차원 배열을 확장한 것. 2차원 배열은 파이썬에서 리스트를 사용해 다음과 같이 선언할 수 있다.

# 2차원 배열을 리스트로 표현
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
# arr[2][3]에 저장된 값을 출력
print(arr[2][3])  # 12
# arr[2][3]에 저장된 값을 15로 변경
arr[2][3] = 15
# 변경된 값을 출력
print(arr[2][3])  # 15

 

리스트 컴프리헨션을 활용하면 다음과 같이 선언할 수도 있다.

# 크기가 3 * 4인 리스트를 선언하는 예
arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]

 

 

2차원 배열 데이터에 접근하는 방법은 1차원 배열과 비슷하다. 행과 열을 명시해 [] 연산자를 연이어 사용한다.

이를 그림으로 나타내면 다음과 같다.

오른쪽 모습이 실제 메모리에 할당된 2차원 배열의 모습

 

 

배열의 효율성

배열 연산의 시간 복잡도와 함께 배열의 효율성을 알아보자.

 

배열 연산의 시간 복잡도

배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있다. 따라서 데이터에 접근하기 위한 시간복잡도는 O(1)이다. 

배열에 데이터를 추가하는 경우에는 배열은 데이터를 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라진다. (삭제 연산도 추가와 마찬가지의 시간 복잡도를 가진다.)

 

맨 뒤에 삽입할 경우

맨 뒤에 삽입할 때는 arr[3]에 임의 접근을 바로 할 수 있어 시간 복잡도는 O(1)이다.

맨 앞에 삽입할 경우

이 경우 기존 데이터들을 뒤로 한 칸씩 밀어야한다. 데이터 개술르 N개로 일반화하면 시간 복잡도는 O(N)이 된다.

 

중간에 삽입할 경우

현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야한다. 밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 O(N)개 이다.

 

배열 선택시 고려할 점

배열은 임의 접근이라는 특징이 있어 데이터에 인덱스로 바로 접근할 수 있어 데이터에 빈번하게 접근하는 경우 효율적이지만 메모리 낭비가 발생할 수 있다. 따라서 다음 사항을 고려해 배열을 선택해야 한다.

 

1. 할당할 수 있는 메모리 크기 확인

• 보통은 정수형 1차원 배열은 1000만 개, 2차원 배열은 3000 * 3000 크기를 최대로 생각한다.

2. 중간에 데이터 삽입이 많은지 확인

• 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 자주 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있다.

 

(배열을 리스트로 표현하기로 했으므로 구현 시에는 배열 크기에 대한 고민은 하지 않는다. 공부하는 용도로만 읽고 기억)

 

 

자주 사용하는 리스트 기법 

https://wjdwwidz.tistory.com/27

[정리] 코딩테스트 자주 활용하는 python 리스트 함수

 

깨알 같은 리스트 연관 메서드

• 리스트의 전체 데이터 개수를 반환하는 len( ) 함수
• 특정 데이터가 처음 등장한 인덱스를 반환하는 index( ) 메서드, 없으면 -1 반환
• 사용자가 정한 기준에 따라 리스트 데이터를 정렬하는 sort( ) 메서드
  • sort 메서드에 아무런 인수도 전달하지 않으면 오름차순으로 데이터를 정렬한다. 만약 다음과 같이 기준을 전달하면 내림차순으로 정리한다. fruits.sort(reverse=True) 
    이때 sort 메서드는 원본 리스트를 정렬한다.
• 특정 데이터 개수를 반환하는 count( ) 메서드

 

 

---

ref : https://wikidocs.net/book/13314

[되기] 코딩 테스트 합격자 되기 - 파이썬 편(~179스택까지)