선형 배열(Linear Arrays)

• 데이터들이 일열로 쭉 늘어져있기 때문에 붙여진 이름.

배열

• 원소들을 순서대로 늘어놓은 것.
• 동일한 타입의 원소만 함께 나열할 수 있다.
  • 예를 들어, 정수 배열은 모두 정수 타입의 원소로만 구성되어야 한다.

 

리스트

• 파이썬의 리스트는 배열(Array)보다 융통성있는 구조를 제공한다.
  • 서로 다른 타입의 데이터를 원소로 채택해서 나열할 수 있다.
    • 예를 들어, 파이썬 리스트는 정수, 문자열, 객체 등 다양한 타입의 데이터를 혼합해서 포함할 수 있다.

리스트 연산

L = ["B", "C" , "S", "P"]

• L.append(”N”) → ["B", "C" , "S", "P" ,”N”] : 오른쪽 끝에 “N”을 추가.
• L.pop() → “N” : 가장 마지막 원소를 빼낸다. ["B", "C" , "S", "P" ]

append()와 pop()은 리스트 길이와 무관하게 순식간에 할 수 있다 (O(1))

 

하지만, 리스트 중간에 원소를 삽입하거나 삭제하는 것은 리스트의 길이 따라 연산시간이 늘어날 수 있다(시간 복잡도가 늘어난다)

 

원소를 중간에 삽입하는 경우

L = [1,2,3,5,6]
L.insert(3,4) #3번째 idx에 4를 삽입 

## 연산과정 ##

#1
[1,2,3,5,6,6]

#2
[1,2,3,5,5,6]

#3
[1,2,3,4,5,6]

 

원소를 중간에 삭제하는 경우

L = [1,2,3,4,5,6]
L.delete(3) #3번째 idx의 원소를 삭제

## 연산과정 ##

#1
[1,2,4,4,5,6]

#2
[1,2,4,5,5,6]

#3
[1,2,4,5,6,6]

#4
[1,2,4,5,6]

• 삽입 : 삽입하려는 index보다 뒤에 있는 index를 모두 뒤로 밀어야함.
• 삭제 : 삭제하려는 index보다 뒤에 있는 index를 모두 앞으로 밀어야함.

→ 길이가 길면 연산 시간이 길어진다 (리스트 길이에 비례해진다) → 선형 시간.(O(N))

리스트 원소 탐색

L = ["B", "C" , "S", "P"]
L.index("B") # 0 

L = ["B", "B" , "S", "P"]
L.index("B") # 0  

• 해당 값을 갖고있는 index값을 반환한다.
• 해당 같을 갖고 있는 모든 index를 반환하려면 반복문을 통해야한다.
• def find_all_indices(lst, value): return [i for i, v in enumerate(lst) if v == value]

실습 문제 풀이

• 유료 강의이므로 문제는 게시하지 않는다.

def solution(L, x):
    # L.append(x)
    # answer = sorted(L)
    a = 0

    for i in range(len(L)):
        if(x < L[i]):
            a=i
            break
        elif(L[-1] < x):
            a=len(L)


    L.insert(a,x)

• x가 가장 클 경우에 조건문을 추가해야하며, L이 오름차순이기 때문에 가장 오른쪽 값과 비교한다.

def solution(L, x):
    answer = [idx for idx, num in enumerate(L) if L[idx] == x]
    if(answer==[]):
        return [-1]
    return answer

• enumerate : 낱낱이 새다 → 반복문과 함께 사용하면 index와 value의 값을 반환한다.
• "리스트 컴프리헨션(List Comprehension)”을 이용하여 간결하게 표현하였다.