배열, 연결 리스트, 선택 정렬 알고리즘

같은 성격의 값을 여러 개 저장할 때는 배열 또는 리스트를 사용한다.

배열(Array)

• 배열의 항목은 모두 이웃하는 위치에 저장
• 삽입 시 배열 크기 만큼의 연속된 공간이 필요
• 모든 요소는 같은 자료형이어야 함 (int, float, string 등)
• 항목을 삽입하거나 삭제할 시 기존 데이터의 메모리 주소도 연쇄적으로 변경해야 함
• index를 이용해 특정 번째의 데이터에 접근 용이
• 속도 : 읽기↑/ 삽입·삭제↓

연결 리스트(Linked List)

• 리스트의 항목은 이웃하는 위치에 저장되지 않고, 각 항목이 다음 항목의 주소를 가리키고 있음
• 항목을 삽입하거나 삭제할 시 기존 데이터가 가리키는 주소값만 변경해주면 됨
• 하나의 요소는 다음 요소의 주소만을 가지고 있기 때문에,
  특정 번째 요소에 접근하기 위해서는 앞의 모든 요소를 차례대로 거쳐야만 함.
  ex) 리스트의 5번째 요소 값은? 1번째 요소→2번째 요소→3번째 요소→4번째 요소→5번째 요소
• 속도 : 삽입·삭제↑/ 읽기↓

선택 정렬 알고리즘

전체 리스트에서 특정 요소를 선택하여 새로운 리스트에 삽입하는 방식으로 새로운 정렬방식의 리스트를 얻음

#최소값 index를 찾는 함수
def findSmallest(arr):
	smallest = arr[0]
	smallest_index = 0
	for i in range(1, len(arr)):
		if(arr[i] < smallest):
			smallest = arr[i]
			smallest_index = i
	return smallest_index

#목록을 오름차순으로 정렬하는 함수
def selectionSort(arr):
	newArr = []
	#목록 전체 원소개수 만큼 반복
	for i in range(len(arr)):
		smallest_index = findSmallest(arr)
		newArr.append(arr.pop(smallest_index))
	return newArr

arr = [9, 7, 5, 8, 4, 2, 1]
print('정렬 전 :{}'.format(arr))
newArr = selectionSort(arr)
print('정렬 후 :{}'.format(newArr))
print('\n')

arr2 = ['사과', '포도', '오렌지', '수박', '바나나']
print('정렬 전 :{}'.format(arr2))
newArr2 = selectionSort(arr2)
print('정렬 후 :{}'.format(newArr2))

정렬 전 :[9, 7, 5, 8, 4, 2, 1]
정렬 후 :[1, 2, 4, 5, 7, 8, 9]


정렬 전 :['사과', '포도', '오렌지', '수박', '바나나']
정렬 후 :['바나나', '사과', '수박', '오렌지', '포도']

 

1. 목록에서 최소값 탐색
2. 해당 값을 새로운 리스트에 삽입 (append)
3. 해당 값을 기존 리스트에서 삭제 (pop)
4. 기존 리스트는 텅텅비고, 오름차순의 새로운 리스트가 생성됨

연습문제

2-1. 가계부 앱을 개발하려고 한다. 매일 돈을 어디에 썼는지 기록하고 월말이 되면 지출을 되돌아보고 소비 금액의 합계를 계산한다. 자료를 읽는 것보다 삽입하는 일이 훨씬 많은데, 이때 배열과 리스트 중 어떤 것을 사용해야 하는가?

=> 리스트

배열 : 읽기가 빠르고 삽입 삭제가 느리다.

리스트 : 읽기가 느리고, 삽입 삭제가 빠르다. 

임의의 위치의 데이터를 읽는 일이 없고, 전체 합계를 구하기 때문에 리스트를 사용하기 적합하다

 

2-2. 레스토랑에서 고객의 주문을 받아서 처리하는 앱을 만들고 있다고 가정하자.

그 앱은 우선 주문목록을 저장해야 한다. 서비스 담당 직원은 이 리스트에 계속해서 주문을 추가하고, 요리사는 리스트에서 주문을 꺼내어 조리를 한다.(=주문 큐) 서비스 담당 직원은 큐의 뒤에 주문을 추가하고, 요리사는 큐의 첫 번째에서 주문을 꺼내어 요리한다. 이러한 큐를 구현하는 데 배열과 리스트 중 어떤것을 사용해야 하겠는가?

=> 리스트

선입선출(First In First Out) 방식의 큐.

데이터 삽입 삭제가 빈번하며, 요리사는 항상 첫번째 요소에만 접근해야 하기 때문에 리스트가 적합하다.

 

2-3. 페이스북이 사용자 이름 목록을 가지고 있다고 했을 때, 누군가가 페이스북에 로그인을 하려고 하면 사용자 이름 목록에서 이름을 검색해야 한다. 만약 사용자 이름 목록에 아이디가 없다면 로그인을 할 수 없으며, 사람들은 빈번하게 로그인을 시도한다. 페이스북이 이 목록을 검색하기 위해 이진 탐색을 사용한다면, 이진탐색을 위해서는 임의접근이 가능해야 한다.(index를 통해 전체 목록 중 중간값에 바로 접근해야 함) 이 경우 배열과 리스트 중 어떤 것을 사용해야 하는가?

=> 배열

 

2-4. 그러나 회원가입을 통해 사용자 이름 목록에는 사용자 등록도 자주 발생한다. 위에서 배열을 사용하기로 했으면 단점은? 

=> 배열은 연속된 메모리에 데이터를 저장해야하기 때문에 새로운 데이터를 삽입할 경우 기존의 데이터 위치도 이동되게 된다.

=> 배열에 원소를 삽입하는 것이 느리며, 사용자 이름을 담색하는 데 이진탐색을 사용하기 때문에 배열의 요소가 늘 정렬되어 있어야 한다. 그러나 새로운 사용자를 등록하면 배열의 맨 마지막에 추가되기때문에 등록때마다 배열을 새로 정렬해야 한다.

 

2-5. 26개의 칸(A~Z)을 가진 배열이 있으며, 각 칸이 각자 다른 연결리스트(Alex, Alexander)를 가리키는 복합 자료 구조를 배열, 리스트와 비교해보자. 검색이나 삽입 시 어떤 것이 빠를까?

=> 검색시에는 배열보다 느리며 리스트보다는 빠르다. 삽입시에는 배열보다는 빠르며 리스트보다는 같다.