같은 타입의 변수들로 이루어진 유한 집합

배열 vs 리스트
배열이란 원소들을 순서대로 늘어놓은 것으로, 개념적인 구조, 즉 데이터를 늘어놓은 모양새를 말한다. 모든 원소가 같은 데이터 타입이어야 한다.
리스트는 데이터형을 가리킨다. 원소별로 다른 데이터 타입을 가져도 된다.

---

선형 배열 (Linear Arrays)

데이터들이 선처럼 일렬로 늘어선 형태

• 길이에 상관 없이 빠른 실행을 하는 연산 : append(), pop()
• 길이에 따라 실행 시간이 다른 연산 : insert(), del()

L = [10, 20, 40]

# 빠르게!
L.append(50)   # 마지막에 요소(50)를 추가한다.
L.pop()        # 맨 끝 요소를 삭제한다.

# 시간 고려..
L.insert(2, 30)   # 2번 인덱스에 요소(30)를 추가한다.
del(10)           # 요소 10을 삭제한다.

# 그 외
L.index(20)   # 요소 20의 인덱스를 출력한다.

Operation	Code	Average Case
인덱싱	L[index]	O(1)
슬라이싱	L[a:b]	O(b-a)
정렬	L.sort(), sorted(L)	O(nlogn)
뒤집기	L.reverse()	O(n)
탐색	x in L	O(n)
끝에 요소 추가	L.append(x)	O(1)
중간에 요소 추가	L.insert(index, x)	O(n)
삭제	del L[index]	O(n)
최솟값 찾기	min(L)	O(n)
최댓값 찾기	max(L)	O(n)
길이 구하기	len(L)	O(1)

딕셔너리 시간 복잡도는 대부분 O(1) 이다.
값 찾기 (D[key]), 값 넣어주기/덮어쓰기 (D[key] = value), 값 삭제 (del D[key])

정렬된 리스트에 원소 삽입하기

일렬로 정렬된 리스트에 임의의 값을 갖는 원소를 삽입하라. 이 값은 제일 작을 수도 있고, 제일 클 수도 있고, 중간값일 수도 있다.

• 💡 순환문을 이용하여 올바른 위치를 결정하고 insert() 메서드를 이용하여 삽입한다.
• ⚠️ 리스트 내에 존재하는 모든 원소들보다 작은 경우, 큰 경우, 혹은 중간값이 주어지는 경우에 대해서 각각 올바르게 처리해야 한다.

def solution(L, x):
    for l in L : 
        if L[-1] < x :
            L.append(x)
        elif l > x :
            L.insert(L.index(l), x)
            break
    return L

정렬된 리스트에 원소 삽입하기

인자로 주어지는 리스트 L 내에서, 또한 인자로 주어지는 원소 x 가 발견되는 모든 인덱스를 구하여 이 인덱스들로 이루어진 리스트를 반환하는 함수
💡 리스트의 index() 메서드와 리스트 슬라이싱을 활용
⚠️ 리스트의 index() 메서드는, 인자로 주어지는 원소가 리스트 내에 존재하지 않을 때 ValueError 발생

def solution(L, x):
    answer = []
    for l in L :
        if l == x :
            answer.append(L.index(l))
    return [i for i, l in enumerate(L) if l==x] if x in L else [-1]