<자료구조와 알고리즘> 선형 배열 with Python

선형 배열(Linear Arrays) : 데이터가 선형처럼 하나의 열로 나열되어 있어서 붙여진 이름입니다.

파이썬에서는 배열을 리스트 형태로 사용합니다.

 

아까 언급했듯이 배열은 원소들을 순서대로 늘어 놓은 것을 의미합니다.

그리고 각각의 원소에는 index라는 번호가 붙게됩니다. 

index는 0으로 시작됩니다. 이것에 대한 유래는 나중에 알아보도록 하겠습니다.

 

파이썬의 리스트는 다음과 같이 표현할 수 있습니다.

L = ['Bob', 'Cat', 5, 'Programmers']

다른 종류의 데이터 타입도 리스트 안에 넣을 수 있다는 특징을 가지고 있죠.

접근 방법은 다음과 같습니다.

L[0] / L[-1]

 

이제 리스트 연산에 대해서 알아보겠습니다\

1. 원소 덧붙이기

    L.append('New') 와 같이 추가할 수 있습니다

2. 원소 꺼내기

    L.pop() 하면 끝에서 하나의 원소를 꺼냅니다

 

위와 같은 동작의 시간 복잡도는 상수 시간이라고 할 수 있습니다. 왜냐면 순식간에 할 수 있는 일이기 떄문이죠.

O(1) 라고 표시할 수 있습니다. 이 표기법은 빅 오 Notation 이라고 합니다

 

3. 원소 덧붙이기 2

L.insert(3, 65)  원소 3번째에 65라는 값을 덧붙여라. 라는 명령어입니다.

그러니까 0 1 2 다음에 추가가 될 겁니다

 

4. 원소 삭제

del(L[2]) "리스트 L에 인덱스 번호 2번을 삭제해라" 라는 뜻입니다.

 

중요한 것은 3번과 4번에서 삭제하고 추가하는 과정이 존재한다는 것입니다.

추가의 경우 인덱스 2번 이후에 있는 모든 원소들에 index + 1 을 통해 자리를 확보한 뒤 인덱스 3번에 65를 추가하는 것이고 삭제의 경우 인덱스 2번에 해당하는 원소를 삭제한 뒤 2번 다음에 있던 원소들에 index - 1을 통해 축소된 리스트를 얻게 되는 겁니다. 그래서 insert나 del은 pop() 이나 append()  같은 메서드보다 더 많은 시간이 들게 되는 것입니다.

따라서 insert, del() 메서드는 리스트의 길이에 비례해서 실행 시간이 걸리게 됩니다. 즉, 리스트의 길이가 길면 시간이 오래 걸린다는 것을 뜻합니다. 이를 선형 시간이라고 합니다.

 

5. 원소 탐색하기

가장 중요하다고 할 수 있습니다.

L.index('Spam') 을 통해 list 안에 해당 값이 있는지를 알 수 있습니다.

 

def solution(L, x):
    answer = []
    
    for i in L:
        if i < x:
            print()
        else:
            n = L.index(i)
            L.insert(n, x)
            break;
    if max(L) < x:
        L.append(x)
    answer = L
    return answer

관련 예제 1에 대한 제 풀이 코드입니다.