2강: 선형 배열(Linear Array)

---

Python 의 선형 배열

배열

원소들을 순서대로 늘어놓은 것

data	2	7	-2	5	10
index	0	1	2	3	4

Python 에서의 리스트(list)

0	'Bob'
1	'Cat'
2	'Spam'
3	'Programmers'

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

---

리스트 (배열) 연산

상수 복잡도 연산

1. 원소 덧붙이기

append()

2. 끝에서 꺼내기

pop()

시간복잡도

• 순식간에(빠르게) 할 수 있는 일
  • 리스트의 길이와 무관(상수 시간) O(1)

선형 함수 복잡도 연산

1. 원소 삽입하기

2. 원소 삭제하기

시간복잡도

• 리스트의 길이가 길면 오래 걸리는 일
  • 리스트의 길이에 비례 (선형 시간) O(N)

---

실습

연습문제 1

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

힌트 :

• 주어진 원소를 삽입할 위치를 찾는다.
• 해당 위치에 원소를 삽입한다.
  • 그 결과는, 여전히 정렬된 상태를 유지하는 리스트

코드

def solution(L, x):
    answer = []
    index_x = 0
    
    for i in range(len(L)):
        print(i)
        if L[i] > x:
            index_x = i
            break
        elif i == len(L) - 1:
            index_x = i + 1
    
    L.insert(index_x,x)
    answer = L
    
    return answer

연습문제 2

주어진 리스트에서 특정 원소를 모두 찾아내라

힌트 :

• index() 메소드를 이용한다.
• 리스트 슬라이싱을 이용해서 반복하여 찾는다.

코드

def solution(L, x):
    answer = []
    
    while x in L:
        index_x = L.index(x)
        if answer:
            answer.append(index_x + answer[-1]+1)
        else:
            answer.append(index_x)
        L = L[index_x+1:]
        
    if not answer:
        answer.append(-1)
    return answer

---