자료구조 : 배열(Array)

 

 배열이란....

  배열은 데이터를 저장하고 구성하는 가장 기본적인 데이터 구조로 배열은 단순한 것이 특징이다. 배열은 자료형이 같은 요소를 저장하며 요소(element)란 배열에 저장된 각각의 자료를 뜻한다. 이러한 요소들에 매겨진 숫자를 배열의 인덱스(index)라 하며 주소와 비슷한 개념으로 이해하면 된다.. 배열의 요소들은 순차적, 연속적으로 정렬되어 있는 것이 특징이다. 배열의 종류로는 1차원 배열, 2차원 배열, 그보다 더 여러 배열들이 있는 다차원 배열이 있다.

 

 

  배열의 삽입/삭제의 빅오 표기법은 O(N) 이며, 탐색은 O(1) 이다.

 

  배열의 간략한 파이썬 코드는 다음과 같다.

# Array
arr = [5, 10, 15, 20]
arr[2] = 30
print(arr)

  print 결과 [5, 10, 30, 20]이 출력될 것이다. 그 뜻은 제일 앞자리가 0 부터 시작한다는것을 의미한다. Python 에서는 리스트를 사용하고 C++ 에서는 int arr[4] = {10, 20, 30, 40} 으로 미리 사이즈를 정하는데 Python은 C++ 과는 다르게 사이즈 변경이 자유롭다. 

 

배열의 탐색

  배열에서 메모리 공간을 접근하는 방식 덕분에 빠른 속도가 장점인데 메모리에 접근하는 방식은 위의 코드 arr[2] = 5 를 예시로 들자면 2 의 주소를 찾기 위해서 인덱스 2 * 4byte =  8byte(메모리 주소값)로 계산하여 순차적으로 0, 1, 2 순서로 메모리에 접근하는 것이 아니라 계산 결과에 따라 바로바로 메모리에 접근한다. 그렇기에 탐색이 O(1)로 빠르다.

 

  수식에서 4byte가 나오는 이유는 int 형의 크기가 4byte 이기 때문이다. 또다른 예시로 만약에 arr[4]의 주소를 찾고 싶다면 4 * 4byte = 16byte로 인덱스 4의 int형 크기는 16byte 로 계산결과에 따라 인덱스 4를 바로 탐색하게 된다. 이러한 접근 방식을 임의 접근(random access)이라 한다.

 

배열의 삽입/삭제

  배열의 삽입/ 삭제는 탐색에 비해 느린 O(N)(최악의 경우)이다. 이는 삽입/삭제하는 방식과 관련되어 있는데 배열 중간에 값을 삽입하면 나머지 뒤에 있는 값들은 한 칸씩 차례대로 뒤로 밀려나기 때문이다. 따라서 삽입/삭제를 자주하는 경우라면 그리 효율적이지 않다.

배열 연습문제

문제1

data_list = [1, 2, 3], [4, 5, 6], [7, 8, 9]

위의 2차원 배열에서 9, 8, 7 을 순서대로 출력해 보라

print(data_list [2] [2])
print(data_list [2] [1])
print(data_list [2] [0])

출력 결과

9

8

7 

 

풀이

이 문제의 풀이를 그림으로 표현하면 다음과 같다.

9, 8 7 을 출력하기 위해서는 출력을 원하는 행과 열을 입력하면 된다.

 

문제2

dataset = ['Braund, Mr. Owen Harris',
'Cumings, Mrs. John Bradley (Florence Briggs Thayer)',
'Heikkinen, Miss. Laina',
'Futrelle, Mrs. Jacques Heath (Lily May Peel)',
'Allen, Mr. William Henry',
'Moran, Mr. James',
'McCarthy, Mr. Timothy J',
'Palsson, Master. Gosta Leonard',
'Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)',
'Nasser, Mrs. Nicholas (Adele Achem)',
'Sandstrom, Miss. Marguerite Rut',
'Bonnell, Miss. Elizabeth',
'Saundercock, Mr. William Henry',
'Andersson, Mr. Anders Johan',
'Vestrom, Miss. Hulda Amanda Adolfina',
'Hewlett, Mrs. (Mary D Kingcome) ',
'Rice, Master. Eugene']

위의 dataset 에서 단어 's' 가 들어간 횟수를 구하라

s_count = 0
for data in dataset:
	for index in range(len(data)):
    	if data[index] == 's':
        	s_count += 1 
            
print(s_count)

출력 결과

34