메모리가 동작하는 방법

컴퓨터에는 엄청나게 많은 서랍이 있고 각각 주소가 붙어있다. 메모리에 저장할 때마다 공간을 요청해야한다. 만약에 여러 개의 원소를 저장해야 한다면 배열과 리스트 중에 한 방법을 사용해야 한다.

배열과 연결 리스트

메모리에 여러개의 목록을 저장한다고 가정하면 어떤 배열을 사용하는게 좋은가?

배열은 메모리에 차례차례 붙여저 저장해야한다. 만약에 배열의 크기가 늘어나는데 이미 그 옆자리에 다른 데이터가 저장되어 있다면 다른 곳으로 그 크기만큼 비어있는 공간으로 옮겨야 할 것이다.

연결리스트

연결리스트를 사용하면 원소를 어느 곳에나 둘 수 있다. 각 원소에는 목록의 다음 원소에 대한 주소가 저장되어 있다.

장점 : 데이터의 삽입/삭제가 빠름(논리적 주소만 바꿔주면 됨) 단점 : 원하는 원소로의 접근이 느리다

배열

배열은 모든 원소의 주소를 다 알고 있다. 예를 들어 배열에 5개의 원소가 있고 주소가 00으로 시작한다면 5번쨰 원소는 04일 것이다.

장점 : 원하는 원소로의 접근이 빠름(인덱스를 가지고 있음) 단점 : 데이터의 삽입/삭제가 느림(삽입/삭제 후 모든 데이터 위치 변경)

결론

데이터의 삽입/삭제가 거의 없고, 데이터 접근이 빈번하게 이루어지는 경우는 배열, 데이터의 삽입/삭제가 빈번하게 이루어지면 연결리스트가 유리함.

리스트의 가운데에 삽입하기

할일 목록 중간에 새로운 할일을 추가한다고 가정.

연결리스트의 경우 이전 원소가 가리키는 주소만 바꾸면 쉽지만 배열은 추가된 원소의 위치 이후의 모든 원소의 위치를 바꾸어야함.

삭제하기

삭제하는 것도 마찬가지. 가리키는 위치만 바꿔주면 리스트와는 달리 배열은 삭제하고 다 옮겨야함.

원소에 바로 접근할 수 있으면 O(1)이 되고 –> 임의접근

순차적으로 원소를 하나씩 읽어야하면 O(n) –> 순차접근

선택 정렬

가수별로 정렬된 노래 목록에서 많이 들은 순서대로 정렬한다고 가정.

가장 많이 연주된 가수를 찾아 새로운 리스트에 기록하면 된다. 이를 원소 수 만큼 반복하면 정렬된 목록을 얻을 수 있다.

O(n) 실행 시간을 n번 해야하므로 O(n²)

예제 코드

# 가장 작은 정수 찾기
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 = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr

print(selectionSort([5,3,6,2,10]))

2장에서 배운 내용

• 컴퓨터 메모리는 거대한 서랍장과 같다
• 여러 항목을 저장할 떄는 배열이나 리스트 사용
• 배열을 쓰면 모든 항목은 이웃함
• 리스트를 쓰면 모든 항목은 흩어지나 각 항목은 다음 항목의 주소를 저장하고 있음
• 배열은 읽기가 빠름
• 연결리스트는 삽입과 삭제가 빠름
• 배열의 모든 원소는 같은 자료형이어야함