자료구조와 알고리즘2

선형 배열(Liner Array)

2.선형 배열(Liner Array)

배열
원소들을 순서대로 늘어놓은것 (파이썬 list)
(주로 인덱스는 0부터 시작)

파이썬 list의 특징
여러 타입의 데이터라도 배열을 만들 수 있다
각 원소의 길이가 같지 않아도 된다

리스트 연산
1. 원소 덧붙이기 : list.append(원소)

• 리스트의 끝에 원소를 추가

2. 원소 끝에서 꺼내기 : list.pop()

• 끝에서 원소를 하나 꺼냄 (리스트의 마지막 원소를 삭제하고 삭제한 원소를 반환함)

1,2 는 리스트의 길이와 무관한 시간(상수시간)으로 동작한다 O(1)

3. 원소 삽입하기 : list.insert(index, 원소)

• 인덱스 번호에 원소를 삽입

4. 원소 삭제하기 : del(list[index])

• 인덱스 번호의 원소 삭제

3,4 는 리스트의 길이에 비례하는 시간으로(선형시간)으로 동작한다 O(n)

추가정리 서술

여기엔 append index insert의 작동원리와 구조를 통해서 시간복잡도를 정리

pop과 del의 차이

pop은 파라메타값을 인덱스를 가지는 원소를 삭제하고 반환하지만 del은 반환 없이 삭제함 그런 특징때문에 del의 실행시간이 pop 보다 빠름
단, 인덱스가 -1 인경우, 파이썬 리스트는 원소를 삭제하면 삭제된 원소의 뒷 원소들을 앞으로 당기는 연산을 수행하기 때문에 pop의 파라메타값이 비어있을경우에는 pop은 리스트를 순회하지 않고 작동하기 때문에 상수 시간의 시간복잡도를 가진다
del의 경우도 -1번 인덱스의 원소를 삭제 할시 시간복잡도는 O(1)이다

append와 insert

append는 리스트의 맨 마지막에 추가하는 개념이고 insert는 중간에 삽입하는 개념이다 마찬가지로 값을 추가 하고 한칸씩 밀어 줘야 하기에 시간이 선형시간이 걸린다

2-1 실습

정렬된 리스트 L이 주어질때 원소 x를 올바른 위치에 삽입하여 반환하는 함수를 완성하시오

def solution(L, x):
    cnt = 0
    for i in L:
        if i < x:
            cnt +=1
        else:
    answer = L
    answer.insert(cnt,x)
    return answer

2-2 실습

리스트 L이 주어질 때 x의 인덱스를 모두 반환하는 함수를 완성하시오

단, 리스트에 x가 존재하지 않을 경우 -1을 반환하시오

def solution(L, x):
    answer = []
    for i in range(len(L)):
        if L[i] == x:
            answer.append(i)
    if len(answer) == 0 :
        return [-1]    
    return answer