코딩 테스트 완전 정복 ・ 배열

my_list = [1, 2, 3]
my_list = my_list + [4, 5] # [1, 2, 3, 4, 5]

배열 선언

일반적인 방법 

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 * 4인 리스트를 선언하는 예
arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]

 

 

 

1차원 배열이 메모리에 할당된 모습

2차원 배열이 메모리에 할당된 모습

 

왼쪽은 2차원 배열을 사람이 이해하기 쉽도록 2차원으로 표현한 것이고,

오른쪽은 실제 메모리에 2차원 배열이 저장된 상태를 표현한 것입니다.

 

실제로는 오른쪽처럼 0행, 1행 순서로 데이터를 할당해 1차원 공간에 저장합니다.

 

 

 

배열 연산의 시간 복잡도

배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있습니다.

따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)입니다.

 

배열에 데이터를 추가하는 경우는, 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라집니다.

맨 뒤에 삽입할 경우의 시간 복잡도는 O(1)입니다.

맨 앞에 삽입할 경우의 시간 복잡도는 O(N)입니다. (기존 데이터를 한 칸씩 뒤로 밀어야 하기 때문)

중간에 삽입할 경우의 시간 복잡도는 O(N)입니다. (밀어야 하는 데이터의 개수가 N개일 때)

 

배열을 선택할 때 고려할 점

데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있습니다.

하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있습니다.

다시 말해 배열은 임의 접근이라는 특징이 있어 데이터에 인덱스로 바로 접근할 수 있어

데이터에 빈번하게 접근하는 경우 효율적이지만 메모리 낭비가 발생할 수 있습니다.

 

코딩 테스트에서는 다음 사항을 고려하여 배열을 선택해야 합니다.

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

(배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있습니다)

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

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

(배열은 선형 자료구조 이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면

시간 복잡도가 높아져서 실제 시험에서 시간 초과가 발생할 수 있습니다.) 

 

 

+ 연산자로 데이터 추가

연산자로 리스트 맨 끝에 다른 리스트의 데이터를 추가할 수도 있습니다. 

 

insert() 메서드로 데이터 삽입

첫 번째 인수에 데이터를 삽입할 위치를 받고, 

두 번째 인수에 삽입할 데이터를 받습니다.

my_list = [1, 2, 3, 4, 5]
my_list.insert(2, 9999) # [1, 2, 9999, 3, 4, 5]

 

 

pop() 메서드로 특정 위치의 데이터 삭제

인수로 인덱스를 받아 삭제하고, 삭제한 데이터의 값을 반환합니다.

my_list = [1, 2, 3, 4, 5]
popped_element = my_list.pop(2) # 3
print(my_list)  # [1, 2, 4, 5]

 

remove() 메서드로 특정 데이터 삭제 

remove() 메서드는 pop() 메서드와 다르게 특정 위치가 아닌, 특정 데이터 자체를 삭제하는 함수입니다.

my_list = [1, 2, 3, 2, 4, 5] 
my_list.remove(2) # [1, 3, 2, 4, 5]

 

 

💡 Tips

코딩 테스트에서 활용하면 유용한 4가지 메서드

1. len(): 리스트의 전체 데이터 개수 반환 

2. index(): 특정 데이터가 처음 등장한 인덱스 반환 (없으면 -1 반환)

3. sort(): 리스트 데이터를 정렬

4. count(): 특정 데이터 개수 반환

fruits = ["apple", "banana", "cherry", "apple", "orange", "banana", "kiwi"]
len(fruits) # 7
fruits.index("banana") # 1
fruits.sort( ) # ["apple", "apple", "banana", "banana", "cherry", "kiwi", "orange"]
fruits.count("apple") # 2

 

 

해시 알고리즘 시간 복잡도 

set()은 해시 알고리즘으로 데이터 저장하므로 시간 복잡도 O(N)을 보장합니다.

 

해시 알고리즘 자체는 시간 복잡도가 O(1)이지만,

리스트의 원소 개수가 N인 경우 중복값을 제거하기 위해

리스트를 한 번 순회하고 삽입해야 하므로 시간 복잡도는 O(N)입니다.