배열 개념에 대해 이해하고 활용하는 방법을 알 수 있습니다. 코딩 테스트 난이도별로 배열 관련 문제를 풀며 여러 함정을 확인하고 이를 해결하는 방법에 익숙해집니다.
배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조입니다. 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있습니다. 총 3편으로 정리했습니다. 2편은 배열의 효율성과 자주 활용하는 리스트 기법입니다.
1. 배열의 개념
2. 배열의 효율성과 자주 활용하는 리스트 기법
3. 배열 몸풀기 문제
배열의 효율성
이제 배열 연산의 시간 복잡도를 공부하면서 배열의 효율성을 알아보겠습니다.
배열 연산의 시간 복잡도
배열 데이터에 접근할 때의 시간 복잡도를 알아봅시다. 배열은 임의 접근이라는 방법으로 배열의 모든 위치에 있는 데이터에 단 한 번에 접근할 수 있습니다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)입니다. 배열에 데이터를 추가하는 경우는 어떨까요? 배열은 데이터를 어디에 저장하느냐에 따라 추가 연산에 대한 시간 복잡도가 달라집니다.
※ 삭제 연산의 경우도 추가와 마찬가지의 시간 복잡도를 가집니다.
맨 뒤에 삽입할 경우
다음과 같은 배열이 있을 때 2를 추가한다고 생각해봅시다. 맨 뒤에 삽입할 때는 arr[3]에 임의 접근을 바로 할 수 있으며 데이터를 삽입해도 다른 데이터 위치에 영향을 주지 않습니다. 따라서 시간 복잡도는 O(1)입니다.
맨 앞에 삽입할 경우
데이터를 맨 앞에 삽입한다면 어떨까요? 이 경우 기존 데이터들을 뒤로 한 칸씩 밀어야 합니다. 즉, 미는 연산이 필요합니다. 데이터 개수를 N개로 일반화하면 시간 복잡도는 O(N)이 되겠네요.
중간에 삽입할 경우
중간에 삽입할 경우도 보겠습니다. 5 앞에 데이터를 삽입한다면 5 이후의 데이터를 뒤로 한 칸씩 밀어야 할 겁니다. 다시 말해 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산을 해야 합니다. 밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 O(N)이겠네요.
배열을 선택할 때 고려할 점
데이터에 자주 접근하거나 읽어야 하는 경우 배열을 사용하면 좋은 성능을 낼 수 있습니다. 예를 들어 그래프를 표현할 때 배열을 활용하면 임의 접근을 할 수 있으므로 간선 여부도 시간 복잡도 O(1)로 판단할 수 있습니다. 하지만 배열은 메모리 공간을 충분히 확보해야 하는 단점도 있습니다. 다시 말해 배열은 임의 접근이라는 특징이 있어 데이터에 인덱스로 바로 접근할 수 있어 데이터에 빈번하게 접근하는 경우 효율적이지만 메모리 낭비가 발생할 수 있습니다. 따라서 코딩 테스트에서는 다음 사항을 고려해 배열을 선택해야 합니다.
- 할당할 수 있는 메모리 크기를 확인해야 합니다. 배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당에 실패할 수 있습니다. 운영체제마다 배열을 할당할 수 있는 메모리의 한계치는 다르지만 보통은 정수형 1차원 배열은 1000만 개, 2차원 배열은 3000 * 3000 크기를 최대로 생각합니다.
- 중간에 데이터 삽입이 많은지 확인해야 합니다. 배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도가 높아져 실제 시험에서 시간 초과가 발생할 수 있습니다.
※ 우리는 배열을 리스트로 표현하기로 했으므로 구현 시에는 배열 크기에 대한 고민은 하지 않습니다. 공부하는 정도로만 읽고 기억해두기 바랍니다.
자주 활용하는 리스트 기법
파이썬에서 배열 자료구조가 필요한 때는 앞서 언급했듯 리스트를 활용합니다. 여기서는 코딩 테스트에 자주 활용하는 리스트 기법을 알아보겠습니다.
리스트에 데이터 추가
여기서는 리스트에 데이터를 삽입하는 방법을 알아보겠습니다.
append( ) 메서드로 데이터 추가
맨 끝에 데이터를 추가하려면 append( ) 메서드를 사용하면 됩니다.
# 리스트의 맨 끝에 데이터 추가
my_list = [1, 2, 3]
my_list.append(4) # [1, 2, 3, 4]
+ 연산자로 데이터 추가
+ 연산자로 리스트 맨 끝에 다른 리스트의 데이터를 추가할 수도 있습니다. 다음 코드는 기존 my_list = [1, 2, 3]에 [4, 5]를 추가해 [1, 2, 3, 4, 5]가 되었습니다.
my_list = [1, 2, 3]
my_list = my_list + [4, 5] # [1, 2, 3, 4, 5]
insert( ) 메서드로 데이터 삽입
insert( ) 메서드를 사용하면 특정 위치에 데이터를 삽입할 수 있습니다. insert( ) 메서드는 첫 번째 인수에 데이터를 삽입할 위치를 받고, 두 번째 인수에 삽입할 데이터를 받습니다. 이렇게 하면 지정한 위치에 데이터를 삽입하고 뒤쪽 데이터를 하나씩 뒤로 이동시킵니다.
my_list = [1, 2, 3, 4, 5]
my_list.insert(2, 9999) # [1, 2, 9999, 3, 4, 5]
리스트에서 데이터 삭제
이번에는 리스트에서 데이터를 삭제하는 방법을 알아봅니다.
pop( ) 메서드로 특정 위치의 데이터 팝
pop( ) 메서드는 팝할 데이터의 인덱스를 인수로 받아 삭제하고 삭제한 데이터의 값을 반환합니다.
my_list = [1, 2, 3, 4, 5]
popped_element = my_list.pop(2) # 3
print(my_list) # [1, 2, 4, 5]
pop(2)를 호출하면 3을 삭제하면서 반환하므로 popped_element에는 3이 저장됩니다. 이후 my_list를 출력하면 [1, 2, 4, 5]를 출력합니다.
remove( ) 메서드로 특정 데이터 삭제
remove( ) 메서드는 앞서 설명한 pop( ) 메서드와 다르게 특정 위치가 아닌, 특정 데이터 자체를 삭제하는 함수입니다. remove( ) 메서드는 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제합니다.
my_list = [1, 2, 3, 2, 4, 5]
my_list.remove(2) # [1, 3, 2, 4, 5]
처음 등장하는 위치의 데이터라는 말을 설명하기 위해 리스트에 일부러 같은 데이터를 넣어두었습니다. 이 상태에서 remove(2)를 실행하면 첫 번째 위치에 있는 2를 삭제합니다.
리스트 컴프리헨션으로 데이터에 특정 연산 적용
리스트 컴프리헨션(List Comprehension)은 기존 리스트를 기반해 새 리스트를 만들거나 반복문, 조건문을 이용해 복잡한 리스트를 생성하는 등 다양한 상황에서 사용할 수 있는 문법입니다.
리스트에 제곱 연산 적용 예
예를 들어 리스트의 모든 데이터에 제곱 연산을 적용하려면 다음과 같이 코드를 작성합니다.
numbers = [1, 2, 3, 4, 5]
squares = [num**2 for num in numbers] # [1, 4, 9, 16, 25]
여기서 여러분이 주목해야 하는 점은 numbers 리스트의 값 변화 유무입니다. numbers값 자체는 [1, 2, 3, 4, 5]로 이전과 비교해서 바뀌지 않았습니다. 이처럼 리스트 컴프리헨션은 연산이 끝난 리스트를 반환할 뿐이지 연산 대상 리스트를 바꾸지 않습니다.
💡합격 조언: 깨알 같은 리스트 연관 메서드
이외에도 코딩 테스트에서 활용하면 유용한 깨알 같은 4가지 메서드를 코드와 함께 소개하겠습니다.
- 리스트의 전체 데이터 개수를 반환하는 len( ) 함수
- 특정 데이터가 처음 등장한 인덱스를 반환하는 index( ) 메서드, 없으면 -1 반환
- 사용자가 정한 기준에 따라 리스트 데이터를 정렬하는 sort( ) 메서드
- 특정 데이터 개수를 반환하는 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
sort( ) 메서드에 아무런 인수도 전달하지 않으면, 즉, 아무 기준도 적용하지 않으면 오름차순으로 데이터를 정렬합니다. 만약 다음과 같이 기준을 전달하면 내림차순으로 데이터를 정리합니다. 이때 sort( ) 메서드는 정렬된 값을 반환하지 않고 원본 리스트를 정렬합니다.
fruits.sort(reverse=True)
3편은 배열 몸풀기 문제입니다.
자료구조, 알고리즘, 빈출 100 문제로 대비하는 코테 풀 패키지
[되기] 코딩 테스트 합격자 되기(파이썬 편)
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
