📖배열이란?
배열(Array)이란, 같은 종류의 데이터들이 저장될 수 있는 자료구조이다. 기본적인 배열의 선언 방식은 다음과 같다.
데이터타입 배열이름[배열길이]
배열은 인덱스(index)라고 하는 번호와 인덱스에 대응하는 데이터들로 이루어져 있으며, 데이터의 인덱스는 배열의 시작점으로부터 데이터가 저장되어 있는 상대적인 위치를 나타낸다. 일반적으로 배열의 시작점이자 인덱스의 첫번째 번호는 0부터 시작한다.
예를 들어, 배열 {5, 3, 1, 2, 4}에 대한 인덱스는 다음과 같다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 원소값 | 5 | 3 | 1 | 2 | 4 |
❓배열의 장점
- 구조가 간단해 사용하기 쉽다
- 인덱스로 쉽게 값을 검색할 수 있다
- 데이터를 읽어오는데 걸리는 시간이 빠르다
❓배열의 단점
- 선언과 동시에 크기를 지정하므로 변경할 수 없다
- 배열의 중간에 데이터를 추가하거나 삭제하는 데에 시간이 많이 걸린다
📖배열의 회전
알고리즘 문제를 풀다보면 배열을 회전시켜야 하는 문제를 종종 만나게 된다. 다음과 같이 1차원 배열을 오른쪽으로 회전시킨다고 가정하고, 사용할 수 있는 간단한 방법을 살펴보려고 한다.
배열 {1, 2, 3, 4, 5}를 오른쪽으로 2번 회전 : {1, 2, 3, 4, 5} -> {4, 5, 1, 2, 3}
❓파이썬의 리스트 슬라이싱
파이썬은 기본적으로 리스트의 슬라이싱 기능을 제공한다. 인덱스를 이용하여 리스트를 원하는만큼 자르는 것이다.
>>> array = [1, 2, 3, 4, 5]
>>> print(array[0:3])
[1, 2, 3]위와 같이 배열이름[시작번호:끝번호]를 통해 슬라이싱 기법을 사용할 수 있는데, 끝번호에 해당하는 원소는 포함하지 않는다.
이러한 슬라이싱 기법을 사용하면 원하는 회전 수만큼 배열의 끝에서부터 원소를 잘라내 배열의 앞에 이어붙이면 된다.
def rotate(arr, n):
n %= len(arr)
front = arr[:-n]
back = arr[-n:]
return back + frontarr은 회전할 배열의 이름, n은 원하는 회전 수이다.
이외에도, 파이썬에서는 collections 모듈의 deque을 이용하면 rotate라는 이미 구현된 함수를 통해 쉽게 배열을 회전시킬 수 있다.
❓역전의 역전
앞서 리스트 슬라이싱을 사용한 코드와 같이 회전하기 전 앞쪽에 있는 원소들을 front, 뒤쪽에 있는 원소들을 back이라고 하자.
front와 back을 각각 좌우로 뒤집고(reverse) 합친 후, 합친 배열을 다시 한번 뒤집으면 원하는 회전 후 배열이 만들어진다.
def rotate(arr, n):
n %= len(arr)
front = arr[:-n]
back = arr[-n:]
front.reverse()
back.reverse()
temp = front + back
temp.reverse()
return temp